当前位置：网站首页>AVL 平衡二叉搜索树
AVL 平衡二叉搜索树
2022-07-01 15:42:00 【颜 然】
二叉搜索树（BST）虽能缩短查找效率，但如果数据有序或接近有序，BST将退化为单支树，此时查找元素就相当于在顺序表中搜索元素，效率低下。
那么此时如果能保证每个结点的左右子树高度差的绝对值不超过1，就可以降低树的高度，从而减少平均搜索长度。所以AVL带着这个使命诞生了。
一、AVL
在二叉树中，如果每个结点的子树的高度差距为0、1或-1，则称这棵树是平衡二叉树，即AVL。
二、平衡二叉树
执行插入或删除操作后如果导致了AVL的不平衡，那么我们需要执行旋转操作来重新平衡这棵树。旋转操作主要有LL、RR、LR、RL四种类型。
1、LL
向左子树中的左孩子插入新结点后导致不平衡，此时需要右旋操作：
旋转后平衡二叉树将B看作新root， 将E结点与A.left相连，再将A与B.right相连，最后得到新的AVL。
private void balanceLL(AVLTreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.left;
if(A == root){
root = B;
}else{
if(parentOfA.left == A){
parentOfA.left = B;
}else{
parentOfA.right = B;
}
}
A.left = B.right;
B.right = A;
updateHeight((AVLTreeNode<E>) A);
2、RR
和LL相反，向右子树中的右孩子插入新结点后导致的不平衡，此时需要左旋操作：
private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B =A.right;
if(A == root){
root = B;
}else{
if(parentOfA.left == A){
parentOfA.left = B;
}else{
parentOfA.right = B;
}
}
A.right = B.left;
B.left = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
}3、LR
左儿子左旋，根结点右旋：
private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.left;
TreeNode C = B.right;
if(A == root){
root = C;
}else{
if(parentOfA.left == A){
parentOfA.left = C;
}else {
parentOfA.right = C;
}
}
A.left = C.right;
B.right = C.left;
C.left = B;
C.right = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}4、RL
右儿子右旋，根结点左旋：
private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.right;
TreeNode<E> C = B.left;
if(A == root){
root = C;
}else{
if(parentOfA.left == A){
parentOfA.left = C;
}else{
parentOfA.right = C;
}
}
A.right = C.left;
B.left = C.right;
C.left = A;
C.right = B;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}三、Java实现AVLTree类
AVLTree类继承BST类。
public class AVLTree<E extends Comparable<E>> extends BST<E>{
public AVLTree() {
}
public AVLTree(E[] objects) {
super(objects);
}
// 插入方法和BST中的方法一样，只不过每次添加后需要检查平衡
@Override
public boolean insert(E e){
boolean success = super.insert(e);
if(!success){
return false;
}else{
balancePath(e); // 检查是否需要平衡操作
}
return true;
}
private void updateHeight(AVLTreeNode<E> node){
if(node.left == null && node.right == null){
node.height = 0;
}else if(node.left == null){
node.height = 1 + ((AVLTreeNode<E>)(node.right)).height;
}else if(node.right == null){
node.height = 1 + ((AVLTreeNode<E>)(node.left)).height;
}else
node.height = 1 + Math.max(((AVLTreeNode<E>)(node.right)).height,((AVLTreeNode<E>)(node.left)).height);
}
// 平衡一条路径上的结点
private void balancePath(E e){
java.util.ArrayList<TreeNode<E>> path = path(e); // 获取包含e的结点到根结点的路径
for(int i = path.size() - 1; i >= 0; i--){
AVLTreeNode<E> A = (AVLTreeNode<E>)(path.get(i));
updateHeight(A); // 更新高度
AVLTreeNode<E> parentOfA = (A == root) ? null : (AVLTreeNode<E>)(path.get(i - 1));
switch(balanceFactor(A)){ // 检查平衡因子，检查是否需要旋转
case -2 :
if(balanceFactor((AVLTreeNode<E>)A.left) <= 0){
balanceLL(A,parentOfA);
}else{
balanceLR(A,parentOfA);
}
break;
case +2 :
if(balanceFactor((AVLTreeNode<E>)A.right) >= 0){
balanceRR(A, parentOfA);
}else{
balanceRL(A, parentOfA);
}
}
}
}
private int balanceFactor(AVLTreeNode<E> node){
if(node.left == null){
return -node.height;
}else if(node.left == null){
return +node.height;
}else
return ((AVLTreeNode<E>)node.right).height - ((AVLTreeNode<E>)node.left).height;
}
private void balanceLL(AVLTreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.left;
if(A == root){
root = B;
}else{
if(parentOfA.left == A){
parentOfA.left = B;
}else{
parentOfA.right = B;
}
}
A.left = B.right;
B.right = A;
updateHeight((AVLTreeNode<E>) A);
updateHeight((AVLTreeNode<E>) B);
}
private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.left;
TreeNode C = B.right;
if(A == root){
root = C;
}else{
if(parentOfA.left == A){
parentOfA.left = C;
}else {
parentOfA.right = C;
}
}
A.left = C.right;
B.right = C.left;
C.left = B;
C.right = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B =A.right;
if(A == root){
root = B;
}else{
if(parentOfA.left == A){
parentOfA.left = B;
}else{
parentOfA.right = B;
}
}
A.right = B.left;
B.left = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
}
private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.right;
TreeNode<E> C = B.left;
if(A == root){
root = C;
}else{
if(parentOfA.left == A){
parentOfA.left = C;
}else{
parentOfA.right = C;
}
}
A.right = C.left;
B.left = C.right;
C.left = A;
C.right = B;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
// 和BST中的删除方法一样，只不过需要判断下是否平衡
@Override
public boolean delete(E element){
if (root == null) {
return false;
}
TreeNode<E> parent = null;
TreeNode<E> current = root;
while(current != null){
if(element.compareTo(current.element) < 0){
parent = current;
current = current.left;
}else if(element.compareTo(current.element) > 0){
parent = current;
current = current.right;
}else break;
}
if(current == null){
return false;
}
if(current.left == null){
if(parent == null){
root = current.right;
}else {
if(element.compareTo(parent.element) < 0){
parent.left = current.right;
}else{
parent.right = current.right;
}
balancePath(parent.element);
}
}else{
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while(rightMost.right != null){
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
current.element = rightMost.element;
if(parentOfRightMost.right == rightMost){
parentOfRightMost.right = rightMost.left;
}else{
parentOfRightMost.left = rightMost.left;
}
balancePath(parentOfRightMost.element);
}
size--;
return true;
}
protected static class AVLTreeNode<E> extends BST.TreeNode<E>{
protected int height = 0;
public AVLTreeNode(E e){
super(e);
}
}
}四、测试AVLTree类
public class TestAVLTree {
public static void main(String[] args){
AVLTree<Integer> tree = new AVLTree<Integer>(new Integer[]{25, 20 ,5});
System.out.print("After inserting 25,20,,5: ");
printTree(tree);
tree.insert(34);
tree.insert(50);
System.out.print("\nAfter inserting 34, 50 : ");
printTree(tree);
tree.insert(30);
System.out.print("\nAfter inserting 30 : ");
printTree(tree);
tree.insert(10);
System.out.print("\nAfter inserting 10 : ");
printTree(tree);
tree.delete(34);
tree.delete(30);
tree.delete(50);
System.out.print("\nAfter removing 34, 30, 50: ");
printTree(tree);
tree.delete(5);
System.out.print("\nAfter removing 5 : ");
printTree(tree);
System.out.print("\nTraverse the element in the tree: ");
for(Object e : tree){
System.out.print(e + " ");
}
}
public static void printTree(BST tree){
System.out.print("\nInorder (sorted) : ");
tree.inorder();
System.out.print("\nPostorder : ");
tree.postorder();
System.out.print("\nPreorder");
tree.preorder();
System.out.print("\nThe number of nodes is " + tree.getSize());
System.out.println();
}
}程序插入图示：
程序删除图示：
边栏推荐
- 如何写出好代码 - 防御式编程指南
- Qt+pcl Chapter 6 point cloud registration ICP Series 2
- Deep operator overloading (2)
- Lean Six Sigma project counseling: centralized counseling and point-to-point counseling
- 【300+精选大厂面试题持续分享】大数据运维尖刀面试题专栏（三）
- Phpcms background upload picture button cannot be clicked
- 《QT+PCL第六章》点云配准icp系列3
- 远程办公经验？来一场自问自答的介绍吧~ | 社区征文
- 张驰咨询：家电企业用六西格玛项目减少客户非合理退货案例
- 你TM到底几点下班？！！！
猜你喜欢
Wechat official account subscription message Wx open subscribe implementation and pit closure guide
精益六西格玛项目辅导咨询：集中辅导和点对点辅导两种方式
Sort out the four commonly used sorting functions in SQL
STM32F4-TFT-SPI时序逻辑分析仪调试记录
Qt+pcl Chapter 6 point cloud registration ICP Series 2
三星率先投产3nm芯片，上海应届硕士生可直接落户，南开成立芯片科学中心，今日更多大新闻在此...
硬件开发笔记（九）: 硬件开发基本流程，制作一个USB转RS232的模块（八）：创建asm1117-3.3V封装库并关联原理图元器件
The newly born robot dog can walk by himself after rolling for an hour. The latest achievement of Wu Enda's eldest disciple
微信小程序02-轮播图实现与图片点击跳转
软件测试的可持续发展，必须要学会敲代码？
随机推荐
STM32F4-TFT-SPI时序逻辑分析仪调试记录
Wechat applet 03 - text is displayed from left to right, and the block elements in the line are centered
SAP s/4hana: one code line, many choices
[300 + selected interview questions from big companies continued to share] big data operation and maintenance sharp knife interview question column (III)
ABAP-屏幕切换时,刷新上一个屏幕
Qt+pcl Chapter 6 point cloud registration ICP series 4
Tableapi & SQL and Kafka message acquisition of Flink example
Redis high availability principle
选择在长城证券上炒股开户可以吗？安全吗？
Implementation of deploying redis sentry in k8s
Logical analysis of automatic decision of SAP CRM organization model
vim 从嫌弃到依赖(22)——自动补全
Photoshop plug-in HDR (II) - script development PS plug-in
二叉树的前序,中序,后续(非递归版本)
go-zero实战demo(一)
软件测试的可持续发展，必须要学会敲代码？
你TM到底几点下班？！！！
如何写出好代码 - 防御式编程指南
What time do you get off work?!!!
Gaussdb (for MySQL):partial result cache, which accelerates the operator by caching intermediate results