AVL Tree 是一种自平衡二叉搜索树（self-balancing BST)，数中任意节点的左子树与右子树的高度差小于或等于 1，举例如下：
返例如下：
图中节点 8 的左子树高度为 3，右子树高度为 1，差为 2。
Operations
Insertion
Deletion
Insertion
每次插入新节点，先按普通二叉树的 insertion 方式插入，若树中所有节点都满足 AVL Tree 的规定，则插入完毕；若树中有节点不满足 AVL Tree 的规定，则根据情况作出相应的调整。可能出现的情况有 4 种：
i) left - left：
ii) left - right:
iii) right - right:
iv) right - left:
代码实现如下：
AVL.py
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)
Deletion
每次删除节点，先按普通二叉树的 deletion 方式删除，若树中所有节点都满足 AVL Tree 的规定，则删除完毕；若树中有节点不满足 AVL Tree 的规定，则根据情况作出相应的调整。可能出现的情况有 4 种，与 insertion 中的 4 种情况相同，代码实现如下：
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），它的结构要求：
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 大小
