# Self-Balancing Tree

提纲：

* AVL Tree
* Red-black Tree
* B Tree
* B+ Tree

## AVL Tree

AVL Tree 是一种自平衡二叉搜索树（self-balancing BST)，数中任意节点的左子树与右子树的高度差小于或等于 1，举例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_zz8bbqb-PxK0nH8_B%2F-La--H51QthdyAGCAOau%2FScreen%20Shot%202019-03-15%20at%202.19.04%20PM.jpg?alt=media\&token=f613cb12-7afd-4be6-9ba0-d84123c537a4)

返例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_zz8bbqb-PxK0nH8_B%2F-La--P0j-vUjcYSKS5PL%2FScreen%20Shot%202019-03-15%20at%202.19.36%20PM.jpg?alt=media\&token=9e43c5ad-8afd-47c0-8892-55973be43262)

图中节点 8 的左子树高度为 3，右子树高度为 1，差为 2。

AVL 提出的原因在于解决普通二叉树可能出现的降格问题，保证在二叉树中的搜索、插入、删除操作的复杂度都能控制在 $$O(logn)$$ 的范围内。

### Operations

* Insertion
* Deletion

#### Insertion

每次插入新节点，先按普通二叉树的 insertion 方式插入，若树中所有节点都满足 AVL Tree 的规定，则插入完毕；若树中有节点不满足 AVL Tree 的规定，则根据情况作出相应的调整。可能出现的情况有 4 种：

i) left - left：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_zz8bbqb-PxK0nH8_B%2F-La-1C3tCus6YoyfEpX5%2FScreen%20Shot%202019-03-15%20at%202.27.27%20PM.jpg?alt=media\&token=4d8cb07a-0015-4d58-b41e-fcc54491b15e)

ii) left - right:

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_zz8bbqb-PxK0nH8_B%2F-La-1NZehxDnfrhEC2-a%2FScreen%20Shot%202019-03-15%20at%202.28.15%20PM.jpg?alt=media\&token=8030a164-923a-4479-acad-6813190324df)

iii) right - right:

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_zz8bbqb-PxK0nH8_B%2F-La-1UeiiAQgey5amPFn%2FScreen%20Shot%202019-03-15%20at%202.28.44%20PM.jpg?alt=media\&token=9f2e297b-a0d8-44e9-b925-c847b5527215)

iv) right - left:

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_zz8bbqb-PxK0nH8_B%2F-La-1bs4k6upsqlAqz-P%2FScreen%20Shot%202019-03-15%20at%202.29.17%20PM.jpg?alt=media\&token=b88364bf-5491-4f3a-a4c7-fad2c5276cf2)

代码实现如下：

{% 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 举例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La-HwdIOF0gu19X0Tqg%2F-La-YZ4xSlB6kgE-LBVe%2FScreen%20Shot%202019-03-15%20at%204.53.11%20PM.jpg?alt=media\&token=04a31568-c5ca-4179-94c4-50046544ec33)

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)$$&#x20;

一棵典型的 B Tree 如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La-HwdIOF0gu19X0Tqg%2F-La-dLVyLVE5Y6van3mr%2FScreen%20Shot%202019-03-15%20at%205.18.29%20PM.jpg?alt=media\&token=e823e17e-0ddc-4960-aaec-f5a3515fdcc4)

### 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

一些可能性如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La-HwdIOF0gu19X0Tqg%2F-La-ltjK06Op9-eqZgta%2FScreen%20Shot%202019-03-15%20at%205.55.50%20PM.jpg?alt=media\&token=43c06abe-46cd-47f9-9ca3-828a79af20f4)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-La-HwdIOF0gu19X0Tqg%2F-La-m14vocUA0atnqDKf%2FScreen%20Shot%202019-03-15%20at%205.56.25%20PM.jpg?alt=media\&token=c8ad6a43-d084-4a42-bc19-e9b738c9dd68)