平衡二叉树及代码实现
程序员文章站
2022-03-03 18:45:13
1 介绍平衡二叉树，又称AVL树，在学习AVL树之前，最好先掌握二叉查找树，因为AVL树，就是对二叉查找树的平衡性进行优化而得到的特殊的二叉搜索树。它有和二叉搜索树一样的特点：树中的任一节点总是大于其左子树的任一节点，小于其右子树的任一节点同时有着自己独特的特点树中任一节点的左右两个子树的高度差的不会超过1示例2 时间复杂度平衡二叉树的左右子树高度差不大于1，这个特点使它的时间复杂度和普通的二叉查找树相比要稳定得多，不会出现普通二叉查找树退化成链表的情况，树高和节点数的关系为 h =...
1 介绍
平衡二叉树，又称AVL树，是对二叉查找树的平衡性进行优化而得到的特殊的二叉查找树（所以在学习AVL树之前，最好先掌握二叉查找树）。
- 它有和二叉搜索树一样的特点：
树中的任一节点总是大于其左子树的任一节点，小于其右子树的任一节点 - 同时有着自己独特的特点
树中任一节点的左右两个子树的高度差的不会超过1
2 时间复杂度
平衡二叉树的左右子树高度差不大于1，这个特点使它的时间复杂度和普通的二叉查找树相比要稳定得多，不会出现普通二叉查找树退化成链表的情况，树高和节点数的关系为 h = log₂n + 1，所以时间复杂度基本可以视为：O(log₂n)。
3 实现
3.1 引子
和普通的二叉查找树对比，搜索节点的方法是一样的，不同的是添加节点方法和删除节点方法，因为这两个方法都可能引起某个节点的左右子树高度差大于1，导致该节点失衡。
实现平衡二叉树，主要就是实现添加节点和删除节点这两个方法，而实现这两个方法的有两个关键点：
- 如何判断有节点失衡
- 如何对失衡节点恢复平衡
3.2 平衡因子
为了判断是否有节点失衡，这里给节点添加一个属性：balance，并将这个属性称为平衡因子。
平衡因子的值所代表含义是：以某节点为根节点，该节点左右子树的高度差，并且这里规定：
- balance = 该节点右子树高度 - 该节点左子树高度
对于新添加的节点，因为它没有任何子节点，所以它的初始 balance 值为0。
3.3 旋转
通过平衡因子可以判断是否有失衡节点（即balance的绝对值超过1的节点），而通过旋转则可以将失衡节点恢复平衡。
旋转按旋转的方向可分为左旋转和右旋转。
以下是一部分失衡情景下对应的旋转方式（仔细阅读它，有助于理解旋转的实现）：
3.4 添加节点
3.4.1 图例
以下是在添加节点后可能导致失衡的情形，以及使之恢复平衡的旋转方式。
- 失衡情形一及对应旋转方式
- 失衡情形二及对应旋转方式
- 失衡情形三及对应旋转方式
- 失衡情形四及对应旋转方式
3.4.2 总结与思路
-
可以看到，列举的所有情形无论经过了多少次旋转，最终都是右旋，即这里只是列举最终右旋的情况，因为分析最终右旋和最终左旋是一样的道理，择其一即可
-
在列举的图例中，可以看到情形一和情形二其实是相同的情况，不同的只是情形一的失衡点是A节点，情形二的失衡点为B节点
-
如果将最终旋转之前所进行的旋转都称为调整，那么可以发现，进行调整的情形都有个共同点，那就是调整点的 balance 和它的父节点 balance 符号相反，拿最复杂、需要进行三次旋转（两次调整 + 一次最终旋转）的失衡情形四的第一种情况（第二张图，以下简称：例4-1）来举例：
第一次调整
E节点的balance为-1，E节点的父节点B的balance为1，二者符号一正一负，刚好相反第二次调整
经过第一次调整，B节点的balance依旧为1，而它的父节点A的balance为-2，二者符号相反 -
结合第3点，总结出如下添加节点实现步骤
- 先执行节点操作
使用普通二叉搜索树添加节点的方式，将节点加入到树中
- 调整balance并寻找失衡点
在加入新节点后，树的结构发生变化，一些节点的balance也会随之改变，所以势必要更新这些节点的balance，而更新的同时，通过判断更新后的balance值就可以顺便获取失衡节点
哪些节点需要更新balance？
对于整棵二叉树而言，新增一个节点，那么从新增节点的父节点，父节点的父节点…一直往上追溯到根节点，它们的balance都会发生改变。
注意，如果遇到失衡点，只需要调整到失衡点即可，因为之后恢复平衡操作之后还需要重新计算一次balance，它会抵消掉当前添加节点、导致的失衡节点到根节点这部分balance受到的影响
具体更新方式
采用从新增的节点开始往上更新的方式，且如果子节点属于父节点的左子节点，父节点balance就减1，如果是右子节点则加1。
如例4-1中，从新增F节点往上找，他属于E的左子节点，所以E的balance减1，,变为-1，继续往上，E属于B的右子节点，B的balance加1，为1，B又属于A节点左子节点，A的balance减1，为-2，此时A节点的左右子树高度差超过1，所以失衡节点为A。- 进行节点调整
如果发现有失衡节点，那就要进行恢复平衡操作，也就是一系列旋转操作，而在进行最终旋转之前，可能存在一些节点需要进行调整。
寻找需要进行调整的节点，一样是以新增节点为初始节点自下往上进行，直至失衡节点为止。
调整方向- 如果当前节点父节点balance > 0，对当前节点右旋；
- 如果当前节点父节点balance < 0，对当前节点左旋。
- 旋转后初始节点的balance符号将和它父节点符号相同。
如列4-1，从新增F节点开始，新增节点的balance为0，所以从他父节点E开始进行符号对比。- E的balance为-1，B的balance为1，符号相反，对E右旋，调整后E的balance为1，符号同B；
- B的balance为1，A的balance为-2，符号相反，对B左旋，调整后B的balance为-1，符号同A；
- A为失衡节点，所以调整到此为止
- 进行最终旋转
在调整结束后就可以放心的进行最后一次旋转了，而最终旋转的方向由失衡点的balance符号决定：
- 如果balance > 0，则对失衡节点左旋；
- 如果balance < 0，则对失衡节点右旋。
3.4.3 代码流程图
3.5 删除节点
3.5.1 图例
以下是删除节点的情形之一以及对应的失衡调整与旋转。
3.5.2 总结与思路
-
所以，删除节点的实现，总体思路同添加节点是一样的，只不过具体操作起来会稍微复杂下。总结如下：
- 先执行节点操作
使用普通二叉搜索树删除节点的方式，将节点从树中移除。
- 调整balance并寻找失衡点
和添加节点一样，删除节点后树的结构也会发生变化，此时balance值受影响的节点为：从被删除节点开始，一直往上追溯到根节点。
被删除节点的一种特殊情况
当被删节点同时有左子节点和右子节点时，用户输入的被删除节点并不是真正的被删除节点，因为此时按照二叉搜索树删除节点的方式：- 找到被删除节点右子树最小节点（或左子树最大节点）
- 删除1中找到的节点
- 将1中找到的节点的节点值赋给被删除节点
所以这种情况下，真正被删除的节点为：被删除节点右子树最小节点。
- 进行节点调整
在添加节点中，可以很明确地知道从新增节点开始往上调整，但是对于删除节点而言，却无法知道从哪个节点开始往上调整，所以在执行调整前，还需要一个额外的操作去获取这个初始节点。
这里采用的是节点调整的反向路线，即从失衡节点开始自上往下寻找，比如3.5.1图例- 首先判断失衡节点balance符号，在删除节点F后，A为失衡节点，balance为-2，表明初始节点存在于它的左子树中。
- B为A的左子节点，balance为1，和A符号相反，说明将来需要对B节点做调整，又B的balance大于0，和第一步一样，说明初始节点存在于B的右子树中，所以暂时可以将初始节点定为B的右子节点E。
- E的balance为-1，和B符号相反，说明将来也需要对E节点做调整，又E的balance小于0，说明初始节点存在于E的左子树中，所以继续将初始节点转设为E的左子节点G。
- G的balance为0，到此为止，可以确定初始节点就是G了。
通过上面的步骤，获得了初始节点，而之后的调整节点操作就完全和添加节点时候一样了。
- 进行最终旋转
3.5.3 代码流程图
3.6 Java实现及验证
3.6.1 Java代码
package structure.tree;
import java.util.Optional;
public class MyAVLTree {
public class AVLNode {
public Comparable value;
public AVLNode leftNode;
public AVLNode rightNode;
private AVLNode parentNode;
private int balance = 0;
AVLNode(Comparable value) {
this.value = value;
}
@SuppressWarnings("unchecked")
private void addNode(AVLNode newNode) {
if (newNode.value.compareTo(this.value) > 0) {
if (null == this.rightNode) {
this.rightNode = newNode;
newNode.parentNode = this;
} else {
this.rightNode.addNode(newNode);
}
} else if (newNode.value.compareTo(this.value) < 0) {
if (null == this.leftNode) {
this.leftNode = newNode;
newNode.parentNode = this;
} else {
this.leftNode.addNode(newNode);
}
}
}
@SuppressWarnings("unchecked")
private Optional<AVLNode> searchNode(Comparable value) {
if (value.compareTo(this.value) == 0) {
return Optional.of(this);
} else if (value.compareTo(this.value) < 0 && null != this.leftNode) {
return this.leftNode.searchNode(value);
} else if (value.compareTo(this.value) > 0 && null != this.rightNode) {
return this.rightNode.searchNode(value);
} else {
return Optional.empty();
}
}
/**
* 删除节点操作
*
* @param targetNode 准备执行删除的节点
* @return 返回真正被删除的节点
*/
private Optional<AVLNode> removeNode(AVLNode targetNode) {
Optional<AVLNode> deletedNode = Optional.empty();
if (null == targetNode.leftNode && null == targetNode.rightNode) {
if (null == targetNode.parentNode) {
MyAVLTree.this.rootNode = null;
} else {
if (targetNode == targetNode.parentNode.leftNode) {
targetNode.parentNode.leftNode = null;
} else {
targetNode.parentNode.rightNode = null;
}
deletedNode = Optional.of(targetNode);
}
} else if (null != targetNode.leftNode && null != targetNode.rightNode) {
AVLNode rightTreeMinNode = searchMinNode(targetNode.rightNode);
removeNode(rightTreeMinNode);
targetNode.value = rightTreeMinNode.value;
deletedNode = Optional.of(rightTreeMinNode);
} else {
if (null == targetNode.parentNode) {
if (null != targetNode.leftNode) {
MyAVLTree.this.rootNode = targetNode.leftNode;
} else {
MyAVLTree.this.rootNode = targetNode.rightNode;
}
MyAVLTree.this.rootNode.parentNode = null;
} else {
if (null != targetNode.leftNode) {
if (targetNode == targetNode.parentNode.leftNode) {
targetNode.parentNode.leftNode = targetNode.leftNode;
} else {
targetNode.parentNode.rightNode = targetNode.leftNode;
}
} else {
if (targetNode == targetNode.parentNode.leftNode) {
targetNode.parentNode.leftNode = targetNode.rightNode;
} else {
targetNode.parentNode.rightNode = targetNode.rightNode;
}
}
deletedNode = Optional.of(targetNode);
}
}
return deletedNode;
}
/**
* 使用中序遍历方式展示所有数据
*/
private void middleOrderShow(AVLNode node) {
if (null == node) return;
middleOrderShow(node.leftNode);
System.out.print(node.value + " ");
middleOrderShow(node.rightNode);
}
/**
* 添加元素时使用的 调整并查找可能存在的失衡节点 方法
*
* @param node 初始值为新增节点
* @return 返回可能存在的失衡节点
*/
@SuppressWarnings("unchecked")
private Optional<AVLNode> adjustAndFindForADD(AVLNode node) {
if (null == node.parentNode) {
return Optional.empty();
}
if (node == node.parentNode.rightNode) {
node.parentNode.balance++;
} else {
node.parentNode.balance--;
}
if (0 == node.parentNode.balance) {
return Optional.empty();
} else if (2 == Math.abs(node.parentNode.balance)) {
return Optional.of(node.parentNode);
} else {
return adjustAndFindForADD(node.parentNode);
}
}
/**
* 删除元素时使用的 调整并查找可能存在的失衡节点 方法
*
* @param node 初始值为被删除节点
* @return 返回可能存在的失衡节点
*/
private Optional<AVLNode> adjustAndFindForDEL(AVLNode node) {
if (null == node.parentNode) {
return Optional.empty();
}
node = node.parentNode;
node.balance = calculateBalance(node);
if (2 == Math.abs(node.balance)) {
return Optional.of(node);
} else {
return adjustAndFindForDEL(node);
}
}
/**
* 恢复平衡操作
*
* @param unbalancedNode 失衡节点
* @param originalNode 如果是添加节点导致的失衡则对应为新增节点；
* 如果是删除节点，通过searchOriginNode方法获取，并且该值可能为null，即只需进行最终的旋转而无需调整
*/
private void restoreBalance(AVLNode unbalancedNode, AVLNode originalNode) {
if (null != originalNode) {
AVLNode node = originalNode.parentNode;
while (node != unbalancedNode) {
int balance = node.balance;
int parentBalance = node.parentNode.balance;
if ((balance < 0 && parentBalance > 0) || (balance > 0 && parentBalance < 0)) {
if (parentBalance < 0) { //左旋
leftRotate(node);
} else { //右旋
rightRotate(node);
}
}
node = node.parentNode;
}
}
if (unbalancedNode.balance < 0) { //右旋
rightRotate(unbalancedNode);
} else { //左旋
leftRotate(unbalancedNode);
}
}
/**
* 左旋
*
* @param unbalancedNode 失衡节点
*/
private void leftRotate(AVLNode unbalancedNode) {
//1.以下是需要处理的节点
AVLNode newRootNode = unbalancedNode.rightNode; //用来取代原来unbalancedNode的位置
AVLNode parentNode = unbalancedNode.parentNode; //用来作为newRootNode的父节点
AVLNode leftNode = newRootNode.leftNode; //用来作旋转后unbalancedNode的新右节点
//2.进行节点调整
if (null != parentNode) {
if (unbalancedNode == parentNode.leftNode) {
parentNode.leftNode = newRootNode;
} else {
parentNode.rightNode = newRootNode;
}
}
newRootNode.parentNode = parentNode;
newRootNode.leftNode = unbalancedNode;
unbalancedNode.parentNode = newRootNode;
if (null != leftNode) {
leftNode.parentNode = unbalancedNode;
}
unbalancedNode.rightNode = leftNode;
//3.重新计算balance（balance发生变动的只有newRootNode和unbalancedNode）
newRootNode.balance = calculateBalance(newRootNode);
unbalancedNode.balance = calculateBalance(unbalancedNode);
}
/**
* 右旋
*
* @param unbalancedNode 失衡节点
*/
private void rightRotate(AVLNode unbalancedNode) {
AVLNode newRootNode = unbalancedNode.leftNode;
AVLNode parentNode = unbalancedNode.parentNode;
AVLNode rightNode = newRootNode.rightNode;
if (null != parentNode) {
if (unbalancedNode == parentNode.leftNode) {
parentNode.leftNode = newRootNode;
} else {
parentNode.rightNode = newRootNode;
}
}
newRootNode.parentNode = parentNode;
newRootNode.rightNode = unbalancedNode;
unbalancedNode.parentNode = newRootNode;
rightNode.parentNode = unbalancedNode;
unbalancedNode.leftNode = rightNode;
newRootNode.balance = calculateBalance(newRootNode);
unbalancedNode.balance = calculateBalance(unbalancedNode);
}
/**
* 计算给定节点的balance值
* balance = 右子树高 - 左子树高
*
* @param node 给定的节点
* @return 计算得到的balance值
*/
private int calculateBalance(AVLNode node) {
int leftTreeHeight = calculateTreeHeight(node.leftNode);
int rightTreeHeight = calculateTreeHeight(node.rightNode);
return rightTreeHeight - leftTreeHeight;
}
/**
* 计算以给定节点为根节点的树高
* 树高 = max(左子树高， 右子树高)
*
* @param node 给定节点
* @return 树高
*/
private int calculateTreeHeight(AVLNode node) {
if (null == node) return 0;
int leftTreeHeight = 1, rightTreeHeight = 1;
if (null != node.leftNode) {
leftTreeHeight += calculateTreeHeight(node.leftNode);
}
if (null != node.rightNode) {
rightTreeHeight += calculateTreeHeight(node.rightNode);
}
return Math.max(leftTreeHeight, rightTreeHeight);
}
private AVLNode searchMinNode(AVLNode node) {
if (null == node.leftNode) return node;
return searchMinNode(node.leftNode);
}
/**
* 删除节点时，使用从上往下的方式来获取节点调整的初始值
*
* @param node 初始值为失衡节点
* @return 可能存在的初始节点
*/
private Optional<AVLNode> searchOriginNode(AVLNode node) {
Optional<AVLNode> originNode = Optional.empty();
while (0 != node.balance) {
if (node.balance > 0) {
node = node.rightNode;
if (node.balance < 0) {
originNode = Optional.of(node.leftNode);
}
} else {
node = node.leftNode;
if (node.balance > 0) {
originNode = Optional.of(node.rightNode);
}
}
}
return originNode;
}
}
private AVLNode rootNode;
public void add(Comparable value) {
AVLNode newNode = new AVLNode(value);
if (null == this.rootNode) {
this.rootNode = newNode;
} else {
//1.先将节点加到树中
this.rootNode.addNode(newNode);
//2.调整balance并获取可能存在的失衡节点
Optional<AVLNode> unbalancedNode = this.rootNode.adjustAndFindForADD(newNode);
//3.如果存在失衡点则进行恢复平衡操作
unbalancedNode.ifPresent(node -> {
this.rootNode.restoreBalance(node, newNode);
//4.如果失衡点是根节点，那么需要更新根节点，这一步很重要
if (node == this.rootNode) {
this.rootNode = this.rootNode.parentNode;
}
});
}
}
public AVLNode search(Comparable value) {
if (null == this.rootNode) return null;
Optional<AVLNode> targetNode = this.rootNode.searchNode(value);
return targetNode.orElse(null);
}
public void remove(Comparable value) {
if (null == this.rootNode) return;
AVLNode targetNode = search(value);
if (null == targetNode) return;
// 1.先删除节点
Optional<AVLNode> deletedNode = this.rootNode.removeNode(targetNode);
deletedNode.ifPresent(delNode -> {
// 2.调整balance并获取可能存在的失衡节点
Optional<AVLNode> unbalancedNode = this.rootNode.adjustAndFindForDEL(delNode);
if (unbalancedNode.isPresent()) { //如果存在失衡节点
AVLNode node = unbalancedNode.get(); //失衡节点
// 3.首先获取节点调整的初始点，如添加元素时，新增的节点就是初始点
Optional<AVLNode> originNode = this.rootNode.searchOriginNode(node);
// 4.对失衡节点进行恢复平衡操作
this.rootNode.restoreBalance(node, originNode.orElse(null));
// 5.判断失衡节点是否是根节点
if (node == this.rootNode) {
this.rootNode = this.rootNode.parentNode;
}
}
});
}
public void show() {
if (null == this.rootNode) return;
System.out.print("[ ");
this.rootNode.middleOrderShow(this.rootNode);
System.out.print("]");
System.out.println();
}
}
- 删除节点测试代码
package structure;
import org.junit.Test;
import structure.tree.MyAVLTree;
public class MyAVLTreeTest {
@Test
public void test() {
MyAVLTree avl = new MyAVLTree();
Comparable[] values;
values = new Comparable[]{90};
for (Comparable value : values) {
avl.add(value);
}
System.out.print("删除前：");
avl.show();
System.out.println();
avl.remove(90);
System.out.print("删除后：");
avl.show();
for (Comparable value : values) {
show(avl.search(value));
}
}
private void show(MyAVLTree.AVLNode node) {
if (null != node) {
System.out.println();
System.out.println(" " + node.value);
System.out.println(" / \\");
if (null != node.leftNode) {
System.out.print(" " + node.leftNode.value);
} else {
System.out.print(" ");
}
if (null != node.rightNode) {
System.out.print(" " + node.rightNode.value);
}
System.out.println();
System.out.println("~~~~~~~~~~~~~~");
}
}
}
3.6.2.2 测试添加节点
- 测试 1-1（命名方式同例4-1）
values = new Comparable[]{5, 2, 1};
[ 1 2 5 ]
5
/ \
~~~~~~~~~~~~~~
2
/ \
1 5
~~~~~~~~~~~~~~
1
/ \
~~~~~~~~~~~~~~
- 测试 1-2
values = new Comparable[]{5, 1, 2};
[ 1 2 5 ]
5
/ \
~~~~~~~~~~~~~~
1
/ \
~~~~~~~~~~~~~~
2
/ \
1 5
~~~~~~~~~~~~~~
- 测试 2-1
values = new Comparable[]{5, 3, 6, 2, 1};
[ 1 2 3 5 6 ]
5
/ \
2 6
~~~~~~~~~~~~~~
3
/ \
~~~~~~~~~~~~~~
6
/ \
~~~~~~~~~~~~~~
2
/ \
1 3
~~~~~~~~~~~~~~
1
/ \
~~~~~~~~~~~~~~
- 测试 2-2
values = new Comparable[]{5, 3, 6, 1, 2};
[ 1 2 3 5 6 ]
5
/ \
2 6
~~~~~~~~~~~~~~
3
/ \
~~~~~~~~~~~~~~
6
/ \
~~~~~~~~~~~~~~
1
/ \
~~~~~~~~~~~~~~
2
/ \
1 3
~~~~~~~~~~~~~~
- 测试 3-1
values = new Comparable[]{90, 50, 100, 30, 60, 10};
[ 10 30 50 60 90 100 ]
90
/ \
60 100
~~~~~~~~~~~~~~
50
/ \
30 90
~~~~~~~~~~~~~~
100
/ \
~~~~~~~~~~~~~~
30
/ \
10
~~~~~~~~~~~~~~
60
/ \
~~~~~~~~~~~~~~
10
/ \
~~~~~~~~~~~~~~
- 测试 3-2
values = new Comparable[]{90, 50, 100, 30, 60, 40};
[ 30 40 50 60 90 100 ]
90
/ \
60 100
~~~~~~~~~~~~~~
50
/ \
40 90
~~~~~~~~~~~~~~
100
/ \
~~~~~~~~~~~~~~
30
/ \
~~~~~~~~~~~~~~
60
/ \
~~~~~~~~~~~~~~
40
/ \
30
~~~~~~~~~~~~~~
- 测试 4-1
values = new Comparable[]{90, 50, 100, 30, 60, 55};
[ 30 50 55 60 90 100 ]
90
/ \
60 100
~~~~~~~~~~~~~~
50
/ \
30
~~~~~~~~~~~~~~
100
/ \
~~~~~~~~~~~~~~
30
/ \
~~~~~~~~~~~~~~
60
/ \
~~~~~~~~~~~~~~
55
/ \
50 90
~~~~~~~~~~~~~~
- 测试 4-2
values = new Comparable[]{90, 50, 100, 30, 60, 65};
[ 30 50 60 65 90 100 ]
90
/ \
65 100
~~~~~~~~~~~~~~
50
/ \
30
~~~~~~~~~~~~~~
100
/ \
~~~~~~~~~~~~~~
30
/ \
~~~~~~~~~~~~~~
60
/ \
50 90
~~~~~~~~~~~~~~
65
/ \
~~~~~~~~~~~~~~
3.6.2.3 测试删除节点
3.6.2.3.1 删除根节点
- 无子节点时
values = new Comparable[]{2};
删除前：[ 2 ]
avl.remove(2);
删除后：
- 只有一个子节点时
values = new Comparable[]{5, 2};
删除前：[ 2 5 ]
avl.remove(5);
删除后：[ 2 ]
2
/ \
~~~~~~~~~~~~~~
- 有两个子节点时
values = new Comparable[]{5, 2, 9, 6};
删除前：[ 2 5 6 9 ]
avl.remove(5);
删除后：[ 2 6 9 ]
2
/ \
~~~~~~~~~~~~~~
9
/ \
~~~~~~~~~~~~~~
6
/ \
2 9
~~~~~~~~~~~~~~
3.6.2.3.2 删除非根节点
- 没有子节点时
values = new Comparable[]{90, 50, 100, 30, 60, 95, 35, 55, 65};
删除前：[ 30 35 50 55 60 65 90 95 100 ]
avl.remove(95);
删除后：[ 30 35 50 55 60 65 90 100 ]
90
/ \
60 100
~~~~~~~~~~~~~~
50
/ \
30 90
~~~~~~~~~~~~~~
100
/ \
~~~~~~~~~~~~~~
30
/ \
35
~~~~~~~~~~~~~~
60
/ \
55 65
~~~~~~~~~~~~~~
35
/ \
~~~~~~~~~~~~~~
55
/ \
~~~~~~~~~~~~~~
65
/ \
~~~~~~~~~~~~~~
- 只有一个子节点时
values = new Comparable[]{90, 50, 100, 30, 60, 95, 35};
删除前：[ 30 35 50 60 90 95 100 ]
avl.remove(100);
删除后：[ 30 35 50 60 90 95 ]
90
/ \
60 95
~~~~~~~~~~~~~~
50
/ \
35 90
~~~~~~~~~~~~~~
30
/ \
~~~~~~~~~~~~~~
60
/ \
~~~~~~~~~~~~~~
95
/ \
~~~~~~~~~~~~~~
35
/ \
30
~~~~~~~~~~~~~~
- 有两个子节点时
values = new Comparable[]{90, 50, 100, 105, 60, 55, 65};
删除前：[ 50 55 60 65 90 100 105 ]
avl.remove(60);
删除后：[ 50 55 65 90 100 105 ]
90
/ \
55 100
~~~~~~~~~~~~~~
50
/ \
~~~~~~~~~~~~~~
100
/ \
105
~~~~~~~~~~~~~~
105
/ \
~~~~~~~~~~~~~~
55
/ \
50 65
~~~~~~~~~~~~~~
65
/ \
~~~~~~~~~~~~~~
3.7 其他语言实现
3.7.1 Python代码实现
class Node:
def __init__(self, value):
self.value = value
self.left_node = None
self.right_node = None
self.parent_node = None
self.balance = 0
def add_node(self, node):
if node.value < self.value:
if not self.left_node:
node.parent_node = self
self.left_node = node
else:
self.left_node.add_node(node)
elif node.value > self.value:
if not self.right_node:
node.parent_node = self
self.right_node = node
else:
self.right_node.add_node(node)
def search_node(self, value):
if value == self.value:
return self
elif value < self.value and self.left_node:
return self.left_node.search_node(value)
elif value > self.value and self.right_node:
return self.right_node.search_node(value)
else:
return None
"""返回一个二元组，第一个数据为删除根结点情况返回的新的根节点，第二个数据为被删除的数据"""
def remove_node(self, target_node, root_node=None) -> (object, object):
if not target_node.left_node and not target_node.right_node:
"""如果被删除的节点没有左节点也没有右节点"""
if not target_node.parent_node: # 如果删除的是根节点
return None, target_node
else:
if target_node == target_node.parent_node.left_node:
target_node.parent_node.left_node = None
else:
target_node.parent_node.right_node = None
return root_node, target_node
elif target_node.left_node and target_node.right_node:
"""如果被删除的节点有左节点也有右节点"""
right_tree_min_node = self.search_min_node(target_node.right_node)
self.remove_node(right_tree_min_node)
target_node.value = right_tree_min_node.value
return [root_node, target_node][target_node == root_node], right_tree_min_node
else:
"""如果被删除的节点只有左节点或者只有右节点"""
if target_node.left_node: # 如果只有左节点时
if not target_node.parent_node: # 如果删除的是根节点
target_node.left_node.parent_node = None
return target_node.left_node, target_node
else:
if target_node == target_node.parent_node.left_node:
target_node.parent_node.left_node = target_node.left_node
else:
target_node.parent_node.right_node = target_node.left_node
return root_node, target_node
else:
if not target_node.parent_node:
target_node.right_node.parent_node = None
return target_node.right_node, target_node
else:
if target_node == target_node.parent_node.left_node:
target_node.parent_node.left_node = target_node.right_node
else:
target_node.parent_node.right_node = target_node.right_node
return root_node, target_node
def adjust_and_find_for_add(self, node):
if not node.parent_node:
return None
if node == node.parent_node.right_node:
node.parent_node.balance += 1
else:
node.parent_node.balance -= 1
if 0 == node.parent_node.balance:
return None
if 2 == abs(node.parent_node.balance):
return node.parent_node
else:
return self.adjust_and_find_for_add(node.parent_node)
def adjust_and_find_for_del(self, node):
if not node.parent_node:
return None
node.parent_node.balance = self.calculate_balance(node.parent_node)
if 2 == abs(node.parent_node.balance):
return node.parent_node
else:
self.adjust_and_find_for_del(node.parent_node)
def restore_balance(self, unbalanced_node, origin_node):
if origin_node: # 删除节点时存在无需进行调整情况，所以有了此处的判断
"""先进行调整操作"""
node = origin_node.parent_node
while node != unbalanced_node:
if node.balance * node.parent_node.balance < 0:
if node.parent_node.balance < 0:
self.left_rotate(node)
else:
self.right_rotate(node)
node = node.parent_node
"""再进行最终旋转"""
if unbalanced_node.balance < 0:
self.right_rotate(unbalanced_node)
else:
self.left_rotate(unbalanced_node)
def left_rotate(self, unbalanced_node):
"""需要处理的3个节点"""
new_root_node = unbalanced_node.right_node
parent_node = unbalanced_node.parent_node
left_node = new_root_node.left_node
"""对这3个节点进行调整"""
if parent_node:
if unbalanced_node == parent_node.left_node:
parent_node.left_node = new_root_node
else:
parent_node.right_node = new_root_node
new_root_node.parent_node = parent_node
new_root_node.left_node = unbalanced_node
unbalanced_node.parent_node = new_root_node
if left_node:
left_node.parent_node = unbalanced_node
unbalanced_node.right_node = left_node
"""重新计算unbalanced_node和new_root_node的balance"""
new_root_node.balance = self.calculate_balance(new_root_node)
unbalanced_node.balance = self.calculate_balance(unbalanced_node)
def right_rotate(self, unbalanced_node):
new_root_node = unbalanced_node.left_node
parent_node = unbalanced_node.parent_node
right_node = new_root_node.right_node
if parent_node:
if unbalanced_node == parent_node.left_node:
parent_node.left_node = new_root_node
else:
parent_node.right_node = new_root_node
new_root_node.parent_node = parent_node
new_root_node.right_node = unbalanced_node
unbalanced_node.parent_node = new_root_node
if right_node:
right_node.parent_node = unbalanced_node
unbalanced_node.left_node = right_node
new_root_node.balance = self.calculate_balance(new_root_node)
unbalanced_node.balance = self.calculate_balance(unbalanced_node)
def calculate_balance(self, node):
"""balance = node右子树高 - node左子树高"""
left_tree_height = self.calculate_tree_height(node.left_node)
right_tree_height = self.calculate_tree_height(node.right_node)
return right_tree_height - left_tree_height
def calculate_tree_height(self, node):
if not node:
return 0
left_tree_height = right_tree_height = 1
if node.left_node:
left_tree_height += self.calculate_tree_height(node.left_node)
if node.right_node:
right_tree_height += self.calculate_tree_height(node.right_node)
return max(right_tree_height, left_tree_height)
def search_min_node(self, node):
if not node.left_node:
return node
return node.left_node.search_min_node(node)
def search_origin_node(self, node):
origin_node = None
while 0 != node.balance:
if node.balance > 0:
node = node.right_node
if node.balance < 0:
origin_node = node.left_node
else:
node = node.left_node
if node.balance > 0:
origin_node = node.right_node
return origin_node
def middle_order_show(self, node):
if node:
self.middle_order_show(node.left_node)
print(node.value, end=", ")
self.middle_order_show(node.right_node)
class MyAVLTree:
root_node = None
def add(self, value):
new_node = Node(value)
if self.root_node is None:
self.root_node = new_node
else:
"""1.先将节点加入到树中"""
self.root_node.add_node(new_node)
"""2.调整并获取可能存在的失衡节点"""
unbalanced_node = self.root_node.adjust_and_find_for_add(new_node)
"""3.如果存在失衡节点则进行旋转恢复平衡操作"""
if unbalanced_node:
self.root_node.restore_balance(unbalanced_node, new_node)
if unbalanced_node == self.root_node: # 当失衡节点是根节点时需要对根节点进行更新
self.root_node = self.root_node.parent_node
def remove(self, value):
if self.root_node is None:
return
target_node = self.search(value)
if not target_node:
return
"""1.先删除节点"""
self.root_node, deleted_node = self.root_node.remove_node(target_node, root_node=self.root_node)
"""2.调整并获取可能存在的失衡节点"""
unbalanced_node = self.root_node.adjust_and_find_for_del(deleted_node)
"""3.如果存在失衡节点则进行旋转恢复平衡操作"""
if unbalanced_node:
origin_node = self.root_node.search_origin_node(unbalanced_node)
self.root_node.restore_balance(unbalanced_node, origin_node)
if unbalanced_node == self.root_node:
self.root_node = self.root_node.parent_node
def search(self, value):
if self.root_node is None:
return None
return self.root_node.search_node(value)
def show(self):
if self.root_node:
print('[', end='')
self.root_node.middle_order_show(self.root_node)
print(']')
print()
if __name__ == '__main__':
avl = MyAVLTree()
for value in [6, 3, 9, 2, 5, 1]:
avl.add(value)
print("删除前：")
avl.show() # [1, 2, 3, 5, 6, 9, ]
print()
avl.remove(5)
print("删除后：")
avl.show() # [1, 2, 3, 6, 9, ]
3.7.2 JavaScript代码实现
function Node(value) {
this.value = value;
this.leftNode = null;
this.rightNode = null;
this.parentNode = null;
this.balance = 0;
}
Node.prototype.addNode = function (node) {
if (node.value < this.value) {
if (!this.leftNode) {
node.parentNode = this;
this.leftNode = node;
}
else this.leftNode.addNode(node);
} else if (node.value > this.value) {
if (!this.rightNode) {
node.parentNode = this;
this.rightNode = node;
}
else this.rightNode.addNode(node);
}
};
Node.prototype.searchNode = function (value) {
if (value === this.value) return this;
else if (value < this.value && this.leftNode) return this.leftNode.searchNode(value);
else if (value > this.value && this.rightNode) return this.rightNode.searchNode(value);
};
Node.prototype.adjustAndFindForAdd = function (originNode) {
if (!originNode.parentNode) return null;
if (originNode === originNode.parentNode.leftNode) originNode.parentNode.balance--;
else originNode.parentNode.balance++;
if (0 === originNode.parentNode.balance) return null;
else if (2 === Math.abs(originNode.parentNode.balance)) return originNode.parentNode;
else return this.adjustAndFindForAdd(originNode.parentNode);
};
Node.prototype.adjustAndFindForDel = function (originNode) {
if (!originNode.parentNode) return null;
let node = originNode.parentNode;
node.balance = this.calculateBalance(node);
if (2 === Math.abs(node.balance)) return node;
else return this.adjustAndFindForDel(node);
};
Node.prototype.restoreBalance = function (unbalancedNode, originNode) {
if (originNode) {
let node = originNode.parentNode;
while (node !== unbalancedNode) {
if (node.balance * node.parentNode.balance < 0) {
if (node.parentNode.balance < 0) this.leftRotate(node);
else this.rightRotate(node);
}
node = node.parentNode;
}
}
if (unbalancedNode.balance < 0) this.rightRotate(unbalancedNode);
else this.leftRotate(unbalancedNode);
};
Node.prototype.leftRotate = function (unbalancedNode) {
let newRootNode = unbalancedNode.rightNode;
let parentNode = unbalancedNode.parentNode;
let leftNode = newRootNode.leftNode;
if (parentNode) {
if (unbalancedNode === parentNode.leftNode) parentNode.leftNode = newRootNode;
else parentNode.rightNode = newRootNode;
}
newRootNode.parentNode = parentNode;
newRootNode.leftNode = unbalancedNode;
unbalancedNode.parentNode = newRootNode;
if (leftNode) leftNode.parentNode = unbalancedNode;
unbalancedNode.rightNode = leftNode;
newRootNode.balance = this.calculateBalance(newRootNode);
unbalancedNode.balance = this.calculateBalance(newRootNode);
};
Node.prototype.rightRotate = function (unbalancedNode) {
let newRootNode = unbalancedNode.leftNode;
let parentNode = unbalancedNode.parentNode;
let rightNode = newRootNode.rightNode;
if (parentNode) {
if (unbalancedNode === parentNode.leftNode) parentNode.leftNode = newRootNode;
else parentNode.rightNode = newRootNode;
}
newRootNode.parentNode = parentNode;
newRootNode.rightNode = unbalancedNode;
unbalancedNode.parentNode = newRootNode;
if (rightNode) rightNode.parentNode = unbalancedNode;
unbalancedNode.leftNode = rightNode;
newRootNode.balance = this.calculateBalance(newRootNode);
unbalancedNode.balance = this.calculateBalance(newRootNode);
};
Node.prototype.calculateBalance = function (node) {
let leftTreeHeight = this.calculateTreeHeight(node.leftNode);
let rightTreeHeight = this.calculateTreeHeight(node.rightNode);
return rightTreeHeight - leftTreeHeight;
};
Node.prototype.calculateTreeHeight = function (node) {
if (!node) return 0;
let leftTreeHeight = 1, rightTreeHeight = 1;
if (node.leftNode) leftTreeHeight += this.calculateTreeHeight(node.leftNode);
if (node.rightNode) rightTreeHeight += this.calculateTreeHeight(node.rightNode);
return Math.max(leftTreeHeight, rightTreeHeight);
};
Node.prototype.searchMinNode = function (node) {
if (!node.leftNode) return node;
else return this.searchMinNode(node.leftNode);
};
Node.prototype.searchOriginNode = function (node) {
let originNode;
while (0 !== node.balance) {
if (node.balance > 0) {
node = node.rightNode;
if (node.balance < 0) originNode = node.leftNode;
} else {
node = node.leftNode;
if (node.balance > 0) originNode = node.rightNode;
}
}
return originNode;
};
Node.prototype.middleOrderShow = function (node) {
if (!node) return;
this.middleOrderShow(node.leftNode);
console.log(node.value);
this.middleOrderShow(node.rightNode);
};
function MyAVLTree() {
this.rootNode = null;
}
MyAVLTree.prototype.add = function (value) {
let newNode = new Node(value);
if (!this.rootNode) this.rootNode = newNode;
else {
this.rootNode.addNode(newNode);
let unbalancedNode = this.rootNode.adjustAndFindForAdd(newNode);
if (unbalancedNode) {
this.rootNode.restoreBalance(unbalancedNode, newNode);
if (unbalancedNode === this.rootNode) this.rootNode = this.rootNode.parentNode;
}
}
};
MyAVLTree.prototype.search = function (value) {
if (this.rootNode) return this.rootNode.searchNode(value);
};
MyAVLTree.prototype.remove = function (value) {
if (!this.rootNode) return;
let targetNode = this.search(value);
if (!targetNode) return;
let deletedNode;
if (!targetNode.leftNode && !targetNode.rightNode) {
if (!targetNode.parentNode) {
this.rootNode = null;
return;
}
else {
if (targetNode === targetNode.parentNode.leftNode) targetNode.parentNode.leftNode = null;
else targetNode.parentNode.rightNode = null;
}
deletedNode = targetNode;
} else if (targetNode.leftNode && targetNode.rightNode) {
let rightTreeMinNode = this.rootNode.searchMinNode(targetNode.rightNode);
this.remove(rightTreeMinNode.value);
this.rootNode.value = rightTreeMinNode.value;
deletedNode = rightTreeMinNode;
} else {
if (!targetNode.parentNode) {
if (targetNode.leftNode) this.rootNode = targetNode.leftNode;
else this.rootNode = targetNode.rightNode;
this.rootNode.parentNode = null;
} else {
if (targetNode.leftNode) {
if (targetNode === targetNode.parentNode.leftNode) targetNode.parentNode.leftNode = targetNode.leftNode;
else targetNode.parentNode.rightNode = targetNode.leftNode;
} else {
if (targetNode === targetNode.parentNode.leftNode) targetNode.parentNode.leftNode = targetNode.rightNode;
else targetNode.parentNode.rightNode = targetNode.rightNode;
}
}
deletedNode = targetNode;
}
let unbalancedNode = this.rootNode.adjustAndFindForDel(deletedNode);
if (unbalancedNode) {
let originNode = this.rootNode.searchOriginNode(unbalancedNode);
this.rootNode.restoreBalance(unbalancedNode, originNode);
if (unbalancedNode === this.rootNode) this.rootNode = this.rootNode.parentNode;
}
};
MyAVLTree.prototype.show = function () {
if (this.rootNode) {
this.rootNode.middleOrderShow(this.rootNode);
}
};
let avl = new MyAVLTree();
[6, 3, 9, 2, 5, 1].forEach(value => avl.add(value));
console.log("删除前：");
avl.show(); // 1 2 3 5 6 9
console.log();
avl.remove(5);
console.log("删除后：");
avl.show(); // 1 2 3 6 9
本文地址：https://blog.csdn.net/oNightfall/article/details/108763151