Data Structures Algorithms 简明教程
AVL Trees
要发明的第一种自平衡二叉搜索树是 AVL 树。AVL 树的名称是由其发明者的名字命名的 − Adelson-Velsky 和 Landis。
The first type of self-balancing binary search tree to be invented is the AVL tree. The name AVL tree is coined after its inventor’s names − Adelson-Velsky and Landis.
在 AVL 树中,左右子树的高度差,称为 Balance Factor ,最多必须为 1。一旦差值超过 1,该树会自动执行平衡算法,直至差值再次变为 1。
In AVL trees, the difference between the heights of left and right subtrees, known as the Balance Factor, must be at most one. Once the difference exceeds one, the tree automatically executes the balancing algorithm until the difference becomes one again.
BALANCE FACTOR =
HEIGHT(LEFT SUBTREE) − HEIGHT(RIGHT SUBTREE)
在 AVL 树的平衡算法中通常有四种旋转情况:LL、RR、LR、RL。
There are usually four cases of rotation in the balancing algorithm of AVL trees: LL, RR, LR, RL.
LL Rotations
当将节点插入导致不平衡树的右子树时,执行 LL 旋转。这是一个单一的左旋转,再次使树平衡 −
LL rotation is performed when the node is inserted into the right subtree leading to an unbalanced tree. This is a single left rotation to make the tree balanced again −
Fig : LL Rotation
Fig : LL Rotation
发生不平衡的节点变为左子节点,新添加的节点变为右子节点,中间节点变为父节点。
The node where the unbalance occurs becomes the left child and the newly added node becomes the right child with the middle node as the parent node.
RR Rotations
当将节点插入导致不平衡树的左子树时,执行 RR 旋转。这是一个单一的右旋转,再次使树平衡 −
RR rotation is performed when the node is inserted into the left subtree leading to an unbalanced tree. This is a single right rotation to make the tree balanced again −
Fig : RR Rotation
Fig : RR Rotation
发生不平衡的节点变为右子节点,新添加的节点变为左子节点,中间节点变为父节点。
The node where the unbalance occurs becomes the right child and the newly added node becomes the left child with the middle node as the parent node.
LR Rotations
LR 旋转是之前单一旋转的扩展版本,也称为双旋转。当将节点插入左子树的右子树中时,执行此操作。LR 旋转将左旋转与右旋转相结合。有几个需要遵循的步骤来执行此操作。
LR rotation is the extended version of the previous single rotations, also called a double rotation. It is performed when a node is inserted into the right subtree of the left subtree. The LR rotation is a combination of the left rotation followed by the right rotation. There are multiple steps to be followed to carry this out.
-
Consider an example with “A” as the root node, “B” as the left child of “A” and “C” as the right child of “B”.
-
Since the unbalance occurs at A, a left rotation is applied on the child nodes of A, i.e. B and C.
-
After the rotation, the C node becomes the left child of A and B becomes the left child of C.
-
The unbalance still persists, therefore a right rotation is applied at the root node A and the left child C.
-
After the final right rotation, C becomes the root node, A becomes the right child and B is the left child.
Fig : LR Rotation
Fig : LR Rotation
RL Rotations
RL 旋转也是先前单旋转的扩展版本,因此它被称为双旋转,并且当将一个节点插入右子树的左子树中时执行该旋转。RL 旋转是右旋转和左旋转的组合。需要遵循多个步骤来执行此操作。
RL rotation is also the extended version of the previous single rotations, hence it is called a double rotation and it is performed if a node is inserted into the left subtree of the right subtree. The RL rotation is a combination of the right rotation followed by the left rotation. There are multiple steps to be followed to carry this out.
-
Consider an example with “A” as the root node, “B” as the right child of “A” and “C” as the left child of “B”.
-
Since the unbalance occurs at A, a right rotation is applied on the child nodes of A, i.e. B and C.
-
After the rotation, the C node becomes the right child of A and B becomes the right child of C.
-
The unbalance still persists, therefore a left rotation is applied at the root node A and the right child C.
-
After the final left rotation, C becomes the root node, A becomes the left child and B is the right child.
Fig : RL Rotation
Fig : RL Rotation
Basic Operations of AVL Trees
对 AVL 树结构执行的基本操作包括对二叉查找树执行的所有操作,因为 AVL 树的核心实际上只是一个保存其所有属性的二叉查找树。因此,对 AVL 树执行的基本操作为 Insertion 和 Deletion 。
The basic operations performed on the AVL Tree structures include all the operations performed on a binary search tree, since the AVL Tree at its core is actually just a binary search tree holding all its properties. Therefore, basic operations performed on an AVL Tree are − Insertion and Deletion.
Insertion operation
通过遵循二叉搜索树的插入属性将数据插入 AVL 树中,即左子树必须包含小于根值的元素,而右子树必须包含所有更大的元素。
The data is inserted into the AVL Tree by following the Binary Search Tree property of insertion, i.e. the left subtree must contain elements less than the root value and right subtree must contain all the greater elements.
但是,在 AVL 树中,在插入每个元素后,检查树的平衡因子;如果它没有超过 1,则树保持原样。但是,如果平衡因子超过 1,则应用平衡算法重新调整树,使得平衡因子再次小于或等于 1。
However, in AVL Trees, after the insertion of each element, the balance factor of the tree is checked; if it does not exceed 1, the tree is left as it is. But if the balance factor exceeds 1, a balancing algorithm is applied to readjust the tree such that balance factor becomes less than or equal to 1 again.
AVL 树的插入操作涉及以下步骤 -
The following steps are involved in performing the insertion operation of an AVL Tree −
Step 1 − Create a node
Step 2 − Check if the tree is empty
Step 3 − If the tree is empty, the new node created will become the
root node of the AVL Tree.
Step 4 − If the tree is not empty, we perform the Binary Search Tree
insertion operation and check the balancing factor of the node
in the tree.
Step 5 − Suppose the balancing factor exceeds ±1, we apply suitable
rotations on the said node and resume the insertion from Step 4.
让我们通过构建一个包含 1 到 7 个整数的示例 AVL 树来理解插入操作。
Let us understand the insertion operation by constructing an example AVL tree with 1 to 7 integers.
从第一个元素 1 开始,我们创建一个节点并测量平衡,即 0。
Starting with the first element 1, we create a node and measure the balance, i.e., 0.
由于二叉查找属性和平衡因子都得到满足,我们再向树中插入另一个元素。
Since both the binary search property and the balance factor are satisfied, we insert another element into the tree.
计算两个节点的平衡因子,发现为 -1(左子树的高度为 0,右子树的高度为 1)。由于它没有超过 1,我们向树中添加另一个元素。
The balance factor for the two nodes are calculated and is found to be -1 (Height of left subtree is 0 and height of the right subtree is 1). Since it does not exceed 1, we add another element to the tree.
现在,添加第三个元素后,平衡因子超过 1 并变成 2。因此,应用旋转。由于不平衡发生在两个右侧节点上,所以在这种情况下应用 RR 旋转。
Now, after adding the third element, the balance factor exceeds 1 and becomes 2. Therefore, rotations are applied. In this case, the RR rotation is applied since the imbalance occurs at two right nodes.
树被重新排列为 −
The tree is rearranged as −
类似地,使用这些旋转插入并重新排列下一个元素。重新排列后,我们实现树为 −
Similarly, the next elements are inserted and rearranged using these rotations. After rearrangement, we achieve the tree as −
以下是该操作在各种编程语言中的实现 −
Following are the implementations of this operation in various programming languages −
Deletion operation
AVL 树中的删除发生在三种不同的情况下 −
Deletion in the AVL Trees take place in three different scenarios −
-
Scenario 1 (Deletion of a leaf node) − If the node to be deleted is a leaf node, then it is deleted without any replacement as it does not disturb the binary search tree property. However, the balance factor may get disturbed, so rotations are applied to restore it.
-
Scenario 2 (Deletion of a node with one child) − If the node to be deleted has one child, replace the value in that node with the value in its child node. Then delete the child node. If the balance factor is disturbed, rotations are applied.
-
Scenario 3 (Deletion of a node with two child nodes) − If the node to be deleted has two child nodes, find the inorder successor of that node and replace its value with the inorder successor value. Then try to delete the inorder successor node. If the balance factor exceeds 1 after deletion, apply balance algorithms.
使用上面给出的同一棵树,让我们在三种情况下执行删除 −
Using the same tree given above, let us perform deletion in three scenarios −
-
Deleting element 7 from the tree above −
由于元素 7 是一个叶节点,我们通常在不干扰树中的任何其他节点的情况下删除该元素
Since the element 7 is a leaf, we normally remove the element without disturbing any other node in the tree
-
Deleting element 6 from the output tree achieved −
然而,元素 6 不是一个叶节点,并且有一个子节点与之相连。在这种情况下,我们用其子节点替换节点 6:节点 5。
However, element 6 is not a leaf node and has one child node attached to it. In this case, we replace node 6 with its child node: node 5.
树的平衡变为 1,并且因为它没有超过 1,所以树保持原样。如果我们进一步删除元素 5,我们不得不应用左旋转;由于不平衡发生在 1-2-4 和 3-2-4,所以可能是 LL 或 LR。
The balance of the tree becomes 1, and since it does not exceed 1 the tree is left as it is. If we delete the element 5 further, we would have to apply the left rotations; either LL or LR since the imbalance occurs at both 1-2-4 and 3-2-4.
删除元素 5 后平衡因子受到干扰,因此我们应用 LL 旋转(这里我们也可以应用 LR 旋转)。
The balance factor is disturbed after deleting the element 5, therefore we apply LL rotation (we can also apply the LR rotation here).
一旦在路径 1-2-4 上应用 LL 旋转,节点 3 保持为节点 2 的右子节点(现在由节点 4 占据)的样子。因此,该节点被添加到节点 2 的右子树中,并作为节点 4 的左子节点。
Once the LL rotation is applied on path 1-2-4, the node 3 remains as it was supposed to be the right child of node 2 (which is now occupied by node 4). Hence, the node is added to the right subtree of the node 2 and as the left child of the node 4.
-
Deleting element 2 from the remaining tree −
如场景 3 中所提到的那样,该节点有两个子节点。因此,我们找到它是一个叶节点的中序后继(例如,3)并用中序后继替换其值。
As mentioned in scenario 3, this node has two children. Therefore, we find its inorder successor that is a leaf node (say, 3) and replace its value with the inorder successor.
树的平衡仍然保持为 1,因此我们在不进行任何旋转的情况下将树保留原样。
The balance of the tree still remains 1, therefore we leave the tree as it is without performing any rotations.
以下是该操作在各种编程语言中的实现 −
Following are the implementations of this operation in various programming languages −