数据结构 --- AVL树( 二 ) _AVL树

文章插图

左右旋转后得到下图:

文章插图

从上图可以看出，该AVL树已经平衡。

删除算法

从AVL树中删除一个节点，可以按照BST删除节点的方法先删除该节点，由于删除后AVL树可能不平衡，因此需要进行调整。假设要删除下面这颗AVL树的值为13的节点。删除过程如下：

文章插图

按照BST的方法删除值为13的节点，删除后结果如下图所示：

文章插图

重新计算各个节点的平衡因子，如下图所示：

文章插图

值为21的节点平衡因子为2，因此需要调整。

调整该AVL数，使其平衡。

文章插图

以上图中棕色框值为9的节点为中心，将值为21的节点右旋，右旋后得到下图：

文章插图

再对上图的各个节点重新计算平衡因子得到下图:

文章插图

从上图可以看出，各个节点的平衡因子均大于等-1并且小于等于1，所以调整完成。该AVL数达到平衡状态。
对于AVL数的遍历，查找均和BST树一样，不再介绍，同学们可以参考我之前的文章<<数据结构---二叉搜索树>> 。
下面是AVL树的Python代码实现：
# AVL tree implementation in Python
import sys
# Create a tree node
class TreeNode(object):
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree(object):
# Function to insert a node
def insert_node(self, root, key):
# Find the correct location and insert the node
if not root:
return TreeNode(key)
elif key < root.key:
root.left = self.insert_node(root.left, key)
else:
root.right = self.insert_node(root.right, key)
root.height = 1 + max(self.getHeight(root.left),
self.getHeight(root.right))
# Update the balance factor and balance the tree
balanceFactor = self.getBalance(root)
if balanceFactor > 1:
if key < root.left.key:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1:
if key > root.right.key:
return self.leftRotate(root)
else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
# Function to delete a node
def delete_node(self, root, key):
# Find the node to be deleted and remove it
if not root:
return root
elif key < root.key:
root.left = self.delete_node(root.left, key)
elif key > root.key:
root.right = self.delete_node(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = self.getMinValueNode(root.right)
root.key = temp.key
root.right = self.delete_node(root.right,
temp.key)
if root is None:
return root
# Update the balance factor of nodes
root.height = 1 + max(self.getHeight(root.left),
self.getHeight(root.right))
balanceFactor = self.getBalance(root)
# Balance the tree
if balanceFactor > 1:
if self.getBalance(root.left) >= 0:
return self.rightRotate(root)
else:
root.left = self.leftRotate(root.left)
return self.rightRotate(root)
if balanceFactor < -1:
if self.getBalance(root.right) <= 0:
return self.leftRotate(root)
【数据结构 --- AVL树】else:
root.right = self.rightRotate(root.right)
return self.leftRotate(root)
return root
# Function to perform left rotation
def leftRotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self.getHeight(z.left),
self.getHeight(z.right))
y.height = 1 + max(self.getHeight(y.left),
self.getHeight(y.right))
return y
# Function to perform right rotation