什么是AVL樹衍腥？
AVL樹即二叉平衡樹岂膳。因?yàn)槎娌檎覙涞男螤顣?huì)受插入數(shù)據(jù)集的影響誓竿，如果數(shù)據(jù)呈現(xiàn)有序排列，則二叉排序樹是線性的闷营，查找算法效率不高。如果我們能保證不管數(shù)據(jù)是否有序知市，都能使二叉查找樹的高度盡可能的小傻盟。這種特殊的二叉查找樹即AVL樹。具有如下特征：
- 根的左子樹和右子樹的高度差的絕對(duì)值的最大值為1
- 根的左子樹和右子樹都是AVL樹
如果構(gòu)造AVL樹嫂丙？
查詢操作和普通的二叉查找樹相同娘赴，但是插入節(jié)點(diǎn)和刪除節(jié)點(diǎn)都可能破壞原樹的平衡性，所以要考慮每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差不能超過1跟啤，這時(shí)可以通過旋轉(zhuǎn)操作來進(jìn)行修正诽表。
** 插入操作 **
-
插入節(jié)點(diǎn)在P的左孩子的左子樹上
處理方式：對(duì)P點(diǎn)右旋轉(zhuǎn)處理。如圖所示
圖片來自網(wǎng)絡(luò).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
-
插入節(jié)點(diǎn)在P的右孩子的右子樹上
處理方式：對(duì)P點(diǎn)左旋轉(zhuǎn)處理隅肥。如圖所示
圖片來自網(wǎng)絡(luò).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
-
插入節(jié)點(diǎn)在P的右孩子的左子樹上
處理方式：先對(duì)C點(diǎn)做一次右旋轉(zhuǎn)竿奏，然后再對(duì)P點(diǎn)做一次左旋轉(zhuǎn)。如圖所示
圖片來自網(wǎng)絡(luò).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)
-
插入節(jié)點(diǎn)在P的左孩子的右子樹上
處理方式：先對(duì)C點(diǎn)做一次左旋轉(zhuǎn)腥放，然后再對(duì)P點(diǎn)做一次右旋轉(zhuǎn)泛啸。如圖所示
圖片來自網(wǎng)絡(luò).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)既有左子樹又有右子樹：如果左子樹高度比較高，則選取左子樹值最大的節(jié)點(diǎn)聚请，將值賦值給當(dāng)前節(jié)點(diǎn)荠雕，并刪除那個(gè)值最大的節(jié)點(diǎn)；如果右子樹高度比較高，則選取右子樹中值最小節(jié)點(diǎn)舞虱，將值賦值給當(dāng)前節(jié)點(diǎn)欢际，并刪除那個(gè)值最小的節(jié)點(diǎn)。 最后再做平衡化處理
python實(shí)現(xiàn)代碼
#!/usr/bin/python
# encoding: utf-8
'''AVL樹的實(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)有值矾兜，則才真正開始執(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)
# 如果左右子樹不平衡损趋，則進(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)的右子樹上椅寺，則先左旋后右旋操作
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í)
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
# 只有左子樹或右子樹;沒有子樹
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)
AVL樹效率
查找節(jié)點(diǎn)：時(shí)間復(fù)雜度為O(logN)
插入節(jié)點(diǎn)：因?yàn)樾枰炔檎业焦?jié)點(diǎn)浑槽，然后進(jìn)行旋轉(zhuǎn)平衡操作（基本為1），所以也為O(logN)
刪除節(jié)點(diǎn)：再查找到節(jié)點(diǎn)之后返帕，還需要檢查從刪除節(jié)點(diǎn)到根節(jié)點(diǎn)的平衡因子桐玻，所以時(shí)間復(fù)雜度為O(logN)
