企业官网建设流程全解析

相关概念

满二叉树

• 高度为 n 的满二叉树节点数目为。
• 结点数量为 n 的满二叉树的高度为 log2​(n+1)

完全二叉树

除最后一层外，其余层全部结点都满；最后一层结点靠左连续排列，不能有空洞。

二叉搜索树(BST, 也称二叉排序树/二叉查找树)

平衡二叉树(BBT, 也称AVL树)

表达式树（链式二叉树）

表达式树后序遍历得到的序列就是后缀表达式（逆波兰表达式）

红黑树

...

B树(也称多路平衡查找树)

1. 阶（Order） B 树的阶定义了每个节点可以拥有的最大子节点数。
2. 平衡性B 树通过保持所有叶子节点在同一层，确保了树的平衡，从而保证了搜索效率。
3. 关键字用来做大小比较、决定往哪棵子树走的“值”。
4. 结构特点结点是方形, 以关键字做分割
5. 度：子节点的数量
6. 分支节点：度>0的节点
7. 叶节点：度=0的节点
8. 高度：等比数列求和公式 Sk = a1 *（q^k - 1）/ q -1

只需记住:

1. m阶B树，所有节点关键字不超过 m-1；根至少 1 个，其他至少一半（向上取整）减 1

2. 新增：中间挤上去

3. 删除: 找前驱后继借

m阶B树示例计算

关键字

根: 1 <= k <= m-1

非根: ⌈m/2⌉-1 <= c <= m-1

B树结构

B树的插入

• 先按二叉搜索树的方式向下找位置 → 插入到叶子 → 若节点溢出(节点数=阶数)则“分裂”
• 分裂步骤：
  1. 取中间关键字上移到父节点
  2. 左边关键字形成左子节点
  3. 右边关键字形成右子节点
  4. 父节点指针重新指向左右子节点
• 三阶B树

B树的删除

优先在叶子删除；若删的是内部节点，用前驱 / 后继替换；删除后若节点关键字不足，则通过“借”或“合并”向上修复

B+树

一颗 m阶 B+ 树满足如下条件：

1. 节点的容量限制
   • 每个非叶子节点（分支节点）最多有 m 棵子树。
   • 除根节点外，每个非叶子节点至少有 ⌈ m/2 ⌉ 棵子树。
2. 关键字与子树的关系
   • 在一个非叶子节点中，如果有 k 个关键字，那么它会有 k+1 棵子树。
   • 关键字起到分隔值域的作用，子树对应这些分隔区间。
3. 数据存储位置
   • 所有数据记录（或指向数据的指针）都存储在叶子节点中。
   • 非叶子节点只存储关键字，用于索引和导航，不直接存放数据。
4. 叶子节点的顺序结构
   • 所有叶子节点之间通过链表指针相连。
   • 这种顺序结构可以支持高效的范围查询和顺序遍历。

B树和B+树的区别

• 查找：
  • B 树：所有节点（包括内部节点）存储KV 对，查找可能在内部节点结束。
  • B+ 树：只有叶节点存储KV 对，查找必须到达叶节点。
• 插入：
  • B 树：所有节点存储KV 对，分裂时中间键值对整体上移。
  • B+ 树：只有叶节点存储KV 对，分裂时中间键复制到父节点（仅键，不带值），叶节点保留所有键。
• 删除：
  • B 树：内部节点存储KV 对，删除内部节点键需用后继/前驱替换，可能复杂。
  • B+ 树：删除只发生在叶节点，内部节点键仅需调整（复制叶节点键），操作更简单。

例题

1. 在一株高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（）

答: 5

1(根)+2(左子树)+2(右子树)=5

2. 在一棵具有 15 个关键字的 4 阶 B 树中，含关键字的结点个数最多是（）

答: 15

关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数最最少。根据 4 阶 B 树 的定义，根结点最少含 1 个关键字，非根结点中最少含 ⌈4/2⌉-1=1 个关键字，所以每个结点中，关键字数量最少都为 1 个，即每个结点都有 2 个分支，类似于排序二叉树，而 15 个结点正好可以构造一个 4 层的 4 阶 B 树，使得叶结点全在第四层，符合 B 树定义，因此为15

3. 依次将关键字 5, 6, 9, 13, 8, 2, 12, 15 插入初始为空的 4 阶 B 树后, 根节点中包含的关键字是（ ）。

答: 6,9

4. 给 7 个不同的关键字，能够构成不同 4 阶 B 树的个数为（ ）。

答: 9

• 树高为 3：每个节点内关键字个数最少取 1 时，B 树 高度为 3（类似满二叉树）——仅一种结构；
• 树高为 2:
  • 根节点关键字个数取 1，第二层两节点关键字个数均取 3——一种结构；
  • 根节点关键字个数取 2，则第二层内三个节点关键字个数分别可取 221、212、122、311、131、113 共计六种结构；
  • 根节点关键字个数取 3，则第二层显然只有四个节点各含一个关键字此一种结构。

5. 在下图所示的 5 阶 B 树 T 中，删除关键字 260 之后需要进行必要的调整，得到新的 B 树 T1。下列选项中，不可能是 T1 根结点中关键字序列的是（ ）。

A.60，90，280

B.60，90，350

C.60，85，110，350

D.60，90，110，350

答: D

排除法: 如果110放根结点, 100就成为单独一个叶节点, 不满足5阶B树的最小关键字数量

参考

计算机考研杂货铺-树形查找