Data structures and algorithms - Balanced binary tree (AVL tree)

Introduction to the

Balanced binary trees, also known as AVL trees, are derived to optimize the sorting of extreme cases of binary trees (from small to large or from large to small inserts, in a chain shape)

The characteristics of

1. Based on sorting binary trees

2. The height difference between the left and right subtrees of any node is less than 2

Therefore, like sorting binary trees, balancing binary trees only requires balancing during insertion and deletion, so that the height difference between the left and right subtrees is less than 1

The query

The query process of all binary sorting trees is consistent, including balanced binary trees and red-black trees, which are all queried down through dichotomy. You can refer to the query of binary sorting trees

Node basic data structure

typedef struct TreeNode {
    int data;
    struct TreeNode *parentNode;
    struct TreeNode *l, *r;
}LSTreeNode;
Copy the code

rotating

Rotation is the ultimate solution to the problem of not being able to self-balance after the addition and deletion process is complete, which is used in both balanced binary trees and red-black trees

So rotations are something you need to know before you can understand insert and delete, see the previous chapter on rotations of binary trees

Left-handed code

void swapLeftRotation(LSTreeNode *parentNode, LSTreeNode *rightNode) {
    int data = parentNode->data;
    parentNode->data = rightNode->data;
    rightNode->data = data;
    parentNode->r = rightNode->r;
    rightNode->r->parentNode = parentNode;
    rightNode->r = rightNode->l;
    rightNode->l = parentNode->l;
    if (parentNode->l) parentNode->l->parentNode = rightNode;
    parentNode->l = rightNode;
}
Copy the code

The right code

void swapRightRotation(LSTreeNode *parentNode, LSTreeNode *leftNode) {
    int data = parentNode->data;
    parentNode->data = leftNode->data;
    leftNode->data = data;
    parentNode->l = leftNode->l;
    leftNode->l->parentNode = parentNode;
    leftNode->l = leftNode->r;
    leftNode->r = parentNode->r;
    if (parentNode->r) parentNode->r->parentNode = leftNode;
    parentNode->r = leftNode;
}
Copy the code

Types of imbalance and means of balance

Before balancing binary tree inserts and deletions, you must know the types of imbalances and how to balance them

Once the balanced binary tree is out of balance, there will be four types of balance: LL, LR, RR and RL

The LL type and LR type are symmetrical to RR type and RL type respectively

LL type

That is, the left branch of the left child node of the specified node is higher than the right branch of the specified node, resulting in imbalance

As shown in the following figure, are the common states of LL type imbalance state

As shown in the figure above, their imbalance contrast points are all at node A, and the height difference between the left and right subtrees reaches 2, where the child node is empty (the right child node of A), and the height is 0

Note: If B, F, and G nodes do not exist at the same time, then the result is the same except for the rotation with empty nodes

Treatment: direct dextrorotation (i.e., dextrorotation of AC)

The transformation results are shown in the figure below

LR type

That is, the branch of the right child node of the left child node of a specified node is higher than that of the right branch of the specified node, resulting in imbalance

As shown in the following figure, are the common states of LR type imbalance state

As shown in the figure above, their imbalance contrast points are all at node A, and the height difference between the left and right subtrees reaches 2. (It is found that this state cannot be balanced by directly right-handed rotation to AC)

Note: If B, D, and G nodes do not exist at the same time, then the result is the same but the rotation with empty nodes, which will not be covered here

Treatment scheme: first sinistral and then dextrorotatory (i.e., sinistral for CF and dextral for AF)

The transformation results are shown in the figure below

The RR type

That is, the specified node with child nodes has branches of child nodes, and the height is higher than the left branch of the specified node, resulting in imbalance

As shown in the following figure, these are the common states of RR imbalance

Note: If B, F, and G nodes do not exist at the same time, then the result is the same except for the rotation with empty nodes

Treatment: direct left-handed (i.e., left handed AC)

The transformation results are shown in the figure below

RL type

That is, the left child node branch of the right child node of the specified node is higher than the left branch of the specified node, resulting in imbalance

As shown in the following figure, are several common states of RL-type imbalance state

As shown in the figure above, their imbalance contrast points are all at node A, and the height difference between the left and right subtrees reaches 2. (It is found that the state cannot be balanced directly by left-handed rotation of AC)

Note: If B, D, and G nodes do not exist at the same time, then the result is the same but the rotation with empty nodes, which will not be covered here

Treatment scheme: dextrorotatory first and then left-handed (i.e., dextrorotatory is performed for CF first and left-handed for AF)

The transformation results are shown in the figure below

To obtain high

The balanced binary tree identifies whether the node is unbalanced by detecting the height difference of the left and right branches, so the height (depth) of the node needs to be obtained.

int getHeight(LSTreeNode *node) {
    int heightX = 0;
    while (node) {
        heightX++;
        node = node->l ? node->l : node->r;
    }
    return heightX;
}
Copy the code

insert

The process of balancing binary tree insertion depends on the insertion of sorting binary tree, that is, maintaining balance after insertion

After normal insertion of an element, the binary tree is checked and balanced by reference to the four unbalanced states

Common post-insertion unbalanced structures (take the insertion of the left black node I as an example, and remember to ignore local similarities to avoid falling into the trap of too many cases) are as follows:

Balance steps

1. Insert an element into the sorting binary tree normally, and mark the parent node

2. Check whether the parent node exists (the parent node must exist; otherwise, the root node is inserted). If the parent node does not exist, the root node is inserted.

3. Compare whether the height difference between the left and right branches of the grandparent node reaches the imbalance condition. The grandparent node is called the imbalance control point here

4. If the grandparent node is not out of balance, the parent node becomes the inserted node, and the grandparent node becomes the parent node. Continue searching from bottom to top (ensure that the inserted node is not out of balance with other branch nodes until the root node), and repeat Step 2. Otherwise proceed to the next step

5. Judge which side height is the insertion edge by comparing the left and right difference results of the grandparent node

6. The insertion point is to the left of the imbalance point: then check whether it is LL type or LR type. At this time, check whether the right child is an insert node through the parent node of the insertion point.

7. If the type is LL, directly rotate the parent node of the inserted node and the grandfather node of the inserted node. If it is of THE LR type, the parent node and the insert node are left turned first, and then the parent node and the grandparent node are right turned

8. The insertion point is to the right of the imbalance point: then check whether it is RR or RL type. At this time, check whether the left child is an insertion node through the parent node of the insertion point.

9. If the value is RR, immediately left the parent node of the inserted node and the grandparent node of the inserted node. If type RL is used, the parent node and the insertion node are rotated right first, and then the opposite node and the grandparent node are rotated left

Code implementation

LSTreeNode *insertData(LSTreeNode *root, int data) { LSTreeNode *node = (LSTreeNode *)malloc(sizeof(LSTreeNode)); node->data = data; if (! root) return node; LSTreeNode *p = root, *s = NULL; While (p) {s = p; if (p->data == data) { free(node); return root; } if (p->data >data) {p = p->l; }else { p = p->r; } } _Bool isLeft = s->data > data; if (isLeft) { s->l = node; }else { s->r = node; } node->parentNode = s; InsertBalanceNode (root, s, node); // Insert a new node (root, s, node); return root; LSTreeNode *insertBalanceNode(LSTreeNode *root, LSTreeNode *parentNode, LSTreeNode *root, LSTreeNode *insertNode) { LSTreeNode *grandNode = parentNode->parentNode; // If (! grandNode) return root; Int heightX = getHeight(grandNode->l) -getheight (grandNode->r); If (abs(heightX) < 2) {// if (abs(heightX) < 2) {// If (abs(heightX) < 2); Return insertBalanceNode(root, grandNode, parentNode); return insertBalanceNode(root, grandNode, parentNode); } // This is where the balance needs to be directly balanced // If (heightX > 0) {// if (heightX > 0) {// if (heightX > 0); If (parentNode->r == insertNode) {// If parentNode->r == insertNode) { SwapLeftRotation (parentNode, insertNode); } swapRightRotation(grandNode, parentNode); If (parentNode->l == insertNode) {swapRightRotation(parentNode, insertNode);}else {swapRightRotation(parentNode, insertNode); } swapLeftRotation(grandNode, parentNode); } return root;} return root; }Copy the code

delete

The process of insertion and deletion of balanced binary tree depends on the deletion of sorted binary tree, that is, maintaining balance after insertion

After deleting an element normally, it is necessary to handle the handover of its parent node (especially the handover of the newly added parent node compared with the sorting binary tree), and then check and balance the binary tree by referring to the four unbalanced states

The common deletion structure (take the right black node X as an example, and remember to ignore local similarities to avoid falling into the trap of too many cases) is as follows:

Balance steps

1. Delete the element from the sorting binary tree and properly maintain the parent-child node connection

2. Check whether the parent node of the node to be deleted exists. If no, delete the pure root node

3. Save the sibling and parent nodes of the deleted node and start balancing the sorting binary tree

4. If the parent node does not exist, it has been balanced or compared to the root node

5. Compare whether the height difference between the left and right branches of the parent node reaches the unbalance condition. The parent node here becomes the unbalance reference point

6. If the parent node is not out of balance, the parent node becomes the sibling node, and the grandparent node becomes the parent node. Continue searching from bottom to top (ensure that the deletion is not out of balance with other branch nodes until the root node is deleted), and repeat Step 2. Otherwise proceed to the next step

7. The sibling node of the deleted node is to the left of the imbalance point: View is LL type, type or LR, unable to directly determine the type of imbalance, so need by brother nodes around the branch height difference, to determine the imbalance type (which can be compared to insert), if the height is less than the right, left for LR, otherwise the default for LL (which have the same height is how to deal with, with LL the most simple)

8. Delete the sibling node of the node to the right of the imbalance point: Is to view the RR, or RL, unable to directly determine the type of imbalance, so need by brother nodes around the branch height difference, to determine the imbalance type (which can be compared to insert), if the height is greater than the right, left for RL, otherwise the default for the RR (which have the same height is how to deal with, with LL the most simple)

LSTreeNode *deleteData(LSTreeNode *root, int data) {if (! root) return NULL; LSTreeNode *p = root, *s = NULL; while (p) { if (p->data == data) break; s = p; if (p->data < data) { p = p->r; }else { p = p->l; } } if (! p) return root; // Failed to find deletion if (! p->l && ! P ->r) {if (p == root) root = NULL; else if (s->l == p) s->l = NULL; else s->r = NULL; }else if (! P - > l & p - > r) {/ / only if right node (p = = root) root = s - > r; else if (s->l == p) s->l = p->r; else s->r = p->r; if (p->r) p->r->parentNode = s; }else if (p->l && ! P ->r) {if (p == root) root = s->l; else if (s->l == p) s->l = p->l; else s->r = p->l; if (p->l) p->l->parentNode = s; LSTreeNode *q = p; S = p; P = p->l; While (p->r) {q = p; p = p->r; } q->data = p->data; if (s == q) { s->l = p->l; if (p->l) p->l->parentNode = s; } else { q->r = p->l; if (p->l) p->l->parentNode = q; }} if (s) {LSTreeNode *brotherNode = s->l == p? s->r : s->l; root = deleteBalanceNode(root, s, brotherNode); } free(p); return root; } // Balance binary tree delete (on the basis of delete), from delete node balance, then similar to insert, the current branch as the missing branch, find another branch balance, if balance, LSTreeNode *deleteBalanceNode(LSTreeNode *root, LSTreeNode *parentNode, LSTreeNode *brotherNode) {// If no, the root node is reached. parentNode) return root; int heightX = getHeight(parentNode->l) - getHeight(parentNode->r); If (abs(heightX) < 2) {if (abs(heightX) < 2) { The parent node and the deleted node can automatically exclude the case that there are two nodes at the same time (at the same time, the balance will not be affected after the deletion of the left and right children). In fact, the initial judgment is made once. To optimize efficiency, return deleteBalanceNode(root, parentNode->parentNode, parentNode); } if (heightX > 0) {// if (heightX > 0) {// if (heightX > 0); If (getHeight(brotherNode->l) -getheight (brotherNode->r) < 0) {if (getHeight(brotherNode->l) -getheight (brotherNode->r) < 0) { In this case, swapLeftRotation(brotherNode, brotherNode->r) must exist in the right node; } swapRightRotation(parentNode, brotherNode); }else {if (getHeight(brotherNode->l) -getheight (brotherNode->r) > 0) { At this time, swapRightRotation(brotherNode, brotherNode-> L) must exist on the left node; } // swapLeftRotation(parentNode, brotherNode) can be balanced by direct whole left; } return root;} return root; }Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Data structures and algorithms —- Balanced binary tree (AVL tree)

Introduction to the

rotating

Types of imbalance and means of balance

To obtain high

insert

delete

Data structures and algorithms —- Balanced binary tree (AVL tree)

Introduction to the

rotating

Types of imbalance and means of balance

To obtain high

insert

delete

Related Posts

2 years ago, a private work experience, worth reflecting ~

How does the front end draw a DAG diagram?

【 Security technology 】 on several DLL injection methods of learning