您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

算法--平衡二叉树AVL原理分析以及代码实现

时间:2019-10-15 10:54:33  来源:  作者:

前文介绍了,二叉树、二叉排序树,需要了解的不妨关注下小JIA。

 

算法--平衡二叉树AVL原理分析以及代码实现

 

 

AVL是一种高度平衡的二叉排序树。对于任意节点左子树与右子树高度差不超过1,AVL的高度与节点数量为O(logn)关系。平衡因子等于左子树高度减去右子树高度。AVL所有节点的平衡因子只可能是-1、0、1。因此当添加元素或删除元素时有可能会破会这种平衡,所以需要维护。失去平衡主要有四种情况,分别为LLLRRRRL

 

AVL 的节点定义

public class AVLTreeNode<T extends Comparable<T>> {
 private T key; //关键字(键值)
 private int height; //高度
 private AVLTreeNode<T> left; //左孩子
 private AVLTreeNode<T> right; //右孩子
 public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
 this.key = key;
 this.left = left;
 this.right = right;
 this.height = 0;
 }
 ......
 }

LL

LL,平衡因子大于1,左子树平衡因子大于等于0,需要将A顺时针向下右旋转,B做为父节点

 

算法--平衡二叉树AVL原理分析以及代码实现

 

 

右旋转操作,首先保存B右子树K3,将A做为B的右子树,K3做为A的左孩子,并更新A,B的高度值,完成旋转。

 

算法--平衡二叉树AVL原理分析以及代码实现

 

/* LL:左旋转 */
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> node) {
 AVLTreeNode<T> tempNode;
 
 tempNode = node.getLeft();
 node.setLeft(tempNode.getRight());
 tempNode.setRight(node);
 
 node.setHeight(max(height(node.getLeft()), height(node.getRight())) + 1);
 tempNode.setHeight(max(height(tempNode.getLeft()), node.getHeight()) + 1);
 return tempNode;
}

 

RR

RR,平衡因子小于-1,右子树平衡因子小于等于0,需要将A逆时针向下左旋转,B做为父节点

 

算法--平衡二叉树AVL原理分析以及代码实现

 

 

左旋转操作,首先保存B左子树K2,将A做为B的左子树,K2做为B的右孩子,并更新A、B的高度值,完成旋转

 

算法--平衡二叉树AVL原理分析以及代码实现

 

/* RR:右旋转 */
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> node) {
 AVLTreeNode<T> tempNode;
 
 tempNode = node.getRight();
 node.setRight(tempNode.getLeft());
 tempNode.setLeft(node);
 node.setHeight(max( height(node), height(node.getRight())) + 1);
 tempNode.setHeight(max( height(tempNode.getRight()), node.getHeight()) + 1);
 return tempNode;
}

 

LR

LR,平衡因子大于1,左子树平衡因子小于0,首先将B进行左旋转,在将A进行右旋转

 

算法--平衡二叉树AVL原理分析以及代码实现

 

/* LR:左双旋转 */
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> node) {
 node.setLeft(rightRightRotation(node.getLeft()));
 return leftLeftRotation(node);
}

 

RL

RL,平衡因子大于-1,右子树平衡因子大于0,首先将B进行右旋转,在将A进行左旋转

 

算法--平衡二叉树AVL原理分析以及代码实现

 

/* RL:右双旋转 */
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> node) {
 node.setRight(leftLeftRotation(node.getRight()));
 return rightRightRotation(node);
}

 

插入节点

原则:根据二叉查找树BST的规定插入数据,再来判断是否失去平衡;若失去平衡再根据文上介绍的旋转规则平衡数据;最后再设置树高。

/* 将结点插入到AVL树中 */
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
 if (tree == null) {
 //新建节点
 tree = new AVLTreeNode<T>(key, null, null);
 } else {
 int cmp = key.compareTo(tree.getKey());
 if (cmp < 0) { //将key插入到tree的左子树
 tree.setLeft(insert(tree.getLeft(), key));
 
 //插入节点后,若AVL树失去平衡,则进行相应的调节。
 if (height(tree.getLeft()) - height(tree.getRight()) > 1) {
 if (key.compareTo(tree.getLeft().getKey()) < 0)
 tree = leftLeftRotation(tree);
 else
 tree = leftRightRotation(tree);
 }
 } else if (cmp > 0) {//将key插入到tree的右子树
 tree.setRight(insert(tree.getRight(), key)); 
 
 //插入节点后,若AVL树失去平衡,则进行相应的调节。
 if (height(tree.getRight()) - height(tree.getLeft()) > 1) {
 if (key.compareTo(tree.getRight().getKey()) > 0)
 tree = rightRightRotation(tree);
 else
 tree = rightLeftRotation(tree);
 }
 }
 }
 tree.setHeight(max(height(tree.getLeft()), height(tree.getRight())) + 1);
 return tree;
}

 

删除节点

同理,先找到删除节点的位置,再进行AVL平衡调节。找到要删除的节点Z后,如果Z的左右孩子都非空,

a)若Z的左子树高于右子树,找出左子树中的最大节点K(maxNum方法),使用K的值替换掉Z的值,并删除K;

b)若Z的左子树矮于或等于右子树,找出右子树中最小节点K(minNum方法),使用K的值替换掉Z的值,并删除K。

这种方式的好处是删除后AVL树仍然是平衡的。

/* 删除结点 */
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> delNode) {
 //根为空 或者 没有要删除的节点,直接返回null。
 if (tree == null || delNode == null)
 return null;
 int cmp = delNode.getKey().compareTo(tree.getKey());
 if (cmp < 0) { //待删除的节点在tree的左子树中
 tree.setLeft(remove(tree.getLeft(), delNode));
 
 // 删除节点后,若AVL树失去平衡,则进行相应的调节。
 if (height(tree.getRight()) - height(tree.getLeft()) > 1) {
 AVLTreeNode<T> r = tree.getRight();
 if (height(r.getLeft()) > height(r.getRight()))
 tree = rightLeftRotation(tree);
 else
 tree = rightRightRotation(tree);
 }
 } else if (cmp > 0) { //待删除的节点在tree的右子树中
 tree.setRight(remove(tree.getRight(), delNode));
 
 // 删除节点后,若AVL树失去平衡,则进行相应的调节。
 if (height(tree.getLeft()) - height(tree.getRight()) > 1) {
 AVLTreeNode<T> l = tree.getLeft();
 if (height(l.getRight()) > height(l.getLeft()))
 tree = leftRightRotation(tree);
 else
 tree = leftLeftRotation(tree);
 }
 } else { // tree是对应要删除的节点。
 // tree的左右孩子都非空
 if ((tree.getLeft() != null) && (tree.getRight() != null)) { 
 //如果tree的左子树比右子树高;
 if (height(tree.getLeft()) > height(tree.getRight())) { 
 AVLTreeNode<T> max = maxNum(tree.getLeft());
 tree.setKey(max.getKey());
 tree.setLeft(remove(tree.getLeft(), max));
 //如果tree的左子树矮于或等于右子树
 } else {
 AVLTreeNode<T> min = minNum(tree.getRight());
 tree.setKey(min.getKey());
 tree.setRight(remove(tree.getRight(), min));
 }
 } else {
 AVLTreeNode<T> tmpNode = tree;
 tree = (tree.getLeft() != null) ? tree.getLeft() : tree.getRight();
 tmpNode = null;
 }
 }
 return tree;
}


Tags:平衡二叉树 算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前文介绍了,二叉树、二叉排序树,需要了解的不妨关注下小JIA。 AVL是一种高度平衡的二叉排序树。对于任意节点左子树与右子树高度差不超过1,AVL的高度与节点数量为O(logn)关系。...【详细内容】
2019-10-15  Tags: 平衡二叉树 算法  点击:(109)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条