本文包括：

1. 旋转示例图
2. 基于balance factor来计算新的balance factor（比基于height）
3. 实现代码

深色字体为 height
红色字体为 两个儿子节点的 height 之差
通过下面5个图，可以

1. 很容易分情况把代码写出来
2. 知道通过旋转后整个子树的高度变化（在插入删除的时候用于判断是否需要对父亲节点进行旋转操作）

2, 1 2, 0 2, -1, 0 2, -1, 1 2, -1, -1

剩下的5种情况，可以由上述5种情况通过镜面反转而获得。

旋转过程中 balance factor 的变化推导

右旋示例

1. 如图所示，定义 为高度函数，如 ，定义 为获取AVL的节点的balance factor 函数，如。
2. 定义旋转后的 节点为 , 节点为 。
3. 显然， 和 成立。
4. 那么，
5. 因此可以通过 和 求出，
6. 又因为 。
7. 那么，。
8. 因此，，通过第5步算出的 可以计算出 。
9. 至此， 与 均已通过 和 计算得出。

同理左旋。

AVL python 实现

class TreeNode:
    
    def __init__(self, key, value, left_child=None, right_child=None, parent=None):
        self.key = key
        self.value = value
        self.parent = parent
        self.left_child = left_child
        self.right_child = right_child
        self.balance_factor = 0
    
    def has_left_child(self):
        return self.left_child is not None
    
    def has_right_child(self):
        return self.right_child is not None

    def is_right_child(self):
        return self.parent is not None and self.parent.right_child is self
    
    def is_left_child(self):
        return self.parent is not None and self.parent.left_child is self
    
    def is_root(self):
        return self.parent is None


class BinarySearchTree:
    
    def __init__(self):
        self.root = None
        
    def insert(self, key, value=None):
        if self.root is None:
            self.root = TreeNode(key, value)
        else:
            self._put(key, value, self.root)
    
    def contains(self, key):
        return self._get(key, self.root) is not None
    
    def delete(self, key):
        cur = self._get(key, self.root)
        
        if cur.has_left_child() and cur.has_right_child():
            new_cur = cur.left_child
            while new_cur.has_right_child():
                new_cur = new_cur.right_child
            cur.key, cur.value = new_cur.key, new_cur.value
            cur = new_cur
        
        if cur.is_root():
            self.root = cur.left_child if cur.has_left_child() else cur.right_child
            if self.root:
                self.root.parent = None
        else:
            if cur.is_left_child():
                cur.parent.left_child = cur.right_child if cur.has_right_child() else cur.left_child
                if cur.parent.left_child:
                    cur.parent.left_child.parent = cur.parent
                cur.parent.balance_factor -= 1
            else:
                cur.parent.right_child = cur.right_child if cur.has_right_child() else cur.left_child
                if cur.parent.right_child:
                    cur.parent.right_child.parent = cur.parent
                cur.parent.balance_factor += 1
            self._update_balance(cur.parent, -1)
        
    def _get(self, key, current_node):
        if current_node is None:
            return None
        if key == current_node.key:
            return current_node
        return self._get(key, current_node.left_child) if key < current_node.key else self._get(key, current_node.right_child)
    
    def _put(self,key,value,current_node):
        if key < current_node.key:
            if current_node.has_left_child():
                self._put(key,value,current_node.left_child)
            else:
                current_node.left_child = TreeNode(key,value,parent=current_node)
                self._update_balance(current_node.left_child)
        else:
            if current_node.has_right_child():
                self._put(key,value,current_node.right_child)
            else:
                current_node.right_child = TreeNode(key,value,parent=current_node)
                self._update_balance(current_node.right_child)

    def _update_balance(self, node, inc=1):
        if node.balance_factor > 1 or node.balance_factor < -1:
            self._rebalance(node)
            return
        if not node.is_root():
            if node.is_left_child():
                node.parent.balance_factor += inc
            elif node.is_right_child():
                node.parent.balance_factor -= inc

            if node.parent.balance_factor != 0:
                self._update_balance(node.parent)
    
    def _rotate_left(self,rot_root):
        new_root = rot_root.right_child
        rot_root.right_child = new_root.left_child
        if new_root.has_left_child():
            new_root.left_child.parent = rot_root
        new_root.parent = rot_root.parent
        if rot_root.is_root():
            self.root = new_root
        else:
            if rot_root.is_left_child():
                rot_root.parent.left_child = new_root
            else:
                rot_root.parent.right_child = new_root
        new_root.left_child = rot_root
        rot_root.parent = new_root
        rot_root.balance_factor = rot_root.balance_factor + 1 - min(new_root.balance_factor, 0)
        new_root.balance_factor = new_root.balance_factor + 1 + max(rot_root.balance_factor, 0)
    
    def _rotate_right(self, rot_root):
        new_root = rot_root.left_child
        rot_root.left_child = new_root.right_child
        if new_root.has_right_child():
            new_root.right_child.parent = rot_root
        new_root.parent = rot_root.parent
        if rot_root.is_root():
            self.root = new_root
        else:
            if rot_root.is_left_child():
                rot_root.parent.left_child = new_root
            else:
                rot_root.parent.right_child = new_root
        new_root.right_child = rot_root
        rot_root.parent = new_root
        rot_root.balance_factor = rot_root.balance_factor - 1 - max(new_root.balance_factor, 0)
        new_root.balance_factor = new_root.balance_factor - 1 + min(rot_root.balance_factor, 0)
        
    def _rebalance(self,node):
        if node.balance_factor < 0:
            if node.right_child.balance_factor > 0:
                self._rotate_right(node.right_child)
                self._rotate_left(node)
            else:
                self._rotate_left(node)
        elif node.balance_factor > 0:
            if node.left_child.balance_factor < 0:
                self._rotate_left(node.left_child)
                self._rotate_right(node)
            else:
                self._rotate_right(node)