当前位置：网站首页>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;
}
}
}
边栏推荐
- 分布式锁实现
- π disk, turning your computer into a personal private cloud
- HDU - 1501 Zipper（记忆化深搜）
- 异常检测方法梳理，看这篇就够了！
- jdbc-连接池
- SOE空间分析服务器 MySQL以及PostGres的地理空间库PostGIS防注入攻击
- 69 cesium code datasource loading geojson
- Cjc8988 Low Power Stereo codec with 2 stereo headphone drivers
- three. JS summary
- Pit of kotlin bit operation (bytes[i] and 0xff error)
猜你喜欢
蚂蚁新村田头村变甜头村 让厦门灌口镇田头村变甜头村的特色农产品之一是
MongoDB：一、MongoDB是什么？MongoDB的优缺点
Tidb database characteristics summary
![[file system] how to run squashfs on UBI](/img/d7/a4769420c510c47f3c2a615b514a8e.png)
[file system] how to run squashfs on UBI
Index method and random forest to realize the information of surface water body in wet season in Shandong Province
HCM Beginner (IV) - time
Transformer le village de tiantou en un village de betteraves sucrières
让厦门灌口镇田头村变甜头村的特色农产品之一是蚂蚁新村
无限水平大理石游戏
Database problems, how to optimize Oracle SQL query statements faster and more efficient
随机推荐
ABP 学习解决方案中的项目以及依赖关系
How does MySQL store Emoji?
让厦门灌口镇田头村变甜头村的特色农产品之一是蚂蚁新村
UOW of dev XPO comparison
Skywalking integrated Nacos dynamic configuration
three. JS summary
Freeswitch dial the extension number
SOE空间分析服务器 MySQL以及PostGres的地理空间库PostGIS防注入攻击
2022 年面向初学者的 10 大免费 3D 建模软件
Arcserver password reset (account cannot be reset)
交换机配置软件具有的作用
地宫取宝（记忆化深搜）
JDBC connection pool
[note] e-commerce order data analysis practice
68 Cesium代码datasource加载czml
HCM Beginner (IV) - time
PLA not pasted on the bed: 6 simple solutions
Ant new village is one of the special agricultural products that make Tiantou village in Guankou Town, Xiamen become Tiantou village
B-树系列
kotlin位运算的坑(bytes[i] and 0xff 报错)