AVL 平衡树和树旋转
目录
1 AVL平衡二叉树
AVL（Adelson-Velskii & Landis）树是一种带有平衡条件的，一棵AVL树其实是一棵左子树和右子树高度最多差1的二叉。一棵树的不平衡主要是由于插入和删除的过程中产生的，此时则需要使用旋转来对AVL树进行平衡。
AVL Tree: 0 _____|_____ | | 0 0 |___ ___|___ | | | 0 0 0 |__ | 0
插入引起不平衡主要有以下四种情况：
Insert unbalance: 1: | 2: | 3: | 4: A(2) | A(2) | A(2) | A(2) __| | __| | |__ | |__ | | | | | | | B(1) | B(1) | B(1) | B(1) __| | |__ | __| | |__ | | | | | | | ---- | ---- | ---- | ---- |X(0)| | |X(0)| | |X(0)| | |X(0)| ---- | ---- | ---- | ----
删除引起不平衡主要有以下四种情况：
Delete unbalance: 1: | 2: | 3: | 4: A(2) | A(2) | A(2) | A(2) __|__ | __|__ | __|__ | __|__ | | | | | | | | | | | B(1) ---- | B(1) ---- | ---- B(1) | ---- B(1) __| |X(0)| | |__ |X(0)| | |X(0)| __| | |X(0)| |__ | ---- | | ---- | ---- | | ---- | C(0) | C(0) | C(0) | C(0)
2. 树旋转
对于上面的不平衡情况，可以分别采用以下的树旋转方式解决，
2.1 向左单旋转
适用于处理上面插入/删除引起的不平衡情况1，
下图中K2两个子树节点相差高度等于2，产生了不平衡，因此需要使用单旋转处理，
在向左单旋转时，若K1有右子树，则转变为K2的左子树。
K2(2) K1(1) __|__ ____|_____ | | | | K1(1) None(-1) --------> X(0) K2(1) __|__ __|__ | | | | X(0) Y(0) Y(0) None(-1)
2.2 向右单旋转
适用于处理上面插入/删除引起的不平衡情况4，
在向右单旋转时，若K1有左子树，则转变为K2的右子树。
K2(2) K1(2) __|__ ____|_____ | | | | (-1)None K1(1) --------> K2(1) Y(0) __|__ __|__ | | | | X(0) Y(0) (-1)None X(0)
2.3 右左双旋转
适用于处理上面插入/删除引起的不平衡情况2，
首先对K1进行一次向右单旋转，再对K3进行一次向左单旋转，
K3(3) K3(3) K2(2) __|__ __|__ _____|_____ | | right | | left | | K1(2) D(0) --------> K2(2) D(0) --------> K1(1) K3(1) __|__ __|__ __|__ __|__ | | | | | | | | A(0) K2(1) K1(1) C(0) A(0) B(0) C(0) D(0) __|__ __|__ | | | | B(0) C(0) A(0) B(0)
2.4 左右双旋转
适用于处理上面插入/删除引起的不平衡情况3，
首先对K1进行一次向左单旋转，再对K3进行一次向右单旋转，
K3(3) K3(3) K2(2) __|__ __|__ _____|_____ | | left | | right | | D(0) K1(2) --------> D(0) K2(2) --------> K3(1) K1(1) __|__ __|__ __|__ __|__ | | | | | | | | K2(1) A(0) C(0) K1(1) D(0) C(0) B(0) A(0) __|__ __|__ | | | | C(0) B(0) B(0) A(0)
3 Python代码实现
下面利用Python实现AVL树，以及树的旋转操作，
完整代码
1 from search_tree import SearchTree 2 3 4 class AvlNode: 5 def __init__(self, val=None, lef=None, rgt=None, hgt=0): 6 self.value = val 7 self.left = lef 8 self.right = rgt 9 self.height = hgt 10 11 def __str__(self): 12 return str(self.value) 13 14 15 class AvlTree(SearchTree): 16 """ 17 AVL Tree: 18 0 19 _____|_____ 20 | | 21 0 0 22 |___ ___|___ 23 | | | 24 0 0 0 25 |__ 26 | 27 0 28 Insert unbalance: 29 1: | 2: | 3: | 4: 30 A(2) | A(2) | A(2) | A(2) 31 __| | __| | |__ | |__ 32 | | | | | | | 33 B(1) | B(1) | B(1) | B(1) 34 __| | |__ | __| | |__ 35 | | | | | | | 36 ---- | ---- | ---- | ---- 37 |X(0)| | |X(0)| | |X(0)| | |X(0)| 38 ---- | ---- | ---- | ---- 39 40 Delete unbalance: 41 1: | 2: | 3: | 4: 42 A(2) | A(2) | A(2) | A(2) 43 __|__ | __|__ | __|__ | __|__ 44 | | | | | | | | | | | 45 B(1) ---- | B(1) ---- | ---- B(1) | ---- B(1) 46 __| |X(0)| | |__ |X(0)| | |X(0)| __| | |X(0)| |__ 47 | ---- | | ---- | ---- | | ---- | 48 C(0) | C(0) | C(0) | C(0) 49 """ 50 def get_height(self, node): 51 if isinstance(node, AvlNode): 52 return node.height 53 return -1 54 55 def single_rotate_left(self, k2): 56 """ 57 K2(2) K1(1) 58 __|__ ____|_____ 59 | | | | 60 K1(1) None(-1) --------> X(0) K2(1) 61 __|__ __|__ 62 | | | | 63 X(0) Y(0) Y(0) None(-1) 64 """ 65 # Left rotate 66 k1 = k2.left 67 k2.left = k1.right 68 k1.right = k2 69 # Update height 70 k2.height = max(self.get_height(k2.left), self.get_height(k2.right)) + 1 71 k1.height = max(self.get_height(k1.left), k2.height) + 1 72 return k1 73 74 def single_rotate_right(self, k2): 75 """ 76 K2(2) K1(2) 77 __|__ ____|_____ 78 | | | | 79 (-1)None K1(1) --------> K2(1) Y(0) 80 __|__ __|__ 81 | | | | 82 X(0) Y(0) (-1)None X(0) 83 """ 84 # Right rotate 85 k1 = k2.right 86 k2.right = k1.left 87 k1.left = k2 88 # Update height 89 k2.height = max(self.get_height(k2.left), self.get_height(k2.right)) + 1 90 k1.height = max(k2.height, self.get_height(k1.right)) + 1 91 return k1 92 93 def double_rotate_left(self, k3): 94 """ 95 K3(3) K3(3) K2(2) 96 __|__ __|__ _____|_____ 97 | | right | | left | | 98 K1(2) D(0) --------> K2(2) D(0) --------> K1(1) K3(1) 99 __|__ __|__ __|__ __|__ 100 | | | | | | | | 101 A(0) K2(1) K1(1) C(0) A(0) B(0) C(0) D(0) 102 __|__ __|__ 103 | | | | 104 B(0) C(0) A(0) B(0) 105 """106 # Rotate between k1 and k2107 k3.left = self.single_rotate_right(k3.left)108 # Rotate between k3 and k2109 return self.single_rotate_left(k3)110 111 def double_rotate_right(self, k3):112 """113 K3(3) K3(3) K2(2) 114 __|__ __|__ _____|_____ 115 | | left | | right | | 116 D(0) K1(2) --------> D(0) K2(2) --------> K3(1) K1(1)117 __|__ __|__ __|__ __|__ 118 | | | | | | | | 119 K2(1) A(0) C(0) K1(1) D(0) C(0) B(0) A(0) 120 __|__ __|__ 121 | | | | 122 C(0) B(0) B(0) A(0) 123 """124 # Rotate between k1 and k2125 k3.right = self.single_rotate_left(k3.right)126 # Rotate between k3 and k2127 return self.single_rotate_right(k3)128 129 def insert(self, item):130 if self._root is None:131 self._root = AvlNode(item)132 return133 134 def _insert(item, node):135 if not node:136 return AvlNode(item)137 if item < node.value:138 node.left = _insert(item, node.left)139 if self.get_height(node.left) - self.get_height(node.right) == 2:140 if item < node.left.value: # Situation 1: left --> left141 node = self.single_rotate_left(node)142 else: # Situation 2: left --> right143 node = self.double_rotate_left(node)144 elif item > node.value:145 node.right = _insert(item, node.right)146 if self.get_height(node.right) - self.get_height(node.left) == 2:147 if item < node.right.value: # Situation 3: right --> left148 node = self.double_rotate_right(node)149 else: # Situation 4: right --> right150 node = self.single_rotate_right(node)151 else: pass152 # Update node height (if not rotated, update is necessary.)153 node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1154 return node155 self._root = _insert(item, self._root)156 157 def delete(self, item):158 if self._root is None:159 return160 161 def _delete(item, node):162 if not node: # Node no found163 # return None164 raise Exception('Element not in tree.')165 166 if item < node.value:167 node.left = _delete(item, node.left)168 # Delete left, rotate right169 if self.get_height(node.right) - self.get_height(node.left) == 2:170 if self.get_height(node.right.right) >= self.get_height(node.right.left): # Situation 4171 node = self.single_rotate_right(node)172 else: # Situation 3173 node = self.double_rotate_right(node)174 175 elif item > node.value:176 node.right = _delete(item, node.right)177 # Delete right, rotate left178 if self.get_height(node.left) - self.get_height(node.right) == 2:179 if self.get_height(node.left.left) >= self.get_height(node.left.right): # Situation 1180 node = self.single_rotate_left(node)181 else: # Situation 3182 node = self.double_rotate_left(node)183 184 else: # Node found185 if node.left and node.right:186 # Minimum node in right sub-tree has no left sub-node, can be used to make replacement187 # Find minimum node in right sub-tree188 min_node = self.find_min(node.right) 189 # Replace current node with min_node190 node.value = min_node.value191 # Delete min_node in right sub-tree192 node.right = _delete(min_node.value, node.right)193 else:194 if node.left: 195 node = node.left196 elif node.right:197 node = node.right198 else:199 node = None200 # Update node height (if not ratated, update is necessary.)201 # If node is None, height is -1 already.202 if node:203 node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1204 return node205 self._root = _delete(item, self._root)206 207 208 def test(avl):209 print('\nInit an AVL tree:')210 for i in [1, 2, 3, 4, 5, 6, 7]:211 avl.insert(i)212 avl.show()213 214 print('\nLeft single rotate:')215 avl.delete(5)216 avl.delete(7)217 avl.delete(6)218 avl.show()219 220 avl.make_empty()221 print('\nInit an AVL tree:')222 for i in [1, 2, 3, 4, 5, 6, 7]:223 avl.insert(i)224 225 print('\nRight single rotate:')226 avl.delete(1)227 avl.delete(3)228 avl.delete(2)229 avl.show()230 231 avl.make_empty()232 print('\nInit an AVL tree:')233 for i in [6, 2, 8, 1, 4, 9, 3, 5]:234 avl.insert(i)235 avl.show()236 237 print('\nRight-Left double rotate:')238 avl.delete(9)239 avl.show()240 241 avl.make_empty()242 print('\nInit an AVL tree:')243 for i in [4, 2, 8, 1, 6, 9, 5, 7]:244 avl.insert(i)245 avl.show()246 247 print('\nLeft-Right double rotate:')248 avl.delete(1)249 avl.show()250 251 if __name__ == '__main__':252 test(AvlTree()) 分段解释
首先，需要导入查找树，以及定义AVL树的节点，
1 from search_tree import SearchTree 2 3 4 class AvlNode: 5 def __init__(self, val=None, lef=None, rgt=None, hgt=0): 6 self.value = val 7 self.left = lef 8 self.right = rgt 9 self.height = hgt10 11 def __str__(self):12 return str(self.value)
接着构建一棵AVL树的类，构造方法可继承查找树，
1 class AvlTree(SearchTree): 2 """ 3 AVL Tree: 4 0 5 _____|_____ 6 | | 7 0 0 8 |___ ___|___ 9 | | |10 0 0 0 11 |__12 |13 0 14 Insert unbalance:15 1: | 2: | 3: | 4:16 A(2) | A(2) | A(2) | A(2) 17 __| | __| | |__ | |__ 18 | | | | | | | 19 B(1) | B(1) | B(1) | B(1) 20 __| | |__ | __| | |__ 21 | | | | | | | 22 ---- | ---- | ---- | ---- 23 |X(0)| | |X(0)| | |X(0)| | |X(0)| 24 ---- | ---- | ---- | ---- 25 26 Delete unbalance:27 1: | 2: | 3: | 4:28 A(2) | A(2) | A(2) | A(2) 29 __|__ | __|__ | __|__ | __|__ 30 | | | | | | | | | | | 31 B(1) ---- | B(1) ---- | ---- B(1) | ---- B(1) 32 __| |X(0)| | |__ |X(0)| | |X(0)| __| | |X(0)| |__ 33 | ---- | | ---- | ---- | | ---- | 34 C(0) | C(0) | C(0) | C(0)35 """
定义获取节点子树高度的方法，当节点为None时，返回高度为-1，
1 def get_height(self, node):2 if isinstance(node, AvlNode):3 return node.height4 return -1
定义向左的单旋转方法，旋转完成后更新高度
1 def single_rotate_left(self, k2): 2 """ 3 K2(2) K1(1) 4 __|__ ____|_____ 5 | | | | 6 K1(1) None(-1) --------> X(0) K2(1) 7 __|__ __|__ 8 | | | | 9 X(0) Y(0) Y(0) None(-1)10 """11 # Left rotate12 k1 = k2.left13 k2.left = k1.right14 k1.right = k215 # Update height16 k2.height = max(self.get_height(k2.left), self.get_height(k2.right)) + 117 k1.height = max(self.get_height(k1.left), k2.height) + 118 return k1
定义向右的单旋转方法，旋转完成后更新高度
1 def single_rotate_right(self, k2): 2 """ 3 K2(2) K1(2) 4 __|__ ____|_____ 5 | | | | 6 (-1)None K1(1) --------> K2(1) Y(0) 7 __|__ __|__ 8 | | | | 9 X(0) Y(0) (-1)None X(0)10 """11 # Right rotate12 k1 = k2.right13 k2.right = k1.left14 k1.left = k215 # Update height16 k2.height = max(self.get_height(k2.left), self.get_height(k2.right)) + 117 k1.height = max(k2.height, self.get_height(k1.right)) + 118 return k1
定义先右后左的双旋转方法，旋转完成后更新高度
1 def double_rotate_left(self, k3): 2 """ 3 K3(3) K3(3) K2(2) 4 __|__ __|__ _____|_____ 5 | | right | | left | | 6 K1(2) D(0) --------> K2(2) D(0) --------> K1(1) K3(1) 7 __|__ __|__ __|__ __|__ 8 | | | | | | | | 9 A(0) K2(1) K1(1) C(0) A(0) B(0) C(0) D(0) 10 __|__ __|__ 11 | | | | 12 B(0) C(0) A(0) B(0) 13 """14 # Rotate between k1 and k215 k3.left = self.single_rotate_right(k3.left)16 # Rotate between k3 and k217 return self.single_rotate_left(k3)
定义先左后右的双旋转方法，旋转完成后更新高度
1 def double_rotate_right(self, k3): 2 """ 3 K3(3) K3(3) K2(2) 4 __|__ __|__ _____|_____ 5 | | left | | right | | 6 D(0) K1(2) --------> D(0) K2(2) --------> K3(1) K1(1) 7 __|__ __|__ __|__ __|__ 8 | | | | | | | | 9 K2(1) A(0) C(0) K1(1) D(0) C(0) B(0) A(0) 10 __|__ __|__ 11 | | | | 12 C(0) B(0) B(0) A(0) 13 """14 # Rotate between k1 and k215 k3.right = self.single_rotate_left(k3.right)16 # Rotate between k3 and k217 return self.single_rotate_right(k3)
定义插入方法，进行递归插入，每次插入后都需要检测子树高度来决定是否需要对树进行平衡旋转，最后进行高度更新，若经过旋转则此时高度已经被更新。
1 def insert(self, item): 2 if self._root is None: 3 self._root = AvlNode(item) 4 return 5 6 def _insert(item, node): 7 if not node: 8 return AvlNode(item) 9 if item < node.value:10 node.left = _insert(item, node.left)11 if self.get_height(node.left) - self.get_height(node.right) == 2:12 if item < node.left.value: # Situation 1: left --> left13 node = self.single_rotate_left(node)14 else: # Situation 2: left --> right15 node = self.double_rotate_left(node)16 elif item > node.value:17 node.right = _insert(item, node.right)18 if self.get_height(node.right) - self.get_height(node.left) == 2:19 if item < node.right.value: # Situation 3: right --> left20 node = self.double_rotate_right(node)21 else: # Situation 4: right --> right22 node = self.single_rotate_right(node)23 else: pass24 # Update node height (if not rotated, update is necessary.)25 node.height = max(self.get_height(node.left), self.get_height(node.right)) + 126 return node27 self._root = _insert(item, self._root)
定义删除方法，进行递归删除，删除后检测是否需要平衡旋转，并选择旋转的方式，删除完成根据需要进行高度更新。
1 def delete(self, item): 2 if self._root is None: 3 return 4 5 def _delete(item, node): 6 if not node: # Node no found 7 # return None 8 raise Exception('Element not in tree.') 9 10 if item < node.value:11 node.left = _delete(item, node.left)12 # Delete left, rotate right13 if self.get_height(node.right) - self.get_height(node.left) == 2:14 if self.get_height(node.right.right) >= self.get_height(node.right.left): # Situation 415 node = self.single_rotate_right(node)16 else: # Situation 317 node = self.double_rotate_right(node)18 19 elif item > node.value:20 node.right = _delete(item, node.right)21 # Delete right, rotate left22 if self.get_height(node.left) - self.get_height(node.right) == 2:23 if self.get_height(node.left.left) >= self.get_height(node.left.right): # Situation 124 node = self.single_rotate_left(node)25 else: # Situation 326 node = self.double_rotate_left(node)27 28 else: # Node found29 if node.left and node.right:30 # Minimum node in right sub-tree has no left sub-node, can be used to make replacement31 # Find minimum node in right sub-tree32 min_node = self.find_min(node.right) 33 # Replace current node with min_node34 node.value = min_node.value35 # Delete min_node in right sub-tree36 node.right = _delete(min_node.value, node.right)37 else:38 if node.left: 39 node = node.left40 elif node.right:41 node = node.right42 else:43 node = None44 # Update node height (if not ratated, update is necessary.)45 # If node is None, height is -1 already.46 if node:47 node.height = max(self.get_height(node.left), self.get_height(node.right)) + 148 return node49 self._root = _delete(item, self._root) 最后定义一个测试函数，用于测试AVL树的功能。
首先初始化一棵树
1 def test(avl):2 print('\nInit an AVL tree:')3 for i in [1, 2, 3, 4, 5, 6, 7]:4 avl.insert(i)5 avl.show() 得到结果
Init an AVL tree:4 | 4 2 | __|__ 1 | | | 3 | 2 6 6 | _|_ _|_ 5 | | | | | 7 | 1 3 5 7
接着尝试删除5, 6, 7三个节点，完成一个向左单旋转，
1 print('\nLeft single rotate:')2 avl.delete(5)3 avl.delete(7)4 avl.delete(6)5 avl.show() 得到结果，可以看到，此时AVL树已经完成了一个向左的平衡旋转
Left single rotate:2 | 2 1 | __|__ 4 | | | 3 | 1 4 | _| | | | 3
清空树并再次初始化树后
尝试删除1, 2, 3三个节点，完成一个向右单旋转，
1 print('\nDelete element from tree:')2 avl.delete(1)3 avl.delete(3)4 avl.delete(2)5 avl.show() 得到结果，可以看到，此时AVL树已经完成了一个向右的平衡旋转
Delete element from tree:6 | 6 4 | __|__ 5 | | | 7 | 4 7 | |_ | | | 5
再次清空树，并建立一棵新的树
1 avl.make_empty()2 print('\nInit an AVL tree:')3 for i in [6, 2, 8, 1, 4, 9, 3, 5]:4 avl.insert(i)5 avl.show() 得到结果
Init an AVL tree:6 | 6 2 | __|__ 1 | | | 4 | 2 8 3 | _|_ |_ 5 | | | | 8 | 1 4 9 9 | _|_ | | | | 3 5
此时尝试删除节点9，完成一个右左双旋转
1 print('\nRight-Left double rotate:')2 avl.delete(9)3 avl.show() 得到结果
Right-Left double rotate:4 | 4 2 | __|__ 1 | | | 3 | 2 6 6 | _|_ _|_ 5 | | | | | 8 | 1 3 5 8
最后再次清空树建立一棵新树，
1 avl.make_empty()2 print('\nInit an AVL tree:')3 for i in [4, 2, 8, 1, 6, 9, 5, 7]:4 avl.insert(i)5 avl.show() 显示结果如下
Init an AVL tree:4 | 4 2 | __|__ 1 | | | 8 | 2 8 6 | _| _|_ 5 | | | | 7 | 1 6 9 9 | _|_ | | | | 5 7
此时尝试删除节点1，造成不平衡完成一个左右双旋转
1 print('\nLeft-Right double rotate:')2 avl.delete(1)3 avl.show() 得到结果
Left-Right double rotate:6 | 6 4 | __|__ 2 | | | 5 | 4 8 8 | _|_ _|_ 7 | | | | | 9 | 2 5 7 9
相关阅读
1.
2.