数据结构与算法Python版平衡二叉查找树AVL

文章目录

一、平衡二叉查找树
二、AVL树测试
三、AVL树-算法分析

一、平衡二叉查找树

平衡二叉查找树-AVL树的定义

AVL树：在key插入时一直保持平衡的二叉查找树。
可以利用AVL树实现抽象数据类型映射Map。与二叉查找树相比，AVL树基本上与二叉查找树的实现相同，不同在于生成与维护过程。
平衡因子balance factor：根据节点的左右子树的高度来定义，等于左子树的高度减去右子树的高度。
- 如果平衡因子大于0，称为“左重left-heavy”，
- 如果平衡因子小于0，称为“右重right-heavy”
- 如果平衡因子等于0，称为平衡
如果一个二叉查找树中每个节点的平衡因子都在-1，0，1之间，则把这个二叉查找树称为平衡树
AVL树的搜索时间复杂度为O(log2n)

AVL树的Python实现

_put方法：AVL树同时也是二叉查找树，所以新key必定以叶节点形式插入到AVL树中。插入一个新key后，更新着其父节点到根节点的平衡因子，对平衡因子大于或小于1的节点进行重新平衡
rebalance重新平衡方法：将不平衡的子树进行旋转rotation，右重子树进行左旋转，左重子树进行右旋转。以右重子树进行左旋转为例，分两种情况：
- 情况一：将右子节点B提升为子树的根，将旧根节点A作为新根节点B的左子节点。如果新根节点B原来有左子节点，则将此节点设置为A的右子节点（A的右子节点一定有空）。
- 情况二：在左旋转之前检查右子节点的因子。如果右子节点“左重”的话，先对它进行右旋转，再实施原来的左旋转

from my_tree import TreeNode, BinarySearchTreeclass AVLNode(TreeNode):def __init__(self, key, val, l_child=None, r_child=None, parent=None, b_factor=0):self.key = keyself.val = valself.l_child: AVLNode = l_childself.r_child: AVLNode = r_childself.parent: AVLNode = parentself.b_factor = b_factorclass AVLTree(BinarySearchTree):def put(self, key, val):"""插入key val，构造BST"""# 如果树不为空时，调用_put()插入到BST；否则成为BST的根if self.root:self._put(key, val, self.root)else:self.root = AVLNode(key, val)self.size += 1def _put(self, key, val, cur_node: TreeNode):# 如果key比currentNode小，那么_put到左子树；否则，_put到左子树。if key < cur_node.key:if cur_node.has_l_child():self._put(key, val, cur_node.l_child)else:cur_node.l_child = AVLNode(key, val, parent=cur_node)# 增加：调整因子self.update_balance(cur_node.l_child)else:if cur_node.has_r_child():self._put(key, val, cur_node.r_child)else:cur_node.r_child = AVLNode(key, val, parent=cur_node)# 增加：调整因子self.update_balance(cur_node.r_child)def update_balance(self, node: AVLNode):if node.b_factor > 1 or node.b_factor < -1:# 重新平衡self.re_balance(node)returnif node.parent != None:if node.is_l_child():node.parent.b_factor += 1elif node.is_r_child():node.parent.b_factor -= 1# 递归调用：调整父节点因子if node.parent.b_factor != 0:self.update_balance(node.parent)def re_balance(self, node: AVLNode):if node.b_factor < 0:  # 右重需要左旋if node.r_child.b_factor > 0:self.rotate_right(node.r_child)  # 右子节点先右旋self.rotate_left(node)else:self.rotate_left(node)elif node.b_factor > 0:if node.l_child.b_factor < 0:self.rotate_left(node.l_child)self.rotate_right(node)else:self.rotate_right(node)def rotate_left(self, rot_root: AVLNode):new_root = rot_root.r_childrot_root.r_child = new_root.l_childif new_root.l_child != None:new_root.l_child.parent = rot_rootnew_root.parent = rot_root.parentif rot_root.is_root():self.root = new_rootelse:if rot_root.is_l_child():rot_root.parent.l_child = new_rootelse:rot_root.parent.r_child = new_rootnew_root.l_child = rot_rootrot_root.parent = new_rootrot_root.b_factor = rot_root.b_factor + 1 - min(new_root.b_factor, 0)new_root.b_factor = new_root.b_factor + 1 + max(rot_root.b_factor, 0)def rotate_right(self, rot_root: AVLNode):new_root = rot_root.l_childrot_root.l_child = new_root.r_childif new_root.r_child != None:new_root.r_child.parent = rot_rootnew_root.parent = rot_root.parentif rot_root.is_root():self.root = new_rootelse:if rot_root.is_r_child():rot_root.parent.r_child = new_rootelse:rot_root.parent.r_child = new_rootnew_root.r_child = rot_rootrot_root.parent = new_rootrot_root.b_factor = rot_root.b_factor + 1 - min(new_root.b_factor, 0)new_root.b_factor = new_root.b_factor + 1 + max(rot_root.b_factor, 0)

二、AVL树测试

依次将下面6个节点插入到平衡二叉查找树，查看平衡二叉查找树状态

在这里插入图片描述

删除节点26，查看平衡二叉查找树状态

在这里插入图片描述

参考资料：AVL树在线演示。在线演示网站，在删除节点时使用的是中序前驱（左子树中的最大节点），所示演示结果与输出结果有差异。

bst = AVLTree()
bst[17] = "tiger"
bst[26] = "dog"
bst[31] = "cow"
bst[54] = "cat"
bst[93] = "lion"
bst[77] = "bird"bst.display_tree()
print(bst[26])
del bst[26]
print(bst[26])
bst.display_tree()### 输出结果
54 26 17 31 93 77 
dog
None
54 31 17 93 77

三、AVL树-算法分析

AVL树始终维持平衡，get方法始终保持O(log2n)最佳性能
AVL树的put方法分为两个部分：
- 需要插入的新节点是叶节点，更新其所有父节点和祖先节点的代价最多为O(log2n)。
- 如果插入的新节点引发了不平衡，重新平衡最多需要2次旋转，但旋转的代价与问题规模无关，是常数O(1)
- put方法的时间复杂度还是O(log2n)

映射的实现方法小结

抽象数据类型映射Map，可以采用多种数据结构和算法来实现，时间复杂度数量级如下

操作类型	有序表	散列表	二叉查找树	AVL树
put	O(n)	O(1) -> O(n)	O(log2n) -> O(n)	O(log2n)
get	O(log2n)	O(1) -> O(n)	O(log2n) -> O(n)	O(log2n)
in	O(log2n)	O(1) -> O(n)	O(log2n) -> O(n)	O(log2n)
del	O(n)	O(1) -> O(n)	O(log2n) -> O(n)	O(log2n)