Python与数据结构[3] -> 树/Tree[2] -> AVL 平衡树和树旋转的 Python 实现
2024-08-31 13:02:03
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树，以及树的旋转操作，
完整代码
from search_tree import SearchTree class AvlNode:
def __init__(self, val=None, lef=None, rgt=None, hgt=0):
self.value = val
self.left = lef
self.right = rgt
self.height = hgt def __str__(self):
return str(self.value) class AvlTree(SearchTree):
"""
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)
"""
def get_height(self, node):
if isinstance(node, AvlNode):
return node.height
return -1 def single_rotate_left(self, k2):
"""
K2(2) K1(1)
__|__ ____|_____
| | | |
K1(1) None(-1) --------> X(0) K2(1)
__|__ __|__
| | | |
X(0) Y(0) Y(0) None(-1)
"""
# Left rotate
k1 = k2.left
k2.left = k1.right
k1.right = k2
# Update height
k2.height = max(self.get_height(k2.left), self.get_height(k2.right)) + 1
k1.height = max(self.get_height(k1.left), k2.height) + 1
return k1 def single_rotate_right(self, k2):
"""
K2(2) K1(2)
__|__ ____|_____
| | | |
(-1)None K1(1) --------> K2(1) Y(0)
__|__ __|__
| | | |
X(0) Y(0) (-1)None X(0)
"""
# Right rotate
k1 = k2.right
k2.right = k1.left
k1.left = k2
# Update height
k2.height = max(self.get_height(k2.left), self.get_height(k2.right)) + 1
k1.height = max(k2.height, self.get_height(k1.right)) + 1
return k1 def double_rotate_left(self, 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)
"""
# Rotate between k1 and k2
k3.left = self.single_rotate_right(k3.left)
# Rotate between k3 and k2
return self.single_rotate_left(k3) def double_rotate_right(self, 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)
"""
# Rotate between k1 and k2
k3.right = self.single_rotate_left(k3.right)
# Rotate between k3 and k2
return self.single_rotate_right(k3) def insert(self, item):
if self._root is None:
self._root = AvlNode(item)
return def _insert(item, node):
if not node:
return AvlNode(item)
if item < node.value:
node.left = _insert(item, node.left)
if self.get_height(node.left) - self.get_height(node.right) == 2:
if item < node.left.value: # Situation 1: left --> left
node = self.single_rotate_left(node)
else: # Situation 2: left --> right
node = self.double_rotate_left(node)
elif item > node.value:
node.right = _insert(item, node.right)
if self.get_height(node.right) - self.get_height(node.left) == 2:
if item < node.right.value: # Situation 3: right --> left
node = self.double_rotate_right(node)
else: # Situation 4: right --> right
node = self.single_rotate_right(node)
else: pass
# Update node height (if not rotated, update is necessary.)
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
return node
self._root = _insert(item, self._root) def delete(self, item):
if self._root is None:
return def _delete(item, node):
if not node: # Node no found
# return None
raise Exception('Element not in tree.') if item < node.value:
node.left = _delete(item, node.left)
# Delete left, rotate right
if self.get_height(node.right) - self.get_height(node.left) == 2:
if self.get_height(node.right.right) >= self.get_height(node.right.left): # Situation 4
node = self.single_rotate_right(node)
else: # Situation 3
node = self.double_rotate_right(node) elif item > node.value:
node.right = _delete(item, node.right)
# Delete right, rotate left
if self.get_height(node.left) - self.get_height(node.right) == 2:
if self.get_height(node.left.left) >= self.get_height(node.left.right): # Situation 1
node = self.single_rotate_left(node)
else: # Situation 3
node = self.double_rotate_left(node) else: # Node found
if node.left and node.right:
# Minimum node in right sub-tree has no left sub-node, can be used to make replacement
# Find minimum node in right sub-tree
min_node = self.find_min(node.right)
# Replace current node with min_node
node.value = min_node.value
# Delete min_node in right sub-tree
node.right = _delete(min_node.value, node.right)
else:
if node.left:
node = node.left
elif node.right:
node = node.right
else:
node = None
# Update node height (if not ratated, update is necessary.)
# If node is None, height is -1 already.
if node:
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
return node
self._root = _delete(item, self._root) def test(avl):
print('\nInit an AVL tree:')
for i in [1, 2, 3, 4, 5, 6, 7]:
avl.insert(i)
avl.show() print('\nLeft single rotate:')
avl.delete(5)
avl.delete(7)
avl.delete(6)
avl.show() avl.make_empty()
print('\nInit an AVL tree:')
for i in [1, 2, 3, 4, 5, 6, 7]:
avl.insert(i) print('\nRight single rotate:')
avl.delete(1)
avl.delete(3)
avl.delete(2)
avl.show() avl.make_empty()
print('\nInit an AVL tree:')
for i in [6, 2, 8, 1, 4, 9, 3, 5]:
avl.insert(i)
avl.show() print('\nRight-Left double rotate:')
avl.delete(9)
avl.show() avl.make_empty()
print('\nInit an AVL tree:')
for i in [4, 2, 8, 1, 6, 9, 5, 7]:
avl.insert(i)
avl.show() print('\nLeft-Right double rotate:')
avl.delete(1)
avl.show() if __name__ == '__main__':
test(AvlTree())
分段解释
首先，需要导入查找树，以及定义AVL树的节点，
from search_tree import SearchTree class AvlNode:
def __init__(self, val=None, lef=None, rgt=None, hgt=0):
self.value = val
self.left = lef
self.right = rgt
self.height = hgt def __str__(self):
return str(self.value)
接着构建一棵AVL树的类，构造方法可继承查找树，
class AvlTree(SearchTree):
"""
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)
"""
定义获取节点子树高度的方法，当节点为None时，返回高度为-1，
def get_height(self, node):
if isinstance(node, AvlNode):
return node.height
return -1
定义向左的单旋转方法，旋转完成后更新高度
def single_rotate_left(self, k2):
"""
K2(2) K1(1)
__|__ ____|_____
| | | |
K1(1) None(-1) --------> X(0) K2(1)
__|__ __|__
| | | |
X(0) Y(0) Y(0) None(-1)
"""
# Left rotate
k1 = k2.left
k2.left = k1.right
k1.right = k2
# Update height
k2.height = max(self.get_height(k2.left), self.get_height(k2.right)) + 1
k1.height = max(self.get_height(k1.left), k2.height) + 1
return k1
定义向右的单旋转方法，旋转完成后更新高度
def single_rotate_right(self, k2):
"""
K2(2) K1(2)
__|__ ____|_____
| | | |
(-1)None K1(1) --------> K2(1) Y(0)
__|__ __|__
| | | |
X(0) Y(0) (-1)None X(0)
"""
# Right rotate
k1 = k2.right
k2.right = k1.left
k1.left = k2
# Update height
k2.height = max(self.get_height(k2.left), self.get_height(k2.right)) + 1
k1.height = max(k2.height, self.get_height(k1.right)) + 1
return k1
定义先右后左的双旋转方法，旋转完成后更新高度
def double_rotate_left(self, 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)
"""
# Rotate between k1 and k2
k3.left = self.single_rotate_right(k3.left)
# Rotate between k3 and k2
return self.single_rotate_left(k3)
定义先左后右的双旋转方法，旋转完成后更新高度
def double_rotate_right(self, 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)
"""
# Rotate between k1 and k2
k3.right = self.single_rotate_left(k3.right)
# Rotate between k3 and k2
return self.single_rotate_right(k3)
定义插入方法，进行递归插入，每次插入后都需要检测子树高度来决定是否需要对树进行平衡旋转，最后进行高度更新，若经过旋转则此时高度已经被更新。
def insert(self, item):
if self._root is None:
self._root = AvlNode(item)
return def _insert(item, node):
if not node:
return AvlNode(item)
if item < node.value:
node.left = _insert(item, node.left)
if self.get_height(node.left) - self.get_height(node.right) == 2:
if item < node.left.value: # Situation 1: left --> left
node = self.single_rotate_left(node)
else: # Situation 2: left --> right
node = self.double_rotate_left(node)
elif item > node.value:
node.right = _insert(item, node.right)
if self.get_height(node.right) - self.get_height(node.left) == 2:
if item < node.right.value: # Situation 3: right --> left
node = self.double_rotate_right(node)
else: # Situation 4: right --> right
node = self.single_rotate_right(node)
else: pass
# Update node height (if not rotated, update is necessary.)
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
return node
self._root = _insert(item, self._root)
定义删除方法，进行递归删除，删除后检测是否需要平衡旋转，并选择旋转的方式，删除完成根据需要进行高度更新。
def delete(self, item):
if self._root is None:
return def _delete(item, node):
if not node: # Node no found
# return None
raise Exception('Element not in tree.') if item < node.value:
node.left = _delete(item, node.left)
# Delete left, rotate right
if self.get_height(node.right) - self.get_height(node.left) == 2:
if self.get_height(node.right.right) >= self.get_height(node.right.left): # Situation 4
node = self.single_rotate_right(node)
else: # Situation 3
node = self.double_rotate_right(node) elif item > node.value:
node.right = _delete(item, node.right)
# Delete right, rotate left
if self.get_height(node.left) - self.get_height(node.right) == 2:
if self.get_height(node.left.left) >= self.get_height(node.left.right): # Situation 1
node = self.single_rotate_left(node)
else: # Situation 3
node = self.double_rotate_left(node) else: # Node found
if node.left and node.right:
# Minimum node in right sub-tree has no left sub-node, can be used to make replacement
# Find minimum node in right sub-tree
min_node = self.find_min(node.right)
# Replace current node with min_node
node.value = min_node.value
# Delete min_node in right sub-tree
node.right = _delete(min_node.value, node.right)
else:
if node.left:
node = node.left
elif node.right:
node = node.right
else:
node = None
# Update node height (if not ratated, update is necessary.)
# If node is None, height is -1 already.
if node:
node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
return node
self._root = _delete(item, self._root)
最后定义一个测试函数，用于测试AVL树的功能。
首先初始化一棵树
def test(avl):
print('\nInit an AVL tree:')
for i in [1, 2, 3, 4, 5, 6, 7]:
avl.insert(i)
avl.show()
得到结果
Init an AVL tree:
4 | 4
2 | __|__
1 | | |
3 | 2 6
6 | _|_ _|_
5 | | | | |
7 | 1 3 5 7
接着尝试删除5, 6, 7三个节点，完成一个向左单旋转，
print('\nLeft single rotate:')
avl.delete(5)
avl.delete(7)
avl.delete(6)
avl.show()
得到结果，可以看到，此时AVL树已经完成了一个向左的平衡旋转
Left single rotate:
2 | 2
1 | __|__
4 | | |
3 | 1 4
| _|
| |
| 3
清空树并再次初始化树后
尝试删除1, 2, 3三个节点，完成一个向右单旋转，
print('\nDelete element from tree:')
avl.delete(1)
avl.delete(3)
avl.delete(2)
avl.show()
得到结果，可以看到，此时AVL树已经完成了一个向右的平衡旋转
Delete element from tree:
6 | 6
4 | __|__
5 | | |
7 | 4 7
| |_
| |
| 5
再次清空树，并建立一棵新的树
avl.make_empty()
print('\nInit an AVL tree:')
for i in [6, 2, 8, 1, 4, 9, 3, 5]:
avl.insert(i)
avl.show()
得到结果
Init an AVL tree:
6 | 6
2 | __|__
1 | | |
4 | 2 8
3 | _|_ |_
5 | | | |
8 | 1 4 9
9 | _|_
| | |
| 3 5
此时尝试删除节点9，完成一个右左双旋转
print('\nRight-Left double rotate:')
avl.delete(9)
avl.show()
得到结果
Right-Left double rotate:
4 | 4
2 | __|__
1 | | |
3 | 2 6
6 | _|_ _|_
5 | | | | |
8 | 1 3 5 8
最后再次清空树建立一棵新树，
avl.make_empty()
print('\nInit an AVL tree:')
for i in [4, 2, 8, 1, 6, 9, 5, 7]:
avl.insert(i)
avl.show()
显示结果如下
Init an AVL tree:
4 | 4
2 | __|__
1 | | |
8 | 2 8
6 | _| _|_
5 | | | |
7 | 1 6 9
9 | _|_
| | |
| 5 7
此时尝试删除节点1，造成不平衡完成一个左右双旋转
print('\nLeft-Right double rotate:')
avl.delete(1)
avl.show()
得到结果
Left-Right double rotate:
6 | 6
4 | __|__
2 | | |
5 | 4 8
8 | _|_ _|_
7 | | | | |
9 | 2 5 7 9
相关阅读
1. 二叉树
2. 查找树
最新文章
- 使用Support Vector Machine
- Velocity语言的介绍
- Entity Framework想说爱你不容易，这么多的报错，这么多的限制，该如何解决？
- 关闭window 8.1 的skydrive
- Haproxy配置支持https获取用户IP地址
- The Longest Increasing Subsequence (LIS)
- c# 计算1-100之间的所有质数（素数）的和
- 关于在Eclipse中构建patch开发环境
- For Me ...
- [php基础]PHP Form表单验证:PHP form validator使用说明
- Invalid file permission Please regenerate them with cacaoadm create-keys --force
- WKWebView代理方法解析
- java 程序编写规则（自己总结）
- VCI_CAN二次开发摘机
- js中的一元加法和一元减法
- ava集合---LinkedList源码解析
- django framework相关的错误信息
- 信息安全之路-web-xss学习(3)
- UOJ.35.[模板]后缀排序(后缀数组 倍增)
- ubuntu，day 2 ，退出当前用户，创建用户，查找，su,sudo，管道符，grep，alias，mount，tar解压