当前位置:网站首页>AVL balanced binary search tree
AVL balanced binary search tree
2022-07-01 15:52:00 【Yan Ran】
Binary search tree (BST) Although it can shorten the search efficiency , but If the data is in order or close to order ,BST take Degenerate into a single tree , At this point, searching for elements is equivalent to The order sheet Search elements in , inefficiency .
At this time, 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 can reduce the height of the tree , This reduces the average search length . therefore AVL With this mission was born .
One 、AVL
In a binary tree , If the height difference of the subtree of each node is 0、1 or -1, Call this tree a balanced binary tree , namely AVL.
Two 、 Balanced binary trees
If the insert or delete operation results in AVL The imbalance of , Then we need to perform a rotation operation to rebalance the tree . Rotation operations mainly include LL、RR、LR、RL Four types .
1、LL
towards The left child in the left subtree inserts New nodes lead to imbalance , At this time need Right hand operation :
After rotation, the balanced binary tree will B As new root, take E Node and A.left Connected to a , then A And B.right Connected to a , Finally get a new AVL.
private void balanceLL(AVLTreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.left;
if(A == root){
root = B;
}else{
if(parentOfA.left == A){
parentOfA.left = B;
}else{
parentOfA.right = B;
}
}
A.left = B.right;
B.right = A;
updateHeight((AVLTreeNode<E>) A);
2、RR
and LL contrary , towards The right child in the right subtree inserts Imbalance caused by new nodes , At this time need left-handed operation :
private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B =A.right;
if(A == root){
root = B;
}else{
if(parentOfA.left == A){
parentOfA.left = B;
}else{
parentOfA.right = B;
}
}
A.right = B.left;
B.left = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
}
3、LR
Left son left rotation , Root node dextral :
private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.left;
TreeNode C = B.right;
if(A == root){
root = C;
}else{
if(parentOfA.left == A){
parentOfA.left = C;
}else {
parentOfA.right = C;
}
}
A.left = C.right;
B.right = C.left;
C.left = B;
C.right = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
4、RL
Right son right rotation , Left rotation of root node :
private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.right;
TreeNode<E> C = B.left;
if(A == root){
root = C;
}else{
if(parentOfA.left == A){
parentOfA.left = C;
}else{
parentOfA.right = C;
}
}
A.right = C.left;
B.left = C.right;
C.left = A;
C.right = B;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
3、 ... and 、Java Realization AVLTree class
AVLTree Class inheritance BST class .
public class AVLTree<E extends Comparable<E>> extends BST<E>{
public AVLTree() {
}
public AVLTree(E[] objects) {
super(objects);
}
// Insertion method and BST In the same way , Just check the balance after each addition
@Override
public boolean insert(E e){
boolean success = super.insert(e);
if(!success){
return false;
}else{
balancePath(e); // Check whether balancing operation is required
}
return true;
}
private void updateHeight(AVLTreeNode<E> node){
if(node.left == null && node.right == null){
node.height = 0;
}else if(node.left == null){
node.height = 1 + ((AVLTreeNode<E>)(node.right)).height;
}else if(node.right == null){
node.height = 1 + ((AVLTreeNode<E>)(node.left)).height;
}else
node.height = 1 + Math.max(((AVLTreeNode<E>)(node.right)).height,((AVLTreeNode<E>)(node.left)).height);
}
// Balance the nodes on a path
private void balancePath(E e){
java.util.ArrayList<TreeNode<E>> path = path(e); // Get contains e The path from the node of to the root node
for(int i = path.size() - 1; i >= 0; i--){
AVLTreeNode<E> A = (AVLTreeNode<E>)(path.get(i));
updateHeight(A); // Update height
AVLTreeNode<E> parentOfA = (A == root) ? null : (AVLTreeNode<E>)(path.get(i - 1));
switch(balanceFactor(A)){ // Check the balance factor , Check if rotation is required
case -2 :
if(balanceFactor((AVLTreeNode<E>)A.left) <= 0){
balanceLL(A,parentOfA);
}else{
balanceLR(A,parentOfA);
}
break;
case +2 :
if(balanceFactor((AVLTreeNode<E>)A.right) >= 0){
balanceRR(A, parentOfA);
}else{
balanceRL(A, parentOfA);
}
}
}
}
private int balanceFactor(AVLTreeNode<E> node){
if(node.left == null){
return -node.height;
}else if(node.left == null){
return +node.height;
}else
return ((AVLTreeNode<E>)node.right).height - ((AVLTreeNode<E>)node.left).height;
}
private void balanceLL(AVLTreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.left;
if(A == root){
root = B;
}else{
if(parentOfA.left == A){
parentOfA.left = B;
}else{
parentOfA.right = B;
}
}
A.left = B.right;
B.right = A;
updateHeight((AVLTreeNode<E>) A);
updateHeight((AVLTreeNode<E>) B);
}
private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.left;
TreeNode C = B.right;
if(A == root){
root = C;
}else{
if(parentOfA.left == A){
parentOfA.left = C;
}else {
parentOfA.right = C;
}
}
A.left = C.right;
B.right = C.left;
C.left = B;
C.right = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B =A.right;
if(A == root){
root = B;
}else{
if(parentOfA.left == A){
parentOfA.left = B;
}else{
parentOfA.right = B;
}
}
A.right = B.left;
B.left = A;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
}
private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA){
TreeNode<E> B = A.right;
TreeNode<E> C = B.left;
if(A == root){
root = C;
}else{
if(parentOfA.left == A){
parentOfA.left = C;
}else{
parentOfA.right = C;
}
}
A.right = C.left;
B.left = C.right;
C.left = A;
C.right = B;
updateHeight((AVLTreeNode<E>)A);
updateHeight((AVLTreeNode<E>)B);
updateHeight((AVLTreeNode<E>)C);
}
// and BST The deletion method in is the same , Just need to judge whether it is balanced
@Override
public boolean delete(E element){
if (root == null) {
return false;
}
TreeNode<E> parent = null;
TreeNode<E> current = root;
while(current != null){
if(element.compareTo(current.element) < 0){
parent = current;
current = current.left;
}else if(element.compareTo(current.element) > 0){
parent = current;
current = current.right;
}else break;
}
if(current == null){
return false;
}
if(current.left == null){
if(parent == null){
root = current.right;
}else {
if(element.compareTo(parent.element) < 0){
parent.left = current.right;
}else{
parent.right = current.right;
}
balancePath(parent.element);
}
}else{
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while(rightMost.right != null){
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
current.element = rightMost.element;
if(parentOfRightMost.right == rightMost){
parentOfRightMost.right = rightMost.left;
}else{
parentOfRightMost.left = rightMost.left;
}
balancePath(parentOfRightMost.element);
}
size--;
return true;
}
protected static class AVLTreeNode<E> extends BST.TreeNode<E>{
protected int height = 0;
public AVLTreeNode(E e){
super(e);
}
}
}
Four 、 test AVLTree class
public class TestAVLTree {
public static void main(String[] args){
AVLTree<Integer> tree = new AVLTree<Integer>(new Integer[]{25, 20 ,5});
System.out.print("After inserting 25,20,,5: ");
printTree(tree);
tree.insert(34);
tree.insert(50);
System.out.print("\nAfter inserting 34, 50 : ");
printTree(tree);
tree.insert(30);
System.out.print("\nAfter inserting 30 : ");
printTree(tree);
tree.insert(10);
System.out.print("\nAfter inserting 10 : ");
printTree(tree);
tree.delete(34);
tree.delete(30);
tree.delete(50);
System.out.print("\nAfter removing 34, 30, 50: ");
printTree(tree);
tree.delete(5);
System.out.print("\nAfter removing 5 : ");
printTree(tree);
System.out.print("\nTraverse the element in the tree: ");
for(Object e : tree){
System.out.print(e + " ");
}
}
public static void printTree(BST tree){
System.out.print("\nInorder (sorted) : ");
tree.inorder();
System.out.print("\nPostorder : ");
tree.postorder();
System.out.print("\nPreorder");
tree.preorder();
System.out.print("\nThe number of nodes is " + tree.getSize());
System.out.println();
}
}
Program insertion diagram :
Program delete icon :
边栏推荐
- Wechat applet 01 bottom navigation bar settings
- 【OpenCV 例程200篇】216. 绘制多段线和多边形
- 跨平台应用开发进阶(二十四) :uni-app实现文件下载并保存
- Samsung took the lead in putting 3nm chips into production, and Shanghai's fresh master students can settle directly. Nankai has established a chip science center. Today, more big news is here
- Qt+pcl Chapter 6 point cloud registration ICP Series 2
- Research on manually triggering automatic decision of SAP CRM organization model with ABAP code
- MySQL advanced 4
- MySQL backup and restore single database and single table
- [Cloudera][ImpalaJDBCDriver](500164)Error initialized or created transport for authentication
- Description | Huawei cloud store "commodity recommendation list"
猜你喜欢
TensorFlow团队:我们没被抛弃
【一天学awk】条件与循环
Zhang Chi's class: several types and differences of Six Sigma data
软件测试的可持续发展,必须要学会敲代码?
Équipe tensflow: Nous ne sommes pas abandonnés
STM32F1与STM32CubeIDE编程实例-PWM驱动蜂鸣器生产旋律
What is the forkjoin framework in the concurrent programming series?
Redis high availability principle
Phpcms background upload picture button cannot be clicked
Automatic, intelligent and visual! Deeply convinced of the eight designs behind sslo scheme
随机推荐
[stm32-usb-msc problem help] stm32f411ceu6 (Weact) +w25q64+usb-msc flash uses SPI2 to read out only 520kb
Wechat applet 01 bottom navigation bar settings
新出生的机器狗,打滚1小时后自己掌握走路,吴恩达开山大弟子最新成果
Zhang Chi Consulting: household appliance enterprises use Six Sigma projects to reduce customers' unreasonable return cases
将ABAP On-Premises系统连接到中央检查系统以进行自定义代码迁移
Tanabata confession introduction: teach you to use your own profession to say love words, the success rate is 100%, I can only help you here ~ (programmer Series)
智慧党建: 穿越时空的信仰 | 7·1 献礼
说明 | 华为云云商店「商品推荐榜」
有些能力,是工作中学不来的,看看这篇超过90%同行
Introduction to RT thread env tool (learning notes)
vim 从嫌弃到依赖(22)——自动补全
Task.Run(), Task.Factory.StartNew() 和 New Task() 的行为不一致分析
[one day learning awk] function and user-defined function
Qt+pcl Chapter 6 point cloud registration ICP Series 5
【300+精选大厂面试题持续分享】大数据运维尖刀面试题专栏(三)
Qt+pcl Chapter 9 point cloud reconstruction Series 2
Task. Run(), Task. Factory. Analysis of behavior inconsistency between startnew() and new task()
Description | Huawei cloud store "commodity recommendation list"
【LeetCode】43. String multiplication
[cloud trend] new wind direction in June! Cloud store hot list announced