当前位置：网站首页>高阶-二叉平衡树
高阶-二叉平衡树
2022-07-01 06:09:00 【qq_52025208】
一、AVL树
1.二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过
1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
2.一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
（1）它的左右子树都是AVL树
（2）左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
3.AVL树的实现
class AVTNode {
public int val;
public int bf;//平衡因子
public AVTNode left;
public AVTNode right;
public AVTNode par;
public AVTNode() {
}
public AVTNode(int val) {
this.val = val;
}
}
public class AVLTest {
public AVTNode root;
public boolean insert(int val) {
AVTNode node = new AVTNode(val);
if (root == null) {
root = node;
return true;
}
AVTNode par = null;
AVTNode cur = root;
while (cur != null) {
if (cur.val == val) {
return false;
} else if (cur.val > val) {
par = cur;
cur = cur.left;
} else {
par = cur;
cur = cur.right;
}
}
node.par = par;
//cur == null
if (par.val > val) {
par.left = node;
} else {
par.right = node;
}
//判断平衡因子
adjustBf(par,node);
return true;
}
private void adjustBf(AVTNode par, AVTNode node) {
while (Math.abs(par.bf) <= 1) {
if (par.left == node) {
par.bf++;
} else if (par.right == node) {
par.bf--;
}
//说明子树的高度没有改变
if (par.bf == 0) {
return;
}
if (par.bf == -1 || par.bf == 1) {
//子树的高度改变，判断父节点的父节点的bf有没有改变
node = par;
par = par.par;
if (par == null) {
//父节点的父节点为空，说明父节点是root
return;
}
}
if (par.bf == 2 || par.bf == -2) {
break;
}
}
//出现失衡情况
if (par.bf == 2) {
if (node.bf == 1) {
//左左失衡
rightRotate(par);
par.bf = node.bf = 0;//推导即可
} else {
//左右失衡
AVTNode c = node.right;
int condition;
if (par.right == null) {
condition = 1;
} else if (c.bf == 1) {
condition = 2;
} else {
condition = 3;
}
leftRotate(node);
rightRotate(par);
if (condition == 1) {
par.bf = node.bf = c.bf = 0;
} else if (condition == 2) {
par.bf = -1;
node.bf = c.bf = 0;
} else {
node.bf = 1;
par.bf = c.bf = 0;
}
}
} else {
if (node.bf == 1) {
//右左失衡
AVTNode c = node.left;
int condition;
if (par.left == null) {
condition = 1;
} else if (c.bf == 1) {
condition = 2;
} else {
condition = 3;
}
rightRotate(node);
leftRotate(par);
if (condition == 1) {
par.bf = node.bf = c.bf = 0;
} else if (condition == 2) {
node.bf = -1;
par.bf = c.bf = 0;
} else {
par.bf = 1;
node.bf = c.bf = 0;
}
} else {
//右右失衡
leftRotate(par);
par.bf = node.bf = 0;
}
}
}
//左旋
/** * 测试用例：6种 * node有父亲，node是父亲的left node有父亲，node是父亲的right * node没有父亲 * right节点的左子树是否为空 * @param node */
public void leftRotate(AVTNode node) {
AVTNode parent = node.par;//node可能存在的父亲节点
AVTNode right = node.right;//node.left
AVTNode rightOfLeft = right.left;
//进行左旋
right.par = parent;
if (parent == null) {
//parent==null说明node是根节点，交换之后right就是根节点
root = right;
} else {
if (node == parent.left) {
parent.left = right;
} else {
parent.right = right;
}
}
right.left = node;
node.par = right;
node.right = rightOfLeft;
if (rightOfLeft != null) {
rightOfLeft.par = node;
}
}
//右旋
public void rightRotate(AVTNode node) {
AVTNode parent = node.par;
AVTNode left = node.left;
AVTNode leftOfRight = left.right;
//进行右旋
left.par = parent;
if (parent == null) {
root = left;
} else {
if (node == parent.left) {
parent.left = left;
} else {
parent.right = left;
}
}
left.right = node;
node.par = left;
node.left = leftOfRight;
if (leftOfRight != null) {
leftOfRight.par = node;
}
}
public static void main(String[] args) {
AVLTest tree = new AVLTest();
AVTNode n1 = new AVTNode(5);
AVTNode n2 = new AVTNode(6);
AVTNode n3 = new AVTNode(7);
n1.right = n2;
n2.par = n1;
n2.right = n3;
n3.par = n2;
tree.leftRotate(n1);
System.out.println("hello");//打断点查看
}
}
4.AVL树的性能分析
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询
时高效的时间复杂度，即 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要
维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要
一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修
改，就不太适合。
二、红黑树
1.红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
2.红黑树的性质
（1） 每个结点不是红色就是黑色
（2）根节点是黑色的
（3）如果一个节点是红色的，则它的两个孩子结点是黑色的
（4）对于每个结点，从该结点到其所有后代叶结点的简单路径上，均 包含相同数目的黑色结点
（5）每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
3.红黑树的实现
public class RBTreeNode {
public long val;
public RBTreeNode left;
public RBTreeNode right;
public RBTreeNode parent;
public boolean color;
public static final boolean BLACK = true;
public static final boolean RED = false;
public RBTreeNode(long val, RBTreeNode parent, boolean color) {
this.val = val;
this.left = this.right = null;
this.parent = parent;
this.color = color;
}
}
public class RBTree {
public RBTreeNode root = null;
//节点的个数
public int size = 0;
public boolean insert(long val) {
if (root == null) {
root = new RBTreeNode(val,null,BLACK);
size++;
return true;
}
RBTreeNode parent = null;
RBTreeNode cur = root;
while (cur != null) {
if (val == cur.val) {
return false;
} else if (val < cur.val) {
parent = cur;
cur = cur.left;
} else {
parent = cur;
cur = cur.right;
}
}
//cur == null,插入的节点一定是红色
RBTreeNode node = new RBTreeNode(val,parent,RED);
if (val < parent.val) {
parent.left = node;
} else {
parent.right = node;
}
size++;
//因为parent节点一定是红色的，所以要进行调整
adjustBalance(node);
return true;
}
private void adjustBalance(RBTreeNode node) {
while (true) {
RBTreeNode parent = node.parent;
if (parent == null) {
//是根节点
break;
}
if (parent.color == BLACK) {
break;
}
//parent.color = RED,进行调整
RBTreeNode grandPa = parent.parent;
if (parent == grandPa.left) {
RBTreeNode uncle = grandPa.right;
if (uncle != null && uncle.color == RED) {
parent.color = uncle.color = BLACK;
grandPa.color = RED;
node = grandPa;
continue;
} else {
//判断grandPa和parent的关系 ，parent和node的关系
if (node == parent.right) {
//左旋
leftRotate(parent);
parent = node;
}
rightRotate(grandPa);
parent.color = BLACK;
grandPa.color = RED;
break;
}
} else {
RBTreeNode uncle = grandPa.left;
if (uncle != null && uncle.color == RED) {
parent.color = uncle.color = BLACK;
grandPa.color = RED;
node = grandPa;
continue;
} else {
if (node == parent.left) {
rightRotate(parent);
parent = node;
}
leftRotate(grandPa);
parent.color = BLACK;
grandPa.color = RED;
break;
}
}
}
//不管根节点的颜色是什么，一律改为黑色
root.color = BLACK;
}
private void rightRotate(RBTreeNode m) {
RBTreeNode parent = m.parent;
RBTreeNode left = m.left;
RBTreeNode leftOfRight = left.right;
left.parent = parent;
if (parent == null) {
root = left;
} else {
if (m == parent.left) {
parent.left = left;
} else {
parent.right = left;
}
}
left.right = m;
m.parent = left;
m.left = leftOfRight;
if (leftOfRight != null) {
leftOfRight.parent = m;
}
}
private void leftRotate(RBTreeNode m) {
RBTreeNode parent = m.parent;
RBTreeNode right = m.right;
RBTreeNode rightOfLeft = right.left;
right.parent = parent;
if (parent == null) {
root = right;
} else {
if (m == parent.left) {
parent.left = right;
} else {
parent.right = right;
}
}
right.left = m;
m.parent = right;
m.right = rightOfLeft;
if (rightOfLeft != null) {
rightOfLeft.parent = m;
}
}
}
边栏推荐
- MongoDB：一、MongoDB是什么？MongoDB的优缺点
- Pychart configuring jupyter
- Code shoe set - mt3149 · and - the data is not very strong. Violent pruning can deceive AC
- Ant new village is one of the special agricultural products that make Tiantou village in Guankou Town, Xiamen become Tiantou village
- 【企业数据安全】升级备份策略 保障企业数据安全
- Fragment upload and breakpoint resume
- excel動態圖錶
- 68 Cesium代码datasource加载czml
- Save data in browser to local file
- What if the data in the cloud disk is harmonious?
猜你喜欢
excel動態圖錶
【ManageEngine卓豪】网络运维管理是什么,网络运维平台有什么用
linux 关闭redis 进程 systemd+
Database problems, how to optimize Oracle SQL query statements faster and more efficient
分布式锁实现
ONEFLOW source code parsing: automatic inference of operator signature
机械臂速成小指南（六）：步进电机驱动器
![[note] e-commerce order data analysis practice](/img/03/367756437be947b5b995d5f7f55236.png)
[note] e-commerce order data analysis practice
DHT11 温湿度传感器
Ant new village is one of the special agricultural products that make Tiantou village in Guankou Town, Xiamen become Tiantou village
随机推荐
Small guide for rapid completion of mechanical arm (VI): stepping motor driver
IT服务管理（ITSM）在高等教育领域的应用
Tidb database characteristics summary
π disk, turning your computer into a personal private cloud
OpenGL es: (1) origin of OpenGL es (transfer)
地宮取寶（記憶化深搜）
数据库er图组成要素
c＃ Xml帮助类
基于LabVIEW的计时器
Understanding of C manualresetevent class
SOE spatial analysis server MySQL and PostGIS geospatial database of Postgres anti injection attack
Ant new village is one of the special agricultural products that make Tiantou village in Guankou Town, Xiamen become Tiantou village
1034 Head of a Gang
Freeswitch dial the extension number
Geoffrey Hinton: my 50 years of in-depth study and Research on mental skills
相同区域 多源栅格数据 各个像元行列号一致，即行数列数相同，像元大小相同
C XML help class
excel動態圖錶
Make: g++: command not found
HDU - 1501 Zipper（记忆化深搜）