当前位置：网站首页>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();
}
}程序插入图示：
程序删除图示：
边栏推荐
- 自动、智能、可视！深信服SSLO方案背后的八大设计
- Detailed explanation of stm32adc analog / digital conversion
- An intrusion detection model
- 你TM到底几点下班？！！！
- 硬件开发笔记（九）: 硬件开发基本流程，制作一个USB转RS232的模块（八）：创建asm1117-3.3V封装库并关联原理图元器件
- SAP S/4HANA: 一条代码线，许多种选择
- [STM32 learning] w25qxx automatic judgment capacity detection based on STM32 USB storage device
- TensorFlow团队：我们没被抛弃
- Tableapi & SQL and Kafka message insertion in Flink
- A unifying review of deep and shallow anomaly detection
猜你喜欢
An intrusion detection model
一次革命、两股力量、三大环节：《工业能效提升行动计划》背后的“减碳”路线图...
![[pyGame practice] do you think it's magical? Pac Man + cutting fruit combine to create a new game you haven't played! (source code attached)](/img/0a/c1a4b57b9729e0cf9de1feae9f8c19.png)
[pyGame practice] do you think it's magical? Pac Man + cutting fruit combine to create a new game you haven't played! (source code attached)
采集数据工具推荐，以及采集数据列表详细图解流程
Wechat official account subscription message Wx open subscribe implementation and pit closure guide
The newly born robot dog can walk by himself after rolling for an hour. The latest achievement of Wu Enda's eldest disciple
Returning to the top of the list, the ID is still weak
Pico, can we save consumer VR?
"Qt+pcl Chapter 6" point cloud registration ICP Series 6
《QT+PCL第六章》点云配准icp系列6
随机推荐
RT-Thread Env 工具介绍（学习笔记）
ABAP-调用Restful API
Wechat official account subscription message Wx open subscribe implementation and pit closure guide
Survey of intrusion detection systems:techniques, datasets and challenges
【目标跟踪】|STARK
Wechat applet 02 - Implementation of rotation map and picture click jump
[300 + selected interview questions from big companies continued to share] big data operation and maintenance sharp knife interview question column (III)
她就是那个「别人家的HR」｜ONES 人物
Tensorflow team: we haven't been abandoned
综述 | 激光与视觉融合SLAM
STM32F4-TFT-SPI时序逻辑分析仪调试记录
Create employee data in SAP s/4hana by importing CSV
三星率先投产3nm芯片，上海应届硕士生可直接落户，南开成立芯片科学中心，今日更多大新闻在此...
[target tracking] |stark
Gaussdb (for MySQL):partial result cache, which accelerates the operator by caching intermediate results
远程办公经验？来一场自问自答的介绍吧~ | 社区征文
TS reports an error don't use 'object' as a type The `object` type is currently hard to use
ABAP-屏幕切换时,刷新上一个屏幕
ThinkPHP advanced
HR面试：最常见的面试问题和技巧性答复