当前位置：网站首页>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;
}
}
}
边栏推荐
- 1034 Head of a Gang
- 68 Cesium代码datasource加载czml
- B-树系列
- Diffusion (multi-source search)
- Stack Title: parsing Boolean expressions
- Multi label lsml for essay learning records
- SystemVerilog learning-10-validation quantification and coverage
- OpenGL es: (1) origin of OpenGL es (transfer)
- 【ManageEngine卓豪】局域网监控的作用
- 让厦门灌口镇田头村变甜头村的特色农产品之一是蚂蚁新村
猜你喜欢
Pla ne colle pas sur le lit: 6 solutions simples
69 Cesium代码datasource加载geojson
FPGA - clocking -02- clock wiring resources of internal structure of 7 Series FPGA
ONEFLOW source code parsing: automatic inference of operator signature
![[summary of knowledge points] chi square distribution, t distribution, F distribution](/img/a6/bb5cabbfffb0edc9449c4c251354ae.png)
[summary of knowledge points] chi square distribution, t distribution, F distribution
Skywalking integrated Nacos dynamic configuration
IT服务管理（ITSM）在高等教育领域的应用
What if the data in the cloud disk is harmonious?
Linux closes the redis process SYSTEMd+
Teach you how to implement a deep learning framework
随机推荐
Kubedm builds kubenetes cluster (Personal Learning version)
C＃ ManualResetEvent 类的理解
蚂蚁新村田头村变甜头村 让厦门灌口镇田头村变甜头村的特色农产品之一是
交换机配置软件具有的作用
【文件系统】如何在ubi之上运行squashfs
【ManageEngine卓豪】用统一终端管理助“欧力士集团”数字化转型
Thoughts on a "01 knapsack problem" expansion problem
无限水平大理石游戏
Stack Title: parsing Boolean expressions
连续四年入选Gartner魔力象限，ManageEngine卓豪是如何做到的？
DEV XPO对比之XAF BO
π disk, turning your computer into a personal private cloud
c＃ Xml帮助类
69 Cesium代码datasource加载geojson
HDU - 1501 Zipper（记忆化深搜）
Freeswitch dial the extension number
Small guide for rapid completion of mechanical arm (VI): stepping motor driver
kotlin位运算的坑(bytes[i] and 0xff 报错)
端口扫描工具是什么？端口扫描工具有什么用
Smartinstantiationawarebeanpostprocessor of the extension point series determines which construction method to execute - Chapter 432