数据结构AVL树,java中树数据结构
这篇文章带给你一些关于java的知识，包括关于平衡二叉树(AVL树)的知识。AVL树本质上是一个具有平衡功能的二叉查找树。下面就来看看吧，希望对你有帮助。
如何解决写爬虫IP受阻的问题？立即使用。
AVL树的引入
搜索二叉树具有极高的搜索效率，但在搜索二叉树时会出现以下极端情况：
这种二叉树搜索效率甚至低于链表。在搜索二叉树的基础上出现的平衡二叉树(AVL树)解决了这个问题。当平衡二叉树(AVL树)中一个节点的左右子树的高度差的绝对值大于1时，它们之间的高度差会通过旋转减小。
基本概念
AVL树本质上是一个二叉查找树。其特点是：
首先，这是一个二叉查找树。每个节点的左右子树的高度差的绝对值(平衡因子)最多为1。也就是说，AVL树本质上是一个具有平衡功能的二叉查找树(二叉树，二叉查找树)。插入或删除节点时，某个节点的左右子树高度差的绝对值大于1。这时候二叉树需要通过左右手操作再次平衡。平衡因子(balanceFactor)
节点的左子树和右子树之间的高度差。AVL树中任意节点的BF只能是-1，0，1。
基础设计
以下是AVL树所需的简单方法和属性：
公共类AVLTree扩展比较{
类节点{
e值；
节点向左；
节点右移；
int高度；
公共节点(){}
公共节点(E值){
this.value=value
高度=1；
left=null
右=空；
}
公共void显示(){
system . out . print(this . value )；
}
}
节点根；
int大小；
public int size(){
返回大小；
}
public int getHeight(Node node) {
if(node==null)返回0；
返回node.height
}
//获取平衡因子(左右子树的高度差，大小1或0为平衡，大小大于1为不平衡)
public int getBalanceFactor(){
返回getBalanceFactor(root)；
}
public int getBalanceFactor(Node Node){
if(node==null)返回0；
返回get height(node . left)-get height(node . right)；
}
//判断一棵树是否是平衡二叉树。
public boolean isBalance(节点node){
if(node==null)返回true
int balance factor=math . ABS(getbalance factor(node . left)-getbalance factor(node . right))；
if(balanceFactor 1)返回false
return is balance(node . left)is balance(node . right)；
}
public boolean isBalance(){
return is balance(root)；
}
//以中间顺序遍历树
private void inPrevOrder(节点根){
if(root==null)返回；
in pre order(root . left)；
root . display()；
inPrevOrder(root . right)；
}
public void in pre order(){
System.out.print(中间顺序遍历：)；
inPrevOrder(root)；
}}
RR(左旋)
在一棵树的右边子树中插入一个节点，导致二叉树变得不平衡，如下图。将5插入平衡二叉树会导致树变得不平衡。此时，需要左手操作，如下所示：
代码如下：
//左转，返回新的根节点
公共节点leftRotate(节点node){
system . out . println( left rotate )；
Node cur=node.right
node . right=cur . left；
cur.left=节点；
//用新节点的高度和cur
node . height=math . max(get height(node . left)，get height(node . right))1；
cur . height=math . max(getHeight(cur . left)，getHeight(cur . right))1；
返回cur
}
LL(右旋)
在AVL树的左子树的左子树中插入一个节点会导致二叉树变得不平衡，如下图。将2插入平衡二叉树会导致树变得不平衡。此时，需要左手操作，如下所示：
代码如下：
//右旋，并且返回新的根节点
公共节点右旋转(节点节点){
系统。出去。println(右旋转)；
节点cur=node.left
节点。左=当前。对；
cur.right=节点
//跟新结节和坏蛋的高度
节点。身高=数学。max(获取高度(节点。左)，获取高度(节点。右))1；
诅咒。身高=数学。max(getHeight(cur。left)、getHeight(cur。右))1；
返回坏蛋
}
LR(先左旋再右旋)
往平衡二叉树树左子树的右子树上插入一个节点，导致该树不再平衡，需要先对左子树进行左旋，再对整棵树右旋，如下图所示，插入节点为5.
RL(先右旋再左旋)
往平衡二叉树树右子树的左子树上插入一个节点，导致该树不再平衡，需要先对右子树进行右旋，再对整棵树左旋，如下图所示，插入节点为2.
添加节点
//添加元素
public void add(E e){
root=add(root，e)；
}
公共节点添加（节点节点，E值){
if (node==null) {
尺寸；
返回新节点（值);
}
如果(值。与(节点进行比较。值)0){
node.right=add(node.right，value)；
} else if(值。与(节点进行比较。值)0){
node.left=add(node.left，value)；
}
//跟新节点高度
节点。身高=数学。max(获取高度(节点。左)，获取高度(节点。右))1；
//获取当前节点的平衡因子
int balance factor=get balance factor(node)；
//该子树不平衡且新插入节点（导致不平衡的节点)在左子树的左子树上，此时需要进行右旋
if(平衡因子1 getbalance因子(节点。left)=0){
返回右旋转(节点);
}
//该子树不平衡且新插入节点（导致不平衡的节点)在右子树子树的右子树上，此时需要进行左旋
else if(平衡因子-1 getbalance因子(节点。right)=0){
返回左旋转(节点);
}
//该子树不平衡且新插入节点（导致不平衡的节点)在左子树的右子树上，此时需要先对左子树左旋，在整个树右旋
else if(平衡因子1 getbalance factor(节点。左)0){
节点。left=向左旋转(节点。左)；
返回右旋转(节点);
}
//平衡因子-1 getbalance因子(节点。左)0
//该子树不平衡且新插入节点（导致不平衡的节点)在右子树的左子树上，此时需要先对右子树右旋，再整个树左旋
else if(平衡因子-1 getbalance因子(节点。右)0){
节点。右=右旋转(节点。对)；
返回左旋转(节点);
}
返回节点；
}
删除节点
//删除节点
公共E移除(E值){
root=删除(根，值);
if(root==null){
返回空
}
返回根值
}
公共节点删除（节点节点，E值){
节点retNode=null
if(node==null)
返回retNode
如果(值。与(节点进行比较。值)0){
node.right=remove(node.right，value)；
retNode=节点；
}
else if(值。与(节点进行比较。值)0){
node.left=remove(node.left，value)；
retNode=节点；
}
//值。与(节点进行比较。值)=0
否则{
//左右节点都为空，或者左节点为空
if(node.left==null){
尺寸-;
retNode=node.right
}
//右节点为空
else if(node.right==null){
尺寸-;
retNode=node.left
}
//左右节点都不为空
否则{
节点继任者=新节点();
//寻找右子树最小的节点
节点cur=node.right
while(cur.left！=null){
cur=cur.left
}
继任者。值=当前值。价值；
successor . right=remove(node . right，value)；
successor . left=node . left；
node . left=node . right=null；
retNode=后继者；
}
if(retNode==null)
返回null
//维护二叉树平衡
//具有新的高度
retnode . height=math . max(get height(retnode . left)，get height(retnode . right))；
}
int balance factor=getbalance factor(retNode)；
//这个子树不平衡，新插入的节点(导致不平衡的节点)在左子树的左子树上。此时需要右转。
if(balance factor 1 getbalance factor(retnode . left)=0){
返回right rotate(retNode)；
}
//这个子树不平衡，新插入的节点(导致不平衡的节点)在右边子树的右边子树上。这时候就需要左转了。
else if(balance factor-1 getbalance factor(retnode . right)=0){
返回left rotate(retNode)；
}
//这个子树不平衡，新插入的节点(导致不平衡的节点)在左子树的右子树上。这时候就需要左转到左子树，右转到整棵树。
else if(balance factor 1 getbalance factor(retnode . left)0){
retnode . left=left rotate(retnode . left)；
返回right rotate(retNode)；
}
//这个子树不平衡，新插入的节点(导致不平衡的节点)在右子树的左子树上。这个时候，右边的子树需要先右转，然后整棵树需要左转。
else if(balance factor-1 getbalance factor(retnode . right)0){
retnode . right=right rotate(retnode . right)；
返回left rotate(retNode)；
}
返回retNode
}推荐学习：以上《java视频教程》是Java数据结构AVL树讲解的详细内容。更多请关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。