AVL树是首个被发明的自平衡二叉查找树,在1962年由两位苏联科学家G.M. Adelson-Velsky和E.M. Landis提出。AVL树得名于发明者的首字母。在AVL树中,任何节点的两个子树的高度最大差别为一,确保了树的平衡度,使得查找操作相比于普通的二叉查找树更加高效。
AVL树保持了二叉查找树的基础性质,即对于任何一个节点,其左子树上的所有节点的值都小于该节点的值,右子树所有节点的值都大于该节点的值。此外,AVL树增加了以下平衡条件:
这种强制的平衡条件确保树的最坏情况下的高度为O(log n),其中n是树中节点的数量,从而也保证了查找/插入/删除操作都可以在对数时间内完成。
保持AVL树平衡的主要机制是通过旋转操作,分为四种基本旋转:
LL(左左)旋转: 当在节点的左子树的左侧插入导致不平衡时进行。通过一个右旋转来平衡树。
RR(右右)旋转: 当在节点的右子树的右侧插入导致不平衡时进行。通过一个左旋转来平衡树。
LR(左右)旋转: 当在节点的左子树的右侧插入导致不平衡时进行。首先在导致失衡节点的左子树上进行左旋转,然后对该节点进行右旋转。
RL(右左)旋转: 当在节点的右子树的左侧插入导致不平衡时进行。首先在导致失衡节点的右子树上进行右旋转,然后对该节点进行左旋转。
这些旋转能够在维持二叉查找树的性质的同时回复AVL树特有的平衡性质。
向AVL树插入一个新的节点大体分为三步:
常规二叉搜索树插入: 首先按照二叉搜索树的规则将节点插入正确位置。
更新平衡因子: 从插入点开始,向上遍历回根节点,更新祖先节点的平衡因子。
重新平衡(如果必要): 如果在更新过程中某个节点的平衡因子变为非-1、0或1,将对该节点进行一次或多次旋转操作以恢复平衡。这可能涉及上述四种旋转中的任何一种或复合旋转。
从AVL树中删除一个节点包括了以下步骤:
常规二叉搜索树删除: 遵循二叉搜索树的规则,找到并删除该节点,这可能涉及将节点与其直接后继互换的操作。
更新平衡因子: 从删除节点的父节点开始,向上遍历到根节点,更新节点的平衡因子。
重新平衡(如果必要): 如果在更新过程中某个节点的平衡因子不是-1、0或1,将对该节点执行相应的旋转操作恢复平衡。
删除操作要复杂些,因为可能需要在不同层上多次进行平衡调整。
AVL树的设计主旨是维持二叉查找树在动态更新操作下的平衡,从而避免性能恶化。为了保持深入的讨论,我们将分别撷取关键方面进行详尽的分析。
AVL树中每个节点N都有一个平衡因子(BF),它是根据以下公式定义的:
平衡因子(BF) = 高度(左子树) - 高度(右子树)
常规情况下,左子树或右子树的高度的计算是从当前节点向下递归到叶子节点,计算最长路径上边的数量,叶子节点的高度定义为0。因此:
AVL树要求所有节点的平衡因子绝对值必须小于或等于1。每次插入或删除操作后,都需要更新从影响节点到根节点路径上所有节点的平衡因子,并进行相应的旋转操作以恢复平衡性。
旋转是用来恢复AVL树平衡的一种操作。在不同的情形下,可能需要不同种类的旋转操作:
当一个节点N的左子树的左边产生了一个新节点,并造成不平衡时,会进行LL旋转。以下是LL旋转的步骤:
这是LL的镜像操作,当一个节点N的右子树的右边产生了一个新节点,并造成不平衡时,会进行RR旋转。以下是RR旋转的步骤:
当一个节点N的左子树的右边产生了一个新节点,并造成不平衡时,会进行LR旋转。LR旋转首先进行L的RR旋转,然后对N进行LL旋转。
这是LR旋转的镜像,当一个节点N的右子树的左边产生了一个新节点,并造成不平衡时,会进行RL旋转。
插入操作可以概括为以下步骤:
伪代码示例:
function insert(node, value)
if node == null
return newNode(value)
if value < node.value
node.left = insert(node.left, value)
else if value > node.value
node.right = insert(node.right, value)
else
return node
// 更新节点的高度
node.height = 1 + max(height(node.left), height(node.right))
// 获取平衡因子
balance = getBalance(node)
// 平衡
if balance > 1 and value < node.left.value
return rightRotate(node)
if balance < -1 and value > node.right.value
return leftRotate(node)
if balance > 1 and value > node.left.value
node.left = leftRotate(node.left)
return rightRotate(node)
if balance < -1 and value < node.right.value
node.right = rightRotate(node.right)
return leftRotate(node)
return node
删除操作遵循以下步骤:
伪代码示例:
function deleteNode(root, value)
// STEP 1: PERFORM STANDARD BST DELETE
if root == null
return root
if value < root.value
root.left = deleteNode(root.left, value)
else if value > root.value
root.right = deleteNode(root.right, value)
else
// node with only one child or no child
if (root.left == null) or (root.right == null)
temp = null
if temp == root.left
temp = root.right
else
temp = root.left
if temp == null // No child case
temp = root
root = null
else // One child case
root = temp // Copy the contents of the non-empty child
else
// node with two children: Get the inorder successor
temp = minValueNode(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
if root == null
return root
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root.height = max(height(root.left), height(root.right)) + 1
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE
balance = getBalance(root)
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if balance > 1 and getBalance(root.left) >= 0
return rightRotate(root)
// Left Right Case
if balance > 1 and getBalance(root.left) < 0
root.left = leftRotate(root.left)
return rightRotate(root)
// Right Right Case
if balance < -1 and getBalance(root.right) <= 0
return leftRotate(root)
// Right Left Case
if balance < -1 and getBalance(root.right) > 0
root.right = rightRotate(root.right)
return leftRotate(root)
return root
由于AVL树的严格平衡特性,插入和删除操作可能要求多次旋转,这增加了操作的复杂性。尽管如此,由于树的高度被严格控制在O(log n),因此插入和删除操作的最坏情况时间复杂度为O(log n)。实际的旋转操作仅涉及改变节点几个指针,因此可以认为是O(1)操作,不过这会在插入或删除后沿着路径向上逐步进行,因此总的旋转成本是O(log n)。由于我们只会在最坏的情况下沿着路径上旋转一次,所以这样的成本是可以接受的。
旋转操作虽然以四类基本操作来定义,但是每种操作对树的结构和平衡因子都有不同的影响。例如,LL旋转是对树的一边性质最直接的补救,它通过一次简单的旋转即可恢复平衡。而LR旋转则涉及到两个步骤,首先是对失衡节点的左子节点进行RR旋转,然后对失衡节点本身进行LL旋转。这意味着在执行LR旋转时,我们需要更新不仅是失衡节点,同时也要更新其左子节点及LR节点的平衡因子。从逻辑上讲,LR旋转处理的是两种不平衡因子的组合,因此在理解和实现时需要更多的注意。
AVL树的维护需要对树的结构和旋转操作有深刻的理解。每次插入和删除操作后都可能要求维护这种平衡,而这种保持平衡的要求是AVL树能够保持其性能特点的根本。