当前位置：网站首页>High order binary balanced tree
High order binary balanced tree
2022-07-01 06:20:00 【qq_ fifty-two million twenty-five thousand two hundred and eight】
One 、AVL Trees
1. Although binary search tree can shorten the search efficiency , However, if the data is ordered or close to ordered, the binary search tree will degenerate into a single branch tree , Finding elements is equivalent to searching for elements in the sequence table , inefficiency .
When a new node is inserted into the binary search tree , If we can ensure that the absolute value of the height difference between the left and right subtrees of each node does not exceed
1( You need to adjust the nodes in the tree ), You can reduce the height of the tree , This reduces the average search length .
2. A tree AVL Trees or empty trees , Or a binary search tree with the following properties ：
（1） Its left and right subtrees are AVL Trees
（2） The difference between the height of the left and right subtrees ( It's called equilibrium factor ) The absolute value of is not more than 1(-1/0/1)
3.AVL Implementation of tree
class AVTNode {
public int val;
public int bf;// Balance factor
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;
}
// Judge the balance factor
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--;
}
// It shows that the height of the subtree has not changed
if (par.bf == 0) {
return;
}
if (par.bf == -1 || par.bf == 1) {
// The height of the subtree changes , Determine the parent node of the parent node bf Has it changed
node = par;
par = par.par;
if (par == null) {
// The parent node of the parent node is empty , The parent node is root
return;
}
}
if (par.bf == 2 || par.bf == -2) {
break;
}
}
// There is an imbalance
if (par.bf == 2) {
if (node.bf == 1) {
// Left left imbalance
rightRotate(par);
par.bf = node.bf = 0;// Derivation is enough
} else {
// Left right imbalance
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) {
// Right left imbalance
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 {
// Right right imbalance
leftRotate(par);
par.bf = node.bf = 0;
}
}
}
// left-handed
/** * The test case ：6 Kind of * node There's a father ,node It's my father's left node There's a father ,node It's my father's right * node No father * right Whether the left subtree of the node is empty * @param node */
public void leftRotate(AVTNode node) {
AVTNode parent = node.par;//node Possible parent nodes
AVTNode right = node.right;//node.left
AVTNode rightOfLeft = right.left;
// To carry on the left-hand
right.par = parent;
if (parent == null) {
//parent==null explain node Root node , After the exchange right It's the root node
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;
}
}
// Right hand
public void rightRotate(AVTNode node) {
AVTNode parent = node.par;
AVTNode left = node.left;
AVTNode leftOfRight = left.right;
// To carry on the right hand
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");// Break point view
}
}
4.AVL Performance analysis of tree
AVL The tree is an absolutely balanced binary search tree , It requires that the absolute value of the height difference between the left and right subtrees of each node should not exceed 1, This ensures that the query
Time efficient time complexity , namely . But if you want to be right AVL The tree does some structure modification , Very poor performance , such as ： To insert
Maintain its absolute balance , The number of rotations is more , Worse, when deleting , It is possible to keep the rotation up to the root . therefore ： if necessary
A query efficient and orderly data structure , And the number of data is static ( That will not change ), You can consider AVL Trees , But a structure is often repaired
Change , It's not suitable for .
Two 、 Red and black trees
1. Red and black trees , It's a binary search tree , But add a memory bit to each node to represent the color of the node , It can be Red or Black. By restricting the coloring method of each node in any path from root to leaf , The red and black trees make sure that no path is twice as long as the others , So it's close to equilibrium .
2. Properties of red black trees
（1） Each node is either red or black
（2） The root node is black
（3） If a node is red , Then its two child nodes are black
（4） For each node , A simple path from this node to all its descendant leaf nodes , all Contains the same number of black nodes
（5） Every leaf node is black ( The leaf node here refers to the empty node )
3. The realization of red and black tree
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;
// Number of nodes
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, The inserted node must be red
RBTreeNode node = new RBTreeNode(val,parent,RED);
if (val < parent.val) {
parent.left = node;
} else {
parent.right = node;
}
size++;
// because parent The node must be red , So make adjustments
adjustBalance(node);
return true;
}
private void adjustBalance(RBTreeNode node) {
while (true) {
RBTreeNode parent = node.parent;
if (parent == null) {
// Root node
break;
}
if (parent.color == BLACK) {
break;
}
//parent.color = RED, Adjustment
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 {
// Judge grandPa and parent The relationship between ,parent and node The relationship between
if (node == parent.right) {
// left-handed
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;
}
}
}
// No matter what the color of the root node is , All changed to black
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;
}
}
}
边栏推荐
- jdbc-连接池
- The row and column numbers of each pixel of multi-source grid data in the same area are the same, that is, the number of rows and columns are the same, and the pixel size is the same
- How does MySQL store Emoji?
- MySQL里记录货币
- Thoughts on a "01 knapsack problem" expansion problem
- 利用百度地图查询全国地铁线路
- Tidb database characteristics summary
- 数据库产生死锁了请问一下有没有解决办法
- 端口扫描工具对企业有什么帮助？
- golang panic recover自定义异常处理
猜你喜欢
Uniapp tree level selector
C＃ ManualResetEvent 类的理解
Database problems, how to optimize Oracle SQL query statements faster and more efficient
68 Cesium代码datasource加载czml
Transformer le village de tiantou en un village de betteraves sucrières
ForkJoin和Stream流测试
DHT11 温湿度传感器
Multi label lsml for essay learning records
【KV260】利用XADC生成芯片温度曲线图
ManageEngine卓豪助您符合ISO 20000标准（四）
随机推荐
地宫取宝（记忆化深搜）
ForkJoin和Stream流测试
Small guide for rapid completion of mechanical arm (VI): stepping motor driver
Ant new village is one of the special agricultural products that make Tiantou village in Guankou Town, Xiamen become Tiantou village
让田头村变甜头村的特色农产品是仙景芋还是白菜
Stack Title: parsing Boolean expressions
Pla ne colle pas sur le lit: 6 solutions simples
69 Cesium代码datasource加载geojson
OpenGL es: (3) EGL, basic steps of EGL drawing, eglsurface, anativewindow
机械臂速成小指南（六）：步进电机驱动器
Golang panic recover custom exception handling
HDU - 1501 Zipper（记忆化深搜）
JDBC connection pool
Top 10 Free 3D modeling software for beginners in 2022
记磁盘扇区损坏导致的Mysql故障排查
Factorial divisor (unique decomposition theorem)
UOW of dev XPO comparison
SOE spatial analysis server MySQL and PostGIS geospatial database of Postgres anti injection attack
[file system] how to run squashfs on UBI
HCM Beginner (I) - Introduction