Briefly describe binary trees
The biggest advantage of binary tree is the search efficiency is high, in the binary sorting tree to find a node in the average time complexity of O(log₂N);
In “Explaining how to learn bad binary trees (2) : Trees and binary/search/balance tree concepts and characteristics” mentioned
Binary sort tree is a data structure designed for dynamic search, which is oriented to search operation. The search process for the target node is similar to binary search for an ordered array. The average time complexity of finding a node in a binary sort tree is O(log n)**.
If the number of nodes is n and the depth of the tree is h, assuming that every layer of the tree is filled (layer L has 2^L nodes and the number of layers starts from 1), then h=log (n+1) can be obtained according to the geometric sequence formula. In the best case, the binary search tree is order log n efficient. When the binary search tree degrades to a singly linked list, for example, there is only the right subtree, as shown in the figure below, the search efficiency is O(n).
In short, the more “chunky” the binary search tree is, that is, the more “crammed” each layer is as much as possible (each parent node has two children), the more efficient the search is.
-
The search is most efficient, order log n, when every level is full.
-
When the binary search tree deforms to a single linked list, the search efficiency is the lowest, the lowest is O(n).
Balanced binary tree (AVL) is introduced to solve the problem of low lookup efficiency when binary search tree is degraded to single linked list.
Basic operation of balanced binary tree
-
Insert: Insert nodes to balance the tree
-
Delete: Deletes nodes to balance the tree
-
Rotation: a rotation operation that elevates a node to its parent position without breaking the property of a balanced binary tree.
-
Stretch: To move the current node to the root, or to make the current node the root.
To learn more about rotation and stretching, I recommend reading Advanced Splay Tree: From Principle to Implementation, where we first introduce binary trees
Balanced binary tree
A Balanced Binary Tree is also called an AVL Tree.
The maximum height difference between the two sons of any node in AVL is 1, so it is also called a height-balanced tree. The maximum depth of an AVL tree with n nodes is about 1.44log2n. Lookups, inserts, and deletes are O(logn) on average and in the worst case. Additions and deletions may require one or more tree rotations to rebalance the tree. This scheme is a good solution to the problem of binary search tree degradation into a linked list, and the time complexity of insertion, search and deletion is maintained at O(logN) in the best case and the worst case. But frequent rotations sacrifice order logN time for insertions and deletions, but the time is much more stable compared to binary search trees.
The common algorithms of balanced binary tree include red-black tree, AVL tree and so on. In the balanced binary search tree, we can see that the height is generally well maintained at O(log2n), greatly reducing the time complexity of the operation.
The formula of the nodes of the least binary balanced tree is as follows:
F(n)=F(n-1)+F(n-2)+1
This is similar to a recursive sequence, you can refer to the Fibonacci sequence, where 1 is the root node, F(n-1) is the number of nodes in the left subtree, and F(n-2) is the number of nodes in the right subtree.
Balance factor
The height or depth difference between the left subtree and the right subtree of a node is the Balance Factor (BF) of the node. The Balance Factor of all nodes in the balanced binary tree (AVL tree) can only be -1, 0 or 1
The balance factors for all nodes are marked in the figure below
(balance factor calculation right subtree – left subtree or right subtree – left subtree can, for the tree to judge whether the balance is: the condition of each node of the absolute value of the height difference between the left and right subtrees of no more than 1, just judge imbalances afterward to judge what kind of imbalance, this needs to choose according to the circumstance is left to right or right to left)
Balanced binary tree lookup nodes
Looking in an AVL tree is exactly the same as looking in a binary search tree, because the AVL tree is always balanced, and the structure of the tree does not change due to queries, which will not be repeated here
Balanced binary tree insert node
So let’s go through the steps
First, search for the lowest unbalance node. Search for the lowest unbalance node is the newly inserted node (that is, the leaf node).
Up search (or into back starting from the new node to the root), search to balance the first factor > 1 (| left subtree is highly – right subtree is highly | > 1) node, as a minimum unbalance node, because it is a search, insert a new node up binary tree search is one-way (struct members only around a tree). It is not convenient to use a single function to reverse search, so instead of searching for the lowest unbalance node, the insertion operation is implemented recursively
The height of each node is clear, and the calculation of balance factor is more convenient. The following is the core operation “rotation” of AVL tree. There are four kinds of node imbalance, as shown in the figure below
Four cases of binary tree imbalance
Examples of binary trees with different unbalance conditions are shown below (readers may find that the judgment “the left subtree of the lowest unbalance node also has a non-empty node in the left subtree” is suitable for the second set of graphs, but not so suitable for the first set of graphs).
AVL tree single rotation and double rotation
Single rotation
Single rotation is a solution for left left and right right, both cases are symmetric, so once you solve left and left, right and right are easy to do. Figure 3 is the solution of the left-left case. The node K2 does not satisfy the equilibrium property, because its left subtree K1 is 2 layers deeper than the right subtree Z, and in the subtree K1, the deeper layer is the left subtree X of K1, so it belongs to the left-left case.
To bring the tree back to equilibrium, we make k2 the root node of the tree, because K2 is greater than k1, we put k2 on the right subtree of K1, and Y that was in the right subtree of K1 is greater than k1 and less than k2, we put Y on the left subtree of K2, which satisfies both the property of binary search trees and the property of balanced binary trees.
This operation only requires a partial pointer change, and we end up with another binary lookup tree, which is an AVL tree, because X has been moved up one level, Y remains at the same level, and Z has been moved down one level. The new height of the tree is the same as the height of the tree that was not inserted into the left subtree, so the insertion has increased the height of X. Therefore, since the height of the subtree does not change, the path to the root node does not need to be rotated any further.
Double rotation
In the case of left and right and left, it’s not going to be balanced by a single rotation, it’s going to take two rotations. Double rotation is the solution for both cases, and again, the two cases are symmetric, so once you solve the left and right case, right and left are easy to do. Figure 4 is the solution of the left-right case. Node K3 does not satisfy the balance property, because its left subtree K1 is 2 layers deeper than the right subtree Z, and in the subtree K1, the deeper layer is the right subtree K2, so it belongs to the left-right case.
In order to rebalance the tree, we need to do two steps, the first step, we take k1 as the root, we do a right to right rotation, and the rotation becomes left to left, so the second step, we do another left to left rotation, and we end up with a balanced binary tree with k2 as the root.
First, the central node, i.e. the minimum unbalance node A, should be determined. The absolute value of its equilibrium factor is 2. There are mainly four kinds of unbalance cases:
(1) Insert in the left subtree of A’s left son B, also called LL — right rotation;
(2) Insert P into the right subtree of A’s left son C, also known as LR — left and right rotation;
(3) Insert P into the left subtree of A’s right son C, also known as RL — right-left rotation;
(4) Insert in the right subtree of A’s right son B, also known as RR — left rotation.
Remember the two important nodes, one is the unbalanced node, and the other is the son of the unbalanced node. The son is in the unbalanced path, and the rotation operation is to move the unbalanced node down according to the son of the unbalanced node as the center. Imbalance in these four cases (1) and (4) the two cases is symmetrical, in both cases the rotation of the algorithm is consistent, need only after a rotation can reach the goal, we call it a single rotation, (2) and (3) the two cases is symmetrical, in both cases the rotation of the algorithm is consistent, needs two rotation, we call it double rotation.
Binary tree rotation left and right
When performing the rotation operation, the minimum unbalance node should be found first, the type of unbalance should be judged, and then the type of rotation should be selected. How to judge? According to node A in the above picture, if BF is 2, it is determined to be L on the left side of the left son; if BF is -1 on the left side, it is determined to be R. In this case, it belongs to the unbalanced situation (2), and double rotation is used. Four rotation modes of single rotation and double rotation are described in detail below.
1, LL right rotation
P moves down and occupies the right son of C, and the right son of C is called the left son of P
2, RR left rotation
P moves down and occupies the left son of C, and the left son of C acts as the right son of P.
3, LR left and right rotation
Double rotation is divided into two steps: left rotation, with P’s son C as the unbalance node, Q’s right son Q, Q moves down, occupies Q’s left son, Q’s left son is Q’s right son, and Q is P’s left son.
If I rotate to the right, P goes down as the right son of P, and the right son of Q as the left son of P.
4, RL right and left rotation
Rotate right, P’s right son C as the new unbalance node Q, Q’s left son Q, Q moves down as the right son of Q, Q’s right son as the left son of Q, Q as the right son of P.
Rotate left, P moves down, occupies q’s left son, and q’s left son becomes P’s right son.
So let’s go through the steps
Balance the tree and rotate the code implementation
Template <class T> class TreeNode {public: TreeNode():lson(NULL),rson(NULL),freq(1), HGT (0){} T data; / / value int HGT; // unsigned int freq; // TreeNode* lson; TreeNode* rson; // point to the address of the right son}; Template <class T> class AVLTree {private: TreeNode<T>* root; Void insertpri(TreeNode<T>* &node,T x); // Insert TreeNode<T>* findpri(TreeNode<T>* node,T x); Void insubtree(TreeNode<T>* node); Void Deletepri(TreeNode<T>* &node,T x); Int height(TreeNode<T>* node); Void SingRotateLeft(TreeNode<T>* &k2); Void SingRotateRight(TreeNode<T>* &k2); Void DoubleRotateLR(TreeNode<T>* &k3); Void DoubleRotateRL(TreeNode<T>* &k3); Int Max(int cmpa,int CMPB); Public: AVLTree():root(NULL){} void insert(T x); TreeNode<T>* find(T x); Void Delete(T x); Void traversal(); // Iterate over the interface}; Template <class T> int AVLTree<T>::height(TreeNode<T>* node) {if(node! =NULL) return node->hgt; return -1; } template<class T> int AVLTree<T>::Max(int cmpa,int CMPB) {return cmpa> CMPB? cmpa:cmpb; } template<class T> void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2) {TreeNode<T>* k1; k1=k2->lson; k2->lson=k1->rson; k1->rson=k2; k2->hgt=Max(height(k2->lson),height(k2->rson))+1; k1->hgt=Max(height(k1->lson),k2->hgt)+1; } template<class T> void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2) {TreeNode<T>* k1; k1=k2->rson; k2->rson=k1->lson; k1->lson=k2; k2->hgt=Max(height(k2->lson),height(k2->rson))+1; k1->hgt=Max(height(k1->rson),k2->hgt)+1; } template<class T> void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3) {SingRotateRight(k3->lson); SingRotateLeft(k3); } template<class T> void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3) {SingRotateLeft(k3->rson); SingRotateRight(k3); } // Insert template<class T> void AVLTree<T>::insertpri(TreeNode<T>* &node,T x) {if(node==NULL); node=new TreeNode<T>(); node->data=x; return; } if(node->data>x) {insertpri(node->lson,x) {insertpri(node->lson,x); if(2==height(node->lson)-height(node->rson)) if(x<node->lson->data) SingRotateLeft(node); else DoubleRotateLR(node); } else if(node->data<x) {insertpri(node->rson,x); else if(node->data<x); If (2==height(node->rson)-height(node->lson)) if(x>node->rson->data) SingRotateRight(node); else DoubleRotateRL(node); } else ++(node->freq); HGT =Max(height(node->lson),height(node->rson)); } template<class T> void AVLTree<T>::insert(T x) {insertpri(root,x); } // Find template<class T> TreeNode<T>* AVLTree<T>:: findprI (TreeNode<T>* node,T x) {if(node==NULL)// Return NULL { return NULL; } if(node->data>x) {return findpri(node->lson,x); if(node->data>x) {return findpri(node->lson,x); } else if(node->data<x) {return findpri(node->rson,x); else if(node->data<x) {return findpri(node->rson,x); } else return node; } template<class T> TreeNode<T>* AVLTree<T>::find(T x) {return findpri(root,x);} // Find interface template<class T> TreeNode<T>* AVLTree<T>::find(T x) {return findpri(root,x); } // Delete template<class T> void AVLTree<T>::Deletepri(TreeNode<T>* &node,T x) {if(node==NULL) return; If (x < node->data) {Deletepri(node->lson,x); If (2==height(node->rson)-height(node->lson)) if(node->rson->lson!) =NULL&&(height(node->rson->lson)>height(node->rson->rson)) ) DoubleRotateRL(node); else SingRotateRight(node); } else if(x > node->data) { Deletepri(node->rson,x); If (2==height(node->lson)-height(node->rson)) if(node->lson->rson!) =NULL&& (height(node->lson->rson)>height(node->lson->lson) )) DoubleRotateLR(node); else SingRotateLeft(node); } else// If (node->lson&&node->rson) {TreeNode<T>* temp=node->rson; While (temp->lson!); =NULL) temp=temp->lson; // Select node->data=temp->data; // Select node->data; node->freq=temp->freq; Deletepri(node->rson,temp->data); If (2==height(node->lson)-height(node->rson)) {if(node->lson->rson! =NULL&& (height(node->lson->rson)>height(node->lson->lson) )) DoubleRotateLR(node); else SingRotateLeft(node); TreeNode<T>* temp=node; TreeNode<T>* temp=node; If (node->lson==NULL); if(node->lson==NULL); Else if(node->rson==NULL); else if(node->rson==NULL); delete(temp); temp=NULL; } } if(node==NULL) return; node->hgt=Max(height(node->lson),height(node->rson))+1; return; } template<class T> void AVLTree<T>::Delete(T x) {Deletepri(root,x); } template<class T> void AVLTree<T>::insubtree(TreeNode<T>* node) {if(node==NULL) return; insubtree(node->lson); Cout <<node->data<<" "; Insubtree (node->rson); Template <class T> void AVLTree<T>::traversal() {insubtree(root); }Copy the codeJavaScript code, not yet implemented
Classification of balanced binary search trees
Balanced binary search trees generally fall into two categories:
Strictly maintain a balanced tree height of log2n, so that each operation can be controlled in order of logn time, such as AVL tree, red black tree;
If the balance is not strictly maintained, it is not guaranteed that each operation is controlled at O(logn), but the average time complexity of each operation is O(logn), such as a stretchtree.
Balanced binomial red-black tree
Red-black tree is a kind of self-balanced binary search tree, also called “symmetric binary B tree”. If N%2=0 is black, N%2=1 is red. If N%2=0 is black, N%2=1 is red. These constraints ensure a key characteristic of red-black trees: the longest possible path from root to leaf is no more than twice as long as the shortest possible path. It turns out that the tree is roughly balanced. Because the worst-case time of operations such as insert, delete, and find a value is required to be proportional to the height of the tree, this theoretical upper limit on the height allows red-black trees to be efficient in the worst case, unlike normal binary search trees.
Self-balancing for red-black trees:
Because every red-black tree is also a specialized binary search tree, the read-only operations on a red-black tree are the same as those on a normal binary search tree. However, insertions and deletions on a red-black tree result in no longer conforming to the properties of a red-black tree. Restoring the red-black tree properties requires a small (O(logn)) color change (which is actually very fast) and no more than three tree rotations (two for insert operations). Although inserts and deletes are complex, the operation time can remain O(logn) times.
We first add nodes to the binary lookup tree and mark them red. If set to black, this will result in an additional black node on the root to leaf path, which is difficult to adjust (contrary to property 5). However, setting it to red may cause two consecutive red nodes to collide, which can be adjusted by color flips and tree rotation. What you do next depends on the color of the other adjacent nodes. As in the human family tree, we will use the term uncle-node to refer to the sibling of a node’s parent. Note:
Property 1 and property 3 are always maintained.
Property 4 is only threatened when adding red nodes, redrawing black nodes to red, or doing rotations.
Property 5 is only threatened when adding black nodes, redrawing red nodes to black, or doing rotations.
Insert operations on red-black trees:
Suppose the node to be inserted is labeled N, the parent node of N is labeled P, the grandparent node of N is labeled G, and the grandparent node of N is labeled U. Any color shown in the diagram is either an assumption made by its situation or implied by that assumption.
-
Case 1: The tree is empty and the location of the root node is directly inserted, which violates property 1. The node color can be changed from red to black.
-
Case 2: The parent node P of the insert node N is black, which does not violate any properties, and no modification is required. In this case, the tree is still valid. Property 5 is also not threatened, even though the new node N has two black leaf children; But since the new node N is red, the path through each of its children will have the same number of black nodes as the path through the black leaf it replaces, so it still satisfies this property.
Note: Case 1 is easy, case 2 is P black, everything is fine, but P red is different, here are the various cases where P is red, and that’s where it really gets difficult.
-
Case 3: if the parent node P U both are red, and uncle node (the newly inserted node N as P left child node or right child nodes are 3, right here only show N as P left child), we can take them two redraw node G to red to black and paint grandfather (used to keep properties (4). Now our new node N has a black parent P. Because any path through parent P or uncle U must go through grandparent G, the number of black nodes on these paths does not change. However, the parent of the red grandparent G may also be red, which violates property 4. To solve this problem, we recursively perform the whole process of the above cases on the grandparent G (checking the cases as if G were a newly added node). For example, if G is the root node, we simply make G black (case 1); If G is not the root node, and its parent is black, then all the properties are met, just insert (case 2); If G is not the root node and its parent node is red, the above procedure recurses (case 3).
-
Case 4: The parent P is red and the uncleu is black or missing, the new node N is the left child of its parent, and the parent P is the left child of its parent G. In this case, we perform a right rotation against the grandparent G; In the tree produced by rotation, the previous parent P is now the parent of the new node N and the previous grandparent G. We know that the previous grandparent G is black, otherwise the parent P cannot be red (it violates property 4 if both P and G are red, so G must be black). We switch the colors of the previous parent P and grandparent G, and the resulting tree satisfies property 4. Property 5 also remains satisfied because all paths through any of the three nodes used to go through the grandparent G, and now they all go through the former parent P. In each case, this is the only black node of the three.
-
Case 5: The parent P is red and the uncle-u is black or missing, and the new node N is the right child of the parent P and the parent P is the left child of the parent. In this case, we do a left rotation to swap the roles of the new node and its parent; Next, we deal with the previous parent node P in case 4 to resolve property 4, which is still invalid. Note that this change causes some paths to pass through the new node N (such as leaf no. 1 in the figure) or not through node P (such as leaf No. 3 in the figure) that they did not pass before, but since both nodes are red, property 5 is still valid.
Note: Insert is actually an in-place algorithm because all of the above calls use tail-recursion.
Red black tree delete operation:
If the node to be deleted has two sons, then the problem can be converted to the problem of deleting another node that has only one son. For binary lookup trees, when deleting a node with two non-leaf sons, we find the largest element in either its left subtree or the smallest element in its right subtree and transfer its value to the node to be deleted. We then delete the node from which we copied the value, which must have fewer than two non-leaf sons. Since only one value is copied and no property is violated, this simplifies the problem to how to remove nodes that have at most one son. It doesn’t care whether the node is the one that was originally removed or the one from which we copied the value.
We just need to talk about removing a node that has only one son (if both sons are empty, that is, leaves, we arbitrarily consider one of them to be its son). If we remove a red node (now the sons of the node will be leaves), its fathers and sons must be black. So we can simply replace it with its black son, without breaking property three and property four. All paths through the deleted node are just one less red node, which continues to guarantee property 5. Another simple case is when the deleted node is black and its son is red. If we just remove the black node and replace it with its red son, we will destroy property 5, but if we redraw its son as black, then all the paths that used to go through it will go through its black son, and we will maintain property 5.
What needs to be discussed further is that this is a complicated situation when both the node to be deleted and its son are black. We first replace the node to be deleted with its son. For convenience, call the son N(in his new position) and his brother (another son of his father) S. In the diagram below, we refer to N’s father as P, S’s left son as SL, and S’s right son as SR.
If N and its original father are black, removing its father results in any path through N having one less black node than any path without it. Because it violates property 5, the tree needs to be rebalanced. There are several scenarios to consider:
Case 1: N is the new root. In this case, we’re done. We remove a black node from all paths, and the new root is black, so the properties remain.
Note: In cases 2, 5, and 6, we assume that N is the left son of its father. If it is the son of the right, then left and right in these cases should be reversed.
Case 2: S is red. In this case we do a left rotation on N’s father, converting the red brother to N’s grandfather, and then we switch the colors of N’s father and grandfather. After both operations, although the number of black nodes on all paths has not changed, N now has a black brother and a red father (its new brother is black because it is a son of red S), so we can proceed to case 4, 5, or 6.
Case 3: N’s father, S, and S’s son are all black. In this case, we simply redraw S as red. The result is that all the paths through S, which are the ones that didn’t go through N before, are missing a black node. Because removing the original father of N removes one black node from all paths through N, this balances things out. However, all paths that go through P now have one less black node than paths that do not go through P, so still violate property 5. To fix this, we’re going to start with case 1, and we’re going to do the rebalancing on P.
Case 4: S and S ‘sons are both black, but N’s father is red. In this case, we simply swap the colors of N’s brother and father. This does not affect the number of black nodes on paths that do not go through N, but it increases the number of black nodes on paths that go through N by one, adding to the number of black nodes that are removed on those paths.
Case 5: S is black, S’s left son is red, S’s right son is black, and N is her father’s left son. In this case we do a right rotation on S, so that the left son of S becomes the father of S and the new brother of N. And then we switch the colors of S and its new father. All paths still have the same number of black nodes, but now N has a black brother, and his right son is red, so we’re in scenario 6. Neither N nor its father is affected by this transformation.
Case 6: S is black, S’s right son is red, and N is her father’s left son. In this case we do a left rotation on the father of N, so that S becomes the father of N (P) and the father of S’s right son. We then switch the colors of N’s father and S, and make S’s right son black. The subtree at its root is still the same color, so property three is not violated. However, N now has a black ancestor added: either N’s father becomes black, or it is black and S is added as a black grandfather. So, every path through N adds a black node.
At this point, if a path does not pass through N, there are two possibilities:
-
It goes through N’s new brother. Then it must have passed through the father of S and N, and they just switched colors. So the path keeps the same number of black nodes.
-
It goes through N’s new uncle, S’s right son. So it used to go through S, S’s father and S’s right son, but now it just goes through S, which is assumed to be the color of its previous father, and S’s right son, and it’s changed from red to black. The resultant effect is that the path passes through the same number of black nodes.
In any case, the number of black nodes on these paths does not change. So we restore property four. The white node in the diagram can be red or black, but the same color must be specified before and after the transformation.
Red black tree implementation source code
#define BLACK 1
#define RED 0
using namespace std;
class bst {
private:
struct Node {
int value;
bool color;
Node *leftTree, *rightTree, *parent;
Node() {
color = RED;
leftTree = NULL;
rightTree = NULL;
parent = NULL;
value = 0;
}
Node* grandparent() {
if (parent == NULL) {
return NULL;
}
return parent->parent;
}
Node* uncle() {
if (grandparent() == NULL) {
return NULL;
}
if (parent == grandparent()->rightTree)
return grandparent()->leftTree;
else
return grandparent()->rightTree;
}
Node* sibling() {
if (parent->leftTree == this)
return parent->rightTree;
else
return parent->leftTree;
}
};
void rotate_right(Node *p) {
Node *gp = p->grandparent();
Node *fa = p->parent;
Node *y = p->rightTree;
fa->leftTree = y;
if (y != NIL)
y->parent = fa;
p->rightTree = fa;
fa->parent = p;
if (root == fa)
root = p;
p->parent = gp;
if (gp != NULL) {
if (gp->leftTree == fa)
gp->leftTree = p;
else
gp->rightTree = p;
}
}
void rotate_left(Node *p) {
if (p->parent == NULL) {
root = p;
return;
}
Node *gp = p->grandparent();
Node *fa = p->parent;
Node *y = p->leftTree;
fa->rightTree = y;
if (y != NIL)
y->parent = fa;
p->leftTree = fa;
fa->parent = p;
if (root == fa)
root = p;
p->parent = gp;
if (gp != NULL) {
if (gp->leftTree == fa)
gp->leftTree = p;
else
gp->rightTree = p;
}
}
void inorder(Node *p) {
if (p == NIL)
return;
if (p->leftTree)
inorder(p->leftTree);
cout << p->value << " ";
if (p->rightTree)
inorder(p->rightTree);
}
string outputColor(bool color) {
return color ? "BLACK" : "RED";
}
Node* getSmallestChild(Node *p) {
if (p->leftTree == NIL)
return p;
return getSmallestChild(p->leftTree);
}
bool delete_child(Node *p, int data) {
if (p->value > data) {
if (p->leftTree == NIL) {
return false;
}
return delete_child(p->leftTree, data);
} else if (p->value < data) {
if (p->rightTree == NIL) {
return false;
}
return delete_child(p->rightTree, data);
} else if (p->value == data) {
if (p->rightTree == NIL) {
delete_one_child(p);
return true;
}
Node *smallest = getSmallestChild(p->rightTree);
swap(p->value, smallest->value);
delete_one_child(smallest);
return true;
}
}
void delete_one_child(Node *p) {
Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL) {
p = NULL;
root = p;
return;
}
if (p->parent == NULL) {
delete p;
child->parent = NULL;
root = child;
root->color = BLACK;
return;
}
if (p->parent->leftTree == p) {
p->parent->leftTree = child;
} else {
p->parent->rightTree = child;
}
child->parent = p->parent;
if (p->color == BLACK) {
if (child->color == RED) {
child->color = BLACK;
} else
delete_case(child);
}
delete p;
}
void delete_case(Node *p) {
if (p->parent == NULL) {
p->color = BLACK;
return;
}
if (p->sibling()->color == RED) {
p->parent->color = RED;
p->sibling()->color = BLACK;
if (p == p->parent->leftTree)
rotate_left(p->sibling());
else
rotate_right(p->sibling());
}
if (p->parent->color == BLACK && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
p->sibling()->color = RED;
delete_case(p->parent);
} else if (p->parent->color == RED && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
p->sibling()->color = RED;
p->parent->color = BLACK;
} else {
if (p->sibling()->color == BLACK) {
if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED
&& p->sibling()->rightTree->color == BLACK) {
p->sibling()->color = RED;
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling()->leftTree);
} else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
&& p->sibling()->rightTree->color == RED) {
p->sibling()->color = RED;
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling()->rightTree);
}
}
p->sibling()->color = p->parent->color;
p->parent->color = BLACK;
if (p == p->parent->leftTree) {
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling());
} else {
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling());
}
}
}
void insert(Node *p, int data) {
if (p->value >= data) {
if (p->leftTree != NIL)
insert(p->leftTree, data);
else {
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->leftTree = tmp;
insert_case(tmp);
}
} else {
if (p->rightTree != NIL)
insert(p->rightTree, data);
else {
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->rightTree = tmp;
insert_case(tmp);
}
}
}
void insert_case(Node *p) {
if (p->parent == NULL) {
root = p;
p->color = BLACK;
return;
}
if (p->parent->color == RED) {
if (p->uncle()->color == RED) {
p->parent->color = p->uncle()->color = BLACK;
p->grandparent()->color = RED;
insert_case(p->grandparent());
} else {
if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {
rotate_left(p);
rotate_right(p);
p->color = BLACK;
p->leftTree->color = p->rightTree->color = RED;
} else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {
rotate_right(p);
rotate_left(p);
p->color = BLACK;
p->leftTree->color = p->rightTree->color = RED;
} else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_right(p->parent);
} else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_left(p->parent);
}
}
}
}
void DeleteTree(Node *p) {
if (!p || p == NIL) {
return;
}
DeleteTree(p->leftTree);
DeleteTree(p->rightTree);
delete p;
}
public:
bst() {
NIL = new Node();
NIL->color = BLACK;
root = NULL;
}
~bst() {
if (root)
DeleteTree(root);
delete NIL;
}
void inorder() {
if (root == NULL)
return;
inorder(root);
cout << endl;
}
void insert(int x) {
if (root == NULL) {
root = new Node();
root->color = BLACK;
root->leftTree = root->rightTree = NIL;
root->value = x;
} else {
insert(root, x);
}
}
bool delete_value(int data) {
return delete_child(root, data);
}
private:
Node *root, *NIL;
};
Copy the codeReference article:
Algorithms: Trees and Graphs – theory blog.csdn.net/weixin_4312…
[Data Structure] various tree in Data Structure www.cnblogs.com/maybe2030/p…
Do you really know anything about trees? Binary tree and AVL balanced binary tree, stretch, b-tree and B + tree principle and the implementation code, www.srcmini.com/1315.html
Stretch Tree (Splay Tree) advanced – from principle to implement www.cnblogs.com/dilthey/p/9…
AVL tree (search, insert, delete) – C www.cnblogs.com/lanhaicode/…
Reprint the home station article “say thoroughly learn bad binary tree (5) : branch balance – AVL tree with red and black tree stretching from balance”, please indicate the source: www.zhoulujun.cn/html/theory…