什么是AVL樹(shù)？
AVL樹(shù)即二叉平衡樹(shù)。因?yàn)槎娌檎覙?shù)的形狀會(huì)受插入數(shù)據(jù)集的影響柬姚，如果數(shù)據(jù)呈現(xiàn)有序排列，則二叉排序樹(shù)勢(shì)線性的翅娶，查找算法效率不高。如果我們能保證不管數(shù)據(jù)是否有序好唯，都能使二叉查找樹(shù)盡可能的小竭沫。這種特殊的二叉查找樹(shù)即AVL樹(shù)。具有如下特征：
- 根的左子樹(shù)和右子樹(shù)的高度差的絕對(duì)值的最大值為1
- 根的左子樹(shù)和右子樹(shù)都是AVL樹(shù)
如何構(gòu)造AVL樹(shù)骑篙？
查詢操作和普通的二叉查找樹(shù)相同蜕提，但是插入節(jié)點(diǎn)和刪除節(jié)點(diǎn)都可能破壞原樹(shù)的的平衡性，所以要考慮每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度差不能超過(guò)1靶端，這時(shí)可以通過(guò)旋轉(zhuǎn)操作來(lái)進(jìn)行修正谎势。
插入操作
1.插入節(jié)點(diǎn)在P的左孩子的左子樹(shù)上
處理方式：對(duì)P點(diǎn)右旋轉(zhuǎn)處理。如圖所示
1.png
python實(shí)現(xiàn)右旋轉(zhuǎn)
def right_rotate(node):
'''
右旋轉(zhuǎn)平衡操作
node: 要旋轉(zhuǎn)的節(jié)點(diǎn)
return: 旋轉(zhuǎn)后作為根的節(jié)點(diǎn)
'''
# 三步完成右旋轉(zhuǎn)操作
node_left = node.left
node.left = node_left.right
node_left.right = node
# 更新節(jié)點(diǎn)的高度
node_left.height = max(get_height(node_left.left),
get_height(node_left.right)) + 1
node.height = max(get_height(node.left), get_height(node.right)) + 1
return node_left
2.插入節(jié)點(diǎn)在P的右孩子的右子樹(shù)上
處理方式：對(duì)P點(diǎn)左旋轉(zhuǎn)處理杨名。如圖所示
2.png
python實(shí)現(xiàn)左旋轉(zhuǎn)
def left_rotate(node):
'''
左旋轉(zhuǎn)平衡操作
node: 要旋轉(zhuǎn)的節(jié)點(diǎn)
return: 旋轉(zhuǎn)后作為根的節(jié)點(diǎn)
'''
# 三步完成左旋轉(zhuǎn)操作
node_right = node.right
node.right = node_right.left
node_right.left = node
# 更新節(jié)點(diǎn)的高度
node.height = max(get_height(node.left), get_height(node.right)) + 1
node_right.height = max(
get_height(node_right.left), get_height(node_right.right)) + 1
return node_right
3.插入節(jié)點(diǎn)在P的右孩子的左子樹(shù)上
處理方式：先對(duì)C點(diǎn)做一次右旋轉(zhuǎn)脏榆，然后再對(duì)P點(diǎn)做一次左旋轉(zhuǎn)。如圖所示
3.png
python實(shí)現(xiàn)先右旋再左旋
def right_left_rotate(node):
'''
先右旋后右左旋平衡操作
node: 要旋轉(zhuǎn)的節(jié)點(diǎn)
return: 旋轉(zhuǎn)后作為根的節(jié)點(diǎn)
'''
# 右旋
node.right = right_rotate(node.right)
# 左旋
return left_rotate(node)
4.插入節(jié)點(diǎn)在P的左孩子的右子樹(shù)上
處理方式：先對(duì)C點(diǎn)做一次左旋轉(zhuǎn)台谍，然后再對(duì)P點(diǎn)做一次右旋轉(zhuǎn)须喂。如圖所示
4.png
python實(shí)現(xiàn)先左旋再右旋
def left_right_rotate(node):
'''
先左旋后右旋平衡操作
node: 要旋轉(zhuǎn)的節(jié)點(diǎn)
return: 旋轉(zhuǎn)后作為根的節(jié)點(diǎn)
'''
# 左旋
node.left = left_rotate(node.left)
# 右旋
return right_rotate(node)
刪除操作
要?jiǎng)h除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則直接刪除趁蕊，然后檢查該節(jié)點(diǎn)的父節(jié)點(diǎn)是否平衡坞生，如果不平衡，做平衡化處理
要?jiǎng)h除的節(jié)點(diǎn)只有左兒子或右兒子掷伙，則用左兒子或右兒子代替該節(jié)點(diǎn)是己，并做平衡花處理
要?jiǎng)h除的節(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)：如果左子樹(shù)高度比較高，則選取左子樹(shù)值最大的節(jié)點(diǎn)任柜，將值賦值給當(dāng)前節(jié)點(diǎn)卒废，并刪除那個(gè)值最大的節(jié)點(diǎn)；如果右子樹(shù)高度比較高宙地，則選取右子樹(shù)中值最小節(jié)點(diǎn)升熊，將值賦值給當(dāng)前節(jié)點(diǎn)，并刪除那個(gè)值最小的節(jié)點(diǎn)绸栅。 最后再做平衡化處理
python實(shí)現(xiàn)代碼
#!/usr/bin/python
# encoding: utf-8
'''AVL樹(shù)的實(shí)現(xiàn)'''
def get_height(node):
return node.height if node else -1
def tree_min(node):
'''找最小值'''
temp = node
while temp.left:
temp = temp.left
return temp
def tree_max(node):
'''找最大值'''
temp = node
while temp.right:
temp = temp.right
return temp
def right_rotate(node):
'''
右旋轉(zhuǎn)平衡操作
node: 要旋轉(zhuǎn)的節(jié)點(diǎn)
return: 旋轉(zhuǎn)后作為根的節(jié)點(diǎn)
'''
# 三步完成右旋轉(zhuǎn)操作
node_left = node.left
node.left = node_left.right
node_left.right = node
# 更新節(jié)點(diǎn)的高度
node_left.height = max(get_height(node_left.left),
get_height(node_left.right)) + 1
node.height = max(get_height(node.left), get_height(node.right)) + 1
return node_left
def left_rotate(node):
'''
左旋轉(zhuǎn)平衡操作
node: 要旋轉(zhuǎn)的節(jié)點(diǎn)
return: 旋轉(zhuǎn)后作為根的節(jié)點(diǎn)
'''
# 三步完成左旋轉(zhuǎn)操作
node_right = node.right
node.right = node_right.left
node_right.left = node
# 更新節(jié)點(diǎn)的高度
node.height = max(get_height(node.left), get_height(node.right)) + 1
node_right.height = max(
get_height(node_right.left), get_height(node_right.right)) + 1
return node_right
def left_right_rotate(node):
'''
先左旋后右旋平衡操作
node: 要旋轉(zhuǎn)的節(jié)點(diǎn)
return: 旋轉(zhuǎn)后作為根的節(jié)點(diǎn)
'''
# 左旋
node.left = left_rotate(node.left)
# 右旋
return right_rotate(node)
def right_left_rotate(node):
'''
先右旋后右左旋平衡操作
node: 要旋轉(zhuǎn)的節(jié)點(diǎn)
return: 旋轉(zhuǎn)后作為根的節(jié)點(diǎn)
'''
# 右旋
node.right = right_rotate(node.right)
# 左旋
return left_rotate(node)
def printTree(node):
if node:
print node.key
printTree(node.left)
printTree(node.right)
class Node(object):
def __init__(self, key):
# height為當(dāng)前節(jié)點(diǎn)的高度
self.key = key
self.left = None
self.right = None
self.height = 0
class AVLTree(object):
def __init__(self):
self.root = None
def find(self, key):
'''查找一個(gè)值'''
if self.root is None:
return None
else:
# 如果根節(jié)點(diǎn)有值级野，則才真正開(kāi)始執(zhí)行查詢函數(shù)
return self._find(key)
def _find(self, key):
# 真正的查詢函數(shù)
start = self.root
while start:
if key == start.key:
return start
elif key < start.key:
start = start.left
elif key > start.key:
start = start.right
return None
def insert(self, node):
# 把第一個(gè)插入的節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)
if self.root is None:
self.root = node
else:
self.root = self._insert(self.root, node)
def _insert(self, index, node):
'''
index: 根節(jié)點(diǎn)
node: 要插入的節(jié)點(diǎn)
'''
# 遞歸實(shí)現(xiàn)插入
# 遞歸結(jié)束條件
if index is None:
index = node
elif node.key < index.key:
index.left = self._insert(index.left, node)
# 如果左右子樹(shù)不平衡，則進(jìn)行平衡操作
if get_height(index.left) - get_height(index.right) == 2:
# 如果插在最左邊粹胯，則右旋
if node.key < index.left.key:
index = right_rotate(index)
# 如果插在左子節(jié)點(diǎn)的右子樹(shù)上蓖柔，則先左旋后右旋操作
else:
index = left_right_rotate(index)
elif node.key > index.key:
index.right = self._insert(index.right, node)
if get_height(index.right) - get_height(index.left) == 2:
if node.key > index.right.key:
index = left_rotate(index)
else:
index = right_left_rotate(index)
# 更新高度
index.height = max(get_height(index.left), get_height(index.right)) + 1
return index
def delete(self, key):
# 更新根節(jié)點(diǎn)
self.root = self._delete(self.root, key)
def _delete(self, index, key):
'''
index: 根節(jié)點(diǎn)
node: 要?jiǎng)h除的節(jié)點(diǎn)
'''
if key < index.key:
index.left = self._delete(index.left, key)
if get_height(index.right) - get_height(index.left) == 2:
if get_height(index.right.right) > get_height(index.right.left):
index = left_rotate(index)
else:
index = right_left_rotate(index)
index.height = max(get_height(index.left), get_height(index.right))
elif key > index.key:
index.right = self._delete(index.right, key)
if get_height(index.left) - get_height(index.right) == 2:
if get_height(index.left.left) > get_height(index.left.right):
index = right_rotate(index)
else:
index = left_right_rotate(index)
index.height = max(get_height(index.left), get_height(index.right))
# 當(dāng)要?jiǎng)h除的節(jié)點(diǎn)左右子樹(shù)都存在時(shí)
elif index.left and index.right:
if get_height(index.left) <= get_height(index.right):
index.key = tree_min(index.right).key
index.right = self._delete(index.right, index.key)
else:
index.key = tree_max(index.left).key
index.left = self._delete(index.left, index.key)
index.height = max(get_height(index.left),
get_height(index.right)) + 1
# 只有左子樹(shù)或右子樹(shù);沒(méi)有子樹(shù)
else:
if index.right:
index = index.right
else:
index = index.left
return index
if __name__ == '__main__':
alist = [10, 6, 2, 12, 13, 8]
tree = AVLTree()
for i in alist:
node = Node(i)
tree.insert(node)
printTree(tree.root)
tree.find(8)
tree.delete(8)
print("====分割線====")
printTree(tree.root)
