什么是闭包?

闭包是指在 JavaScript 中，内部函数可以访问外部函数作用域中的变量和资源的特性。当内部函数在外部函数中定义时，它会创建一个闭包，将外部函数的词法作用域中的变量和资源保存在闭包中。这使得内部函数在外部函数执行完毕后仍然能够访问外部函数的作用域。

什么是词法作用域?

词法作用域（lexical scope）是指变量的作用域是由它们在代码中的位置决定的。在 JavaScript 中，词法作用域是通过函数的嵌套关系来确定的。这意味着内部函数可以访问外部函数的变量和资源，但外部函数无法访问内部函数的变量和资源。

什么是 Hoisting?

在编译阶段,就在代码执行前几微秒, 会扫描查找函数和变量声明. 所有这些函数和变量声明都被添加到称为词法环境(Lexical Environment)的数据结构的内存中. 这样即使在源代码声明它们之前, 也可以使用它们.

什么是词法环境?

词法环境是一个包含identifier-variable映射的结构(这里的identifier是指变量或函数的名称, variable是指实际对象[包括函数对象和数组对象]或原始值的引用).

Execution Context(执行上下文)

什么是执行上下文?

执行上下文是一个环境的抽象概念, 这个环境用于评估和执行JavaScript代码. 任何代码在JavaScript中运行时,都是在执行上下文中运行的.

执行上下文的类型

在JavaScript中执行上下文有三种类型:

• Global Execution Context(全局执行上下文)
• Function Execution Context(函数执行上下文)
• Eval Function Execution Context(eval 函数执行上下文)

Fenwick 树

Fenwick 树（也称为二进制索引树）是一种数据结构，它可以高效地更新元素和计算数字表中的前缀和。

与一个平面数组相比，Fenwick 树在两个操作之间实现了更好的平衡：元素更新和前缀和计算。在一个平面数组中，你可以存储元素或前缀和。在第一种情况下，计算前缀和需要线性时间；在第二种情况下，更新数组元素需要线性时间（在这两种情况下，另一个操作可以在常量时间内完成）。Fenwick 树允许这两个操作在 O(log n)时间内完成。这是通过将数字表示为一棵树来实现的，其中每个节点的值是该子树中数字的总和。树结构允许只使用 O(log n)的节点访问来执行操作。

线段树

线段树（Segment Tree），也称为统计树，是一种用于存储关于区间或段的信息的树数据结构。它允许查询哪些存储的段包含给定的点。它原则上是一个静态结构，也就是说，一旦构建完成就不能修改。类似的数据结构是区间树。

线段树是一棵二叉树。树的根表示整个数组。根节点的两个子节点表示数组的第一半和第二半。同样，每个节点的子节点对应于与节点对应的数组的两半。

我们从底部向上构建树，每个节点的值是其子节点值的“最小值”（或任何其他函数）。这将花费 O(n log n)的时间。执行的操作数是树的高度，即 O(log n)。为了进行范围查询，每个节点将查询分成两个子查询，一个子查询对应于每个子节点。如果查询包含节点的整个子数组，我们可以使用节点上预计算的值。利用这种优化，我们可以证明只有 O(log n)次最小操作。

红黑树

红黑树是一种自平衡的二叉搜索树，在计算机科学中使用。二叉树的每个节点都有一个额外的位，这个位通常被解释为节点的颜色（红色或黑色）。这些颜色位用于在插入和删除过程中保持树的大致平衡。

通过以一种满足特定属性的方式将树的每个节点标记为两种颜色之一，可以保持树的平衡，这些属性共同限制了树在最坏情况下可能变得不平衡的程度。当修改树时，新的树会被重新排列和重新标记以恢复颜色属性。这些属性的设计使得这种重新排列和重新标记可以高效地进行。

树的平衡并不完美，但足够好，可以确保在 O(log n)的时间内进行搜索，其中 n 是树中的元素总数。插入和删除操作以及树的重新排列和重新标记也可以在 O(log n)的时间内完成。

红黑树的一个示例：

AVL 树

在计算机科学中，AVL 树（以发明者 Adelson-Velsky 和 Landis 命名）是一种自平衡的二叉搜索树。它是第一个被发明出来的这种数据结构。在 AVL 树中，任何节点的两个子树的高度最多相差一；如果在任何时候它们相差超过一，就会进行重新平衡以恢复这个属性。查找、插入和删除在平均和最坏情况下都需要 O(log n)的时间，其中 n 是操作之前树中节点的数量。插入和删除可能需要对树进行一个或多个树旋转进行重新平衡。

动画显示将几个元素插入到 AVL 树中。它包括左旋、右旋、左右旋和右左旋。

二叉搜索树

二叉搜索树（Binary Search Tree，简称 BST）是计算机科学中一种特定类型的容器，有时也被称为有序二叉树或排序二叉树。它们用于在内存中存储“项”（如数字、名称等），可以快速进行查找、添加和删除操作。它们可以用于实现动态集合或查找表，以便通过键来查找项（例如，通过姓名查找人的电话号码）。

二叉搜索树将其键按照排序顺序存储，以便查找和其他操作可以使用二分查找的原理：在树中查找键（或查找要插入新键的位置）时，从根到叶子遍历树，与树节点中存储的键进行比较，并根据比较结果决定是继续在左子树还是右子树中搜索。平均而言，这意味着每次比较都可以跳过树的约一半，因此每次查找、插入或删除操作的时间与树中存储的项数的对数成比例。这比在（未排序的）数组中按键查找项所需的线性时间要好得多，但比哈希表上的相应操作要慢。

下图是一个大小为 9、深度为 3 的二叉搜索树示例，根节点为 8。叶子节点未绘制。

树

• 二叉搜索树
• AVL 树
• 红黑树
• 线段树 - with min/max/sum range queries examples
• 芬威克树/Fenwick Tree (Binary Indexed Tree)

在计算机科学中, 树(tree) 是一种广泛使用的抽象数据类型(ADT)— 或实现此 ADT 的数据结构 — 模拟分层树结构, 具有根节点和有父节点的子树,表示为一组链接节点。

树可以被(本地地)递归定义为一个(始于一个根节点的)节点集, 每个节点都是一个包含了值的数据结构, 除了值,还有该节点的节点引用列表(子节点)一起。
树的节点之间没有引用重复的约束。

一棵简单的无序树; 在下图中:

标记为 7 的节点具有两个子节点, 标记为 2 和 6;
一个父节点,标记为 2,作为根节点, 在顶部,没有父节点。

字典树

在计算机科学中, 字典树(trie,中文又被称为”单词查找树“或 ”键树“), 也称为数字树,有时候也被称为基数树或前缀树（因为它们可以通过前缀搜索）,它是一种搜索树–一种已排序的数据结构,通常用于存储动态集或键为字符串的关联数组。

与二叉搜索树不同, 树上没有节点存储与该节点关联的键; 相反,节点在树上的位置定义了与之关联的键。一个节点的全部后代节点都有一个与该节点关联的通用的字符串前缀, 与根节点关联的是空字符串。

值对于字典树中关联的节点来说,不是必需的,相反,值往往和相关的叶子相关,以及与一些键相关的内部节点相关。