当前位置:网站首页>1.AVL树:左右旋-bite
1.AVL树:左右旋-bite
2022-07-06 23:30:00 【风生u】
AVL树的定义
左右子树的高度差的绝对值均不超过1的二叉搜索树.
有n个结点,时间复杂度是log以n为底2的对数;
AVL树的插入
左单旋:左旋就是旋转节点的右子树的左子树变为其新的右子树,同时旋转节点变成以前右子树的左子树
右端单旋:右旋就是旋转节点的左子树的右子树变成其新的左子树,同时旋转节点变成以前左子树的右子树
何时使用左旋,右旋,左右双旋,右左双选?
增加节点在要旋转节点的右子树的右子树上时:左旋,在要旋转节点的右子树的左子树上时:右左双旋.
增加节点在要旋转节点的左子树的左子树上时:右旋,在要旋转节点的左子树的右子树上时:左右双旋.
创建一个结点类:
public class TreeNode {
public int val;
public int bf;
public TreeNode left;
public TreeNode right;
public TreeNode parent;
public TreeNode(int val){
this.val = val;
}
}
插入元素:
public TreeNode root;//根节点
public boolean insert(int val) {
TreeNode node = new TreeNode(val);
if(root == null) {
root = node;
return true;
}
TreeNode parent = null;
TreeNode cur = root;
让node节点的双亲节点(parent)
while (cur != null) {
if(cur.val < val) {
parent = cur;
cur = cur.right;
}else if(cur.val == val) {
return false;
}else {
parent = cur;
cur = cur.left;
}
}
//cur == null
判断node,该插入parent的哪个子树.
if(parent.val < val) {
parent.right = node;
}else {
parent.left = node;
}
//
node.parent = parent;
cur = node;
// 平衡因子的修改
while (parent != null) {
//先看cur是parent的左还是右 决定平衡因子是++还是--
if(cur == parent.right) {
//如果是右树,那么右树高度增加 平衡因子++
parent.bf++;
}else {
//如果是左树,那么左树高度增加 平衡因子--
parent.bf--;
}
//检查当前的平衡因子 是不是绝对值 1 0 -1
if(parent.bf == 0) {
//说明已经平衡了
break;
}else if(parent.bf == 1 || parent.bf == -1) {
//继续向上去修改平衡因子
cur = parent;
parent = cur.parent;
}else {
if(parent.bf == 2) {
//右树高-》需要降低右树的高度
if(cur.bf == 1) {
//左旋
rotateLeft(parent);
}else {
//cur.bf == -1
//右左双旋
rotateRL(parent);
}
}else {
//parent.bf == -2 左树高-》需要降低左树的高度
if(cur.bf == -1) {
//右旋
rotateRight(parent);
}else {
//cur.bf == 1
//左右双旋
rotateLR(parent);
}
}
//上述代码走完就平衡了
break;
}
}
return true;
}
左单旋:左旋就是旋转节点的右子树的左子树变为其新的右子树,同时旋转节点变成以前右子树的左子树
private void rotateLeft(TreeNode parent) {
//获取左旋节点的右子树
TreeNode subR = parent.right;
//获取左旋节点的右子树的左子树
TreeNode subRL = subR.left;
//左旋节点的右子树变为左旋节点旧右子树的左子树
parent.right = subRL;
//旧右子树的左子树变为左旋节点
subR.left = parent;
//如果当前旧右子树的左子树不为空,则让其双亲节点指向左旋节点.
if(subRL != null) {
subRL.parent = parent;
}
//先保存左旋点的双亲节点,好让其指向subR
TreeNode pParent = parent.parent;
parent.parent = subR;
判断左旋节点是否是根节点
if(root == parent) {
root = subR;
root.parent = null;
}else {
//判断左旋节点是双亲节点的哪个节点.
if(pParent.left == parent) {
pParent.left = subR;
}else {
pParent.right = subR;
}
subR.parent = pParent;
}
//调整平衡因子
subR.bf = parent.bf = 0;
}
右端单旋:右旋就是旋转节点的左子树的右子树变成其新的左子树,同时旋转节点变成以前左子树的右子树
private void rotateRight(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
parent.left = subLR;
subL.right = parent;
//没有subLR
if(subLR != null) {
subLR.parent = parent;
}
//必须先记录
TreeNode pParent = parent.parent;
parent.parent = subL;
//检查 当前是不是就是根节点
if(parent == root) {
root = subL;
root.parent = null;
}else {
//不是根节点,判断这棵子树是左子树还是右子树
if(pParent.left == parent) {
pParent.left = subL;
}else {
pParent.right = subL;
}
subL.parent = pParent;
}
subL.bf = 0;
parent.bf = 0;
}
左右双旋:增加节点在要旋转节点的左子树的左子树上时:右旋,在要旋转节点的左子树的右子树上时:左右双旋.
private void rotateLR(TreeNode parent) {
TreeNode subL = parent.left;
TreeNode subLR = subL.right;
int bf = subLR.bf;
rotateLeft(parent.left);
rotateRight(parent);
//由dubLT.bf的值(-1/1)调整平衡因子.
if(bf == -1) {
subL.bf = 0;
subLR.bf = 0;
parent.bf = 1;
}else if(bf == 1){
subL.bf = -1;
subLR.bf = 0;
parent.bf = 0;
}
}
右左双旋:增加节点在要旋转节点的右子树的右子树上时:左旋,在要旋转节点的右子树的左子树上时:右左双旋.
//右左双旋
private void rotateRL(TreeNode parent) {
TreeNode subR = parent.right;
TreeNode subRL = subR.left;
int bf = subRL.bf;
rotateR(parent.right);
rotateL(parent);
if(bf == -1){
parent.bf = 0;
subR.bf = 0;
subRL.bf = 1;
}else if(bf == 1){
parent.bf = -1;
subR.bf = 0;
subRL.bf = 0;
}
}
判断是否是AVL树
private int height(TreeNode root) {
if(root == null) return 0;
int leftH = height(root.left);
int rightH = height(root.right);
return leftH > rightH ? leftH+1 : rightH+1;
}
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int leftH = height(root.left);
int rightH = height(root.right);
if(rightH-leftH != root.bf) {
System.out.println("这个节点:"+root.val+" 平衡因子异常");
return false;
}
return Math.abs(leftH-rightH) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}
AVL树的删除(待定)
边栏推荐
- Why JSON is used for calls between interfaces, how fastjson is assigned, fastjson 1.2 [email protected] Mapping relatio
- Safe landing practice of software supply chain under salesforce containerized ISV scenario
- Creation and use of thread pool
- 项目经理如何凭借NPDP证书逆袭?看这里
- DFS,BFS以及图的遍历搜索
- 一条 update 语句的生命经历
- ASP. Net MVC - resource cannot be found error - asp Net MVC – Resource Cannot be found error
- 创始人负债10亿,开课吧即将“下课”?
- 线程池的创建与使用
- 《四》表单
猜你喜欢
随机推荐
记录一次压测经验总结
DFS,BFS以及图的遍历搜索
SQL injection HTTP header injection
阿里云的神龙架构是怎么工作的 | 科普图解
人体传感器好不好用?怎么用?Aqara绿米、小米之间到底买哪个
最长不下降子序列(LIS)(动态规划)
As we media, what websites are there to download video clips for free?
《四》表单
Let f (x) = Σ x^n/n^2, prove that f (x) + F (1-x) + lnxln (1-x) = Σ 1/n^2
线程池的创建与使用
Understand common network i/o models
Pytest testing framework -- data driven
Safe landing practice of software supply chain under salesforce containerized ISV scenario
背包问题(01背包,完全背包,动态规划)
Use Zhiyun reader to translate statistical genetics books
10 distributed databases that take you to the galaxy
ScheduledExecutorService定时器
线程同步的两个方法
Error: No named parameter with the name ‘foregroundColor‘
How can professional people find background music materials when doing we media video clips?