# Self-Balancing Tree 提纲： * AVL Tree * Red-black Tree * B Tree * B+ Tree ## AVL Tree AVL Tree 是一种自平衡二叉搜索树（self-balancing BST)，数中任意节点的左子树与右子树的高度差小于或等于 1，举例如下： ![](/files/-La--H51QthdyAGCAOau) 返例如下： ![](/files/-La--P0j-vUjcYSKS5PL) 图中节点 8 的左子树高度为 3，右子树高度为 1，差为 2。 AVL 提出的原因在于解决普通二叉树可能出现的降格问题，保证在二叉树中的搜索、插入、删除操作的复杂度都能控制在 $$O(logn)$$ 的范围内。 ### Operations * Insertion * Deletion #### Insertion 每次插入新节点，先按普通二叉树的 insertion 方式插入，若树中所有节点都满足 AVL Tree 的规定，则插入完毕；若树中有节点不满足 AVL Tree 的规定，则根据情况作出相应的调整。可能出现的情况有 4 种： i) left - left： ![](/files/-La-1C3tCus6YoyfEpX5) ii) left - right: ![](/files/-La-1NZehxDnfrhEC2-a) iii) right - right: ![](/files/-La-1UeiiAQgey5amPFn) iv) right - left: ![](/files/-La-1bs4k6upsqlAqz-P) 代码实现如下： {% code title="AVL.py" %} ```python class TreeNode(object): def __init__(self, val): self.val = val self.left = None self.right = None self.height = 1 class AVLTree(object): def insert(self, root, key): # Step 1 - Perform normal BST if not root: return TreeNode(key) elif key < root.val: root.left = self.insert(root.left, key) else: root.right = self.insert(root.right, key) # Step 2 - Update the height of the ancestor node root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right)) # Step 3 - Get the balance factor balance = self.getBalance(root) # Step 4 - If the node is unbalanced, # then try out the 4 cases # Case 1 - Left Left if balance > 1 and key < root.left.val: return self.rightRotate(root) # Case 2 - Right Right if balance < -1 and key > root.right.val: return self.leftRotate(root) # Case 3 - Left Right if balance > 1 and key > root.right.val: root.left = self.leftRotate(root.left) return self.rightRotate(root) # Case 4 - Right Left if balance < -1 and key < root.right.val: self.right = self.rightRotate(root.right) return self.leftRotate(root) return root def leftRotate(self, z): y = z.right T = y.left y.left = z z.right = T # Update heights z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) return y def rightRotate(self, z): y = z.left T = y.right y.right = z z.left = T # Update heights z.height = 1 + max(self.getHeight(z.left), self.getHeight(z.right)) y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right)) return y def getHeight(self, root): if not root: return 0 return root.height def getBalance(self, root): if not root: return 0 return self.getHeight(root.left) - self.getHeight(root.right) ``` {% endcode %} #### Deletion 每次删除节点，先按普通二叉树的 deletion 方式删除，若树中所有节点都满足 AVL Tree 的规定，则删除完毕；若树中有节点不满足 AVL Tree 的规定，则根据情况作出相应的调整。可能出现的情况有 4 种，与 insertion 中的 4 种情况相同，代码实现如下： ```python class AVLTree(object): def delete(self, root, key): # Step 1 - Perform standard BST delete if not root: return root elif key < root.val: root.left = self.delete(root.left, key) elif key > root.val: root.right = self.delete(root.right, key) else: if root.left is None: tmp = root.right root = None return tmp elif root.right is None: tmp = root.left root = None return tmp tmp = self.getMinValueNode(root.right) root.val = tmp.val root.right = self.delete(root.right, tmp.val) # If the tree has only one node, simply return it if root is None: return root # Step 2 - Update the height of the ancestor node root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right)) # Step 3 - Get the balance factor balance = self.getBalance(root) # Step 4 - If the node is unbalanced, # then try out the 4 cases # Case 1 - Left Left if balance > 1 and self.getBalance(root.left) >= 0: return self.rightRotate(root) # Case 2 - Right Right if balance < -1 and self.getBalance(root.right) <= 0: return self.leftRotate(root) # Case 3 - Left Right if balance > 1 and self.getBalance(root.left) < 0: root.left = self.leftRotate(root.left) return self.rightRotate(root) # Case 4 - Right Left if balance < -1 and self.getBalance(root.right) > 0: root.right = self.rightRotate(root.right) return self.leftRotate(root) return root ``` ## Red-Black Tree Red-Black Tree 与 AVL 一样是自平衡二叉搜索树（self-balancing BST），它的结构要求： * 每个 node 都有一种颜色，红或者黑 * root node 永远是黑色 * 不能出现相邻的红色 nodes，即一个红色 node 的 parent 和 child 都必须是黑色 * 从任意 node 出发到所有 leaf node 的路径上包含的黑色 nodes 数量相等 一棵典型的 Red-Black Tree 举例如下： ![](/files/-La-YZ4xSlB6kgE-LBVe) Red-Black Tree 提出的原因与 AVL Tree 相同，都在于解决普通二叉树可能出现的降格问题，保证在二叉树中的搜索、插入、删除操作的复杂度都能控制在 $$O(logn)$$ 的范围内。 它与 AVL Tree 相比： AVL Tree 在 insert 和 delete 操作中会出现更多的 rotations，因此如果应用的 insert 和 delete 操作频繁，则 Red-Black Tree 更合适；若应用的 search 操作较多，insert 和 delete 操作较少，则 AVL Tree 更合适。 值得注意的是： * 一棵只含黑色 nodes 的树有可能是 Red-Black Tree，但它必须是完美平衡树（Perfect Balanced Tree） * 存在一棵 Red-Black Tree 不满足 AVL Tree 的性质，如上图中的树 ### Operations * Insertion * Deletion #### Insertion 略 #### Deletion 略 ## B Tree B Tree 是自平衡搜索树 (self-balancing search tree)，与 AVL Tree 以及 Red-Black Tree 不同，它不是二叉搜索树，它的使用场景主要在于整棵树无法一次性载入到内存中的场景，当数据需要在 memory 与 disk 之间传输时，各个操作的时间瓶颈就出现在了 disk I/O 上。因此，B Tree 的设计思想是尽可能地矮，使得通往目标 node 的路径尽可能短，从而减少 disk I/O 次数。通常 B Tree 的每个 node 大小为一个 page/block。 B Tree 的主要性质有： * 所有的 leaf nodes 都在同一 level * B Tree 的类型由 minimum degree --- t 来定义，t 的取值取决于 page/block 大小 * 除 root node 外的 nodes 都至少包含 k-1 个 keys，root node 至少包含 1 个 key * 所有 nodes 至多包含 2t - 1 个 keys * 每个 node 的 children 数量比 keys 数量多 1 * 一个 node 内部的所有 keys 按升序排列，在 k1 与 k2 之间的所有 keys 都包含在 k1、k2 之间的 child node 中 B Tree 的所有操作复杂度都为 $$O(logn)$$ 一棵典型的 B Tree 如下图所示： ![](/files/-La-dLVyLVE5Y6van3mr) ### Operations * Search * Traverse * Insertion * Deletion #### Search 与其它搜索树的 search 操作类似，递归地从 root node 开始往下搜索，找到合适的 child node，若发现相应的 key 则返回结果，若知道 leaf node 都没找到， 则返回 NULL。 #### Traverse traverse 与 inorder traversal 类似，从左下角的 leaf node 开始，inorder traverse 所有 node。 #### Insertion 与 BST 类似，从 root node 开始往下搜索，直到 leaf nodes 位置，在路径上每遇到一个 node，都先检查该 node 是否已经 full，若是，则先将其分裂成两个 nodes： 1. 初始化 x 为 root 2. 当 x 不是 leaf node 时 a. 找到 x 中与 key 对应的 child，记为 y b. 如果 y 不满，则修改 x 为 y c. 如果 y 已满，则将 y 分裂，根据 key 的大小将 x 修改为 y 分裂后的其中一个 node 3. 循环执行第 2 步，直到 x 为 leaf 为止，这时 x 肯定有足够的空间，直接插入 key 即可 这种实现采用主动分裂的策略，但有可能做出不必要的分裂操作。 #### Deletion deletion 操作比较复杂，考虑的情况也比较多，有可能需要： * 直接删除 * parent 中的某 key 被删除后拆借 child 中的 key * parent 中的某 key 被删除后合并 children 一些可能性如下图所示： ![](/files/-La-ltjK06Op9-eqZgta) ![](/files/-La-m14vocUA0atnqDKf) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://zhenghe.gitbook.io/open-courses/mit-6.006/self-balancing-tree.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.