Introduction to the
Balanced binary tree, full name balanced binary search tree, because it is proposed by Adelse_Velskil and Landis, so it is also called AVL tree. Speaking of binary search trees, we have to mention its properties, the node size of the left subtree is smaller than the root node, the node size of the right subtree is larger than the root node, and the left and right subtrees are also binary search trees. Therefore, in general, the operation of binary search tree, a data structure, can reach O(logn) time complexity. But!! Because of this “but”, they proposed the concept of balanced binary trees. If the original is the following binary search tree, then maybe not very easy to solve.
The binary tree is degraded to a linked list, so that all operations are the same as the linked list, which is called the “imbalance” of the binary tree.
On this basis, the binary tree is balanced, aiming to make the unbalanced binary tree become “balanced”.
The nature of the
Balanced binary trees inherit the properties of binary search trees structurally:
- Balanced binary trees can be empty
- The left and right subtrees of any node of a balanced binary tree are balanced binary trees, and the height difference between the left and right subtrees of == cannot exceed 1==
For example
The figure below is not a balanced binary tree because 40 is not a balanced binary tree and the difference in height between the left and right sides is greater than 1\
The following is also not a balanced binary tree, since the height difference between 9 and 40 is greater than 2\
The following is a more standard balanced binary tree:
implementation
node
The nodes of a balanced binary tree are defined as follows
Java version
class AVLNode{// Tree node definition
private AVLNode left;/ / the left node
private AVLNode right;/ / right node
private int data;
private int height;/ / tree height
public AVLNode(AVLNode left, AVLNode right, int data) {
this(left, right, data, 0);
}
public AVLNode(int data){
this(null.null, data);
}
public AVLNode(AVLNode left, AVLNode right, int data, int height) {
this.left = left;
this.right = right;
this.data = data;
this.height = height;
}
public void setHeight(int h) {
this.height = h;
};
public int getHeight(a) {
return this.height;
};
};
Copy the codeGo version
type AVLNode struct {
left *AVLNode
right *AVLNode
data int
height int
}
func createNewNode(data int) *AVLNode{
return &AVLNode{
left: nil,
right: nil,
data: data,
height: 0,}}Copy the codeBalance factor
As for the concept of Balance, this data structure determines whether the binary search tree is unbalanced based on whether the height difference between the left subtree and the right subtree is greater than 1 as the standard, which is called the Balance Factor.
Java version
public int getBalanceFactor(AVLNode tree){
return tree.left.getHeight() - tree.right.getHeight();
}
Copy the codeGo version
type AVLTree struct {
root *AVLNode
}
func createNewTree(data int) *AVLTree{
return &AVLTree{
root:createNewNode(data),
}
}/ / AVL tree structure
type method interface {// The method to implement
getBalanceFactor(treeNode *AVLNode) int
leftLeftRotation(treeNode *AVLNode) *AVLNode
rightRightRotation(treeNode *AVLNode) *AVLNode
leftRightRotation(treeNode *AVLNode) *AVLNode
rightLeftRotation(treeNode *AVLNode) *AVLNode
insertNode(treeNode *AVLNode, key int) *AVLNode
insertValue(key int)
removeNode(treeNode *AVLNode, z *AVLNode)
removeValue(key int)
search(key int)}func(avlTree *AVLTree)getBalanceFactor(treeNode *AVLNode) int{
return treeNode.left.height - treeNode.right.height
}
Copy the codeObviously, a return value greater than 0 means the left subtree is higher, and a return value less than 0 means the right subtree is higher, equal to 0.
Node insertion imbalance adjustment
In the figure above, our nodes are out of balance after 60 is inserted, so how can we adjust them? Don’t worry, I’m going to take you step by step to solve the imbalance. Nodes can be classified into LL, RR, LR, and RL based on their positions.
LL: A node is inserted into the left subtree of the left root node of a node, causing an imbalance
In accordance with the rhythm from simple to complex, first introduce LL situation should be how to deal with.
In the figure above, the left subtree insertion node of a left subtree root node causes an imbalance. To solve the imbalance, it is necessary to find a way to reduce the height of the first unbalanced node.
The following flow shows how to balance:
- find
The first node out of balance20(that is, one of the nodes in the title) - The 20
The left subtreeThe node’sThe right subtreeThe node is transferred to 20 - In order to reduce the height of the first imbalanced point, it is found that node 10 has no right subtree and belongs to the imbalanced state, so 20 is made the right subtree node of node 10 of its left subtree, which not only reduces the height of the first imbalanced node, but also prevents new imbalanced node 10.
From this we introduce a concept called minimum imbalance subtree.
Look up the newly inserted node, and the subtree rooted in the node whose absolute value of the first balance factor exceeds 1 is called the least unbalanced subtree, also known as the least unbalanced subtree.
It’s actually the first node that starts to get out of balance.
LL is the simplest case, and we call this adjustment of imbalance a dextral operation. Right-handed is clockwise, you can think of it as rotating 20 with its right subtree on its left subtree node clockwise to the right (right-handed). So we know, for LL, we only need one right rotation.
Java version
Params: * treeNode root * return: * Returns the rotated root * */
private AVLNode leftLeftRotation(AVLNode treeNode){
AVLNode leftNode = treeNode.left;
treeNode.left = leftNode.right;
leftNode.right = treeNode;
int h = Math.max(treeNode.left.getHeight(), treeNode.right.getHeight()) + 1;// The height of the original root node depends on its new left subtree height and its unchanged right subtree height
treeNode.setHeight(h);
h = Math.max(leftNode.left.getHeight(), treeNode.getHeight()) + 1;// The height of the new root node depends on the height of its left subtree node and the height of the original root node that becomes its right subtree node
leftNode.setHeight(h);
return leftNode;
}
Copy the codeGo version
/ / LL: right
func(avlTree *AVLTree)leftLeftRotation(treeNode *AVLNode) *AVLNode{
leftNode := treeNode.left
treeNode.left = leftNode.right
leftNode.right = treeNode
if treeNode.left.height > treeNode.right.height{
treeNode.height = treeNode.left.height + 1
}else{
treeNode.height = treeNode.right.height + 1
}
if leftNode.left.height > treeNode.height{
leftNode.height = leftNode.left.height + 1
}else{
leftNode.height = treeNode.height + 1
}
return leftNode
}
Copy the codeRR: a node is inserted into the right subtree of the right root node of a node, resulting in an imbalance
Again, in the RR case, you just flip it over.
- find
The first node out of balance20(that is, one of the nodes in the title) - Transfer the == left == node of the == right subtree == of 20 to 20
- In order to reduce the height of the first imbalanced point, it is found that node 40 has no left subtree and is in an imbalanced state, so 20 is made the left subtree node of node 40 of its right subtree, which not only reduces the height of the first imbalanced node, but also prevents new imbalanced node 40.
We call this adjustment of imbalances a dextral operation. Left rotation is counterclockwise, so you can think of it as taking 20 and its left subtree and rotating it counterclockwise around its right subtree node to the left.
So we know, in the case of RR, we only need one left rotation.
Java version
Params: * treeNode root * return: * Returns the rotated root * */
private AVLNode rightRightRotation(AVLNode treeNode){
AVLNode rightNode = treeNode.right;
treeNode.right = rightNode.left;
rightNode.left = treeNode;
int h = Math.max(treeNode.left.getHeight(),treeNode.right.getHeight())+1;
treeNode.setHeight(h);
h = Math.max(rightNode.left.getHeight(),treeNode.getHeight())+1;
rightNode.setHeight(h);
return rightNode;
}
Copy the codeGo version
/ / RR: left-handed
func(avlTree *AVLTree)rightRightRotation(treeNode *AVLNode) *AVLNode{
rightNode := treeNode.right
treeNode.right = rightNode.left
rightNode.left = treeNode
if treeNode.left.height > treeNode.right.height{
treeNode.height = treeNode.left.height + 1
}else{
treeNode.height = treeNode.right.height + 1
}
if rightNode.right.height > treeNode.height{
rightNode.height = rightNode.right.height + 1
}else{
rightNode.height = treeNode.height + 1
}
return rightNode
}
Copy the codeLR: A node is inserted into the right subtree of the left child root node of a node, resulting in an imbalance
In this case, it’s at 20Left child root node9Right subtree nodeThe insertion of node 13 on 15 causes imbalance. In this case, one left rotation and one right rotation are enough.
- Perform the RR operation on the left child root node of 20
- Then perform LL on root node 20
RL: The left subtree of a node in the right subtree is inserted into the node, resulting in an imbalance
Only the process is shown here
Java version
private AVLNode leftRightRotation(AVLNode treeNode){
treeNode.left = rightRightRotation(treeNode.left);
return leftLeftRotation(treeNode);
}
private AVLNode rightLeftRotation(AVLNode treeNode){
treeNode.right = leftLeftRotation(treeNode.right);
return rightRightRotation(treeNode);
}
Copy the codeGo version
func(avlTree *AVLTree)leftRightRotation(treeNode *AVLNode) *AVLNode{
treeNode.left = avlTree.rightRightRotation(treeNode.left)
return avlTree.leftLeftRotation(treeNode)
}
func(avlTree *AVLTree)rightLeftRotation(treeNode *AVLNode) *AVLNode{
treeNode.right = avlTree.leftLeftRotation(treeNode.right)
return avlTree.rightRightRotation(treeNode)
}
Copy the codeFull insert operation
For the above four types of insertion, the routine is relatively fixed and easy to understand. The full insert operation is as follows
Java version
/* * Insert node -- insert(tree,key) * params: * tree AVL root node * key inserted node key * return: * root node * */
private AVLNode insert(AVLNode tree, int key){
if(tree==null) {
// Create a node
tree = new AVLNode(null.null, key);
if(tree==null){
System.out.println("ERROR : create avlTree node failed!");
return null; }}else{
int cmp = key - tree.data;
if(cmp<0) {
tree.left = insert(tree.left, key);
if(getBalanceFactor(tree) == 2) {// The left subtree is 2
if(key - tree.left.data > 0) {If the value is greater than the left subtree, the node is inserted into the right subtree
tree = leftRightRotation(tree);// Right subtree node of left subtree
}else {
tree = leftLeftRotation(tree);// Left subtree node of left subtree}}}else if(cmp>0){
tree.right = insert(tree.right, key);
if(getBalanceFactor(tree) == -2) {// The right subtree should be -2
if(key - tree.right.data > 0) {If the value is greater than that of the right subtree, the node is inserted in the right subtree
tree = rightRightRotation(tree);// The left node of the right subtree
}else {
tree = rightLeftRotation(tree);// The right subtree node of the right subtree}}}else {
System.out.println("Add failed: cannot add the same node!");
}
}
tree.setHeight(Math.max(tree.left.getHeight(), tree.right.getHeight()) + 1);
return tree;
}
public void insert(int key) {
Root = insert(Root,key);
}
Copy the codeGo version
func(avlTree *AVLTree)insertNode(treeNode *AVLNode, key int) *AVLNode {
if treeNode == nil{
treeNode = createNewNode(key)
}else{
cmp := key - treeNode.data
if cmp > 0 {/ / right subtree
treeNode.right = avlTree.insertNode(treeNode.right, key)
if avlTree.getBalanceFactor(treeNode) == 2 - {
if key - treeNode.right.data > 0{
treeNode = avlTree.rightRightRotation(treeNode)
}else{
treeNode = avlTree.rightLeftRotation(treeNode)
}
}
}else if cmp < 0{
treeNode.left = avlTree.insertNode(treeNode.left, key)
if avlTree.getBalanceFactor(treeNode) == 2 {
if key - treeNode.left.data > 0{
treeNode = avlTree.leftRightRotation(treeNode)
}else{
treeNode = avlTree.leftLeftRotation(treeNode)
}
}
}else{
fmt.Println("Add failed, cannot join same node")}}if treeNode.left.height > treeNode.right.height {
treeNode.height = treeNode.left.height + 1
}else {
treeNode.height = treeNode.right.height + 1
}
return treeNode
}
func(avlTree *AVLTree)insert(key int) {
avlTree.root = avlTree.insertNode(avlTree.root, key)
}
Copy the codeIn addition to insertion, deletion can also cause an imbalance, as removing a node means that some nodes lose height.
Node deletion imbalance adjustment
Before deleting a node, determine the node type and whether the node is unbalanced after deletion. Node types are divided into three categories and four sub-categories:
- A leaf node
- Only left subtree/only right subtree
- We have left subtrees and right subtrees
Delete a node as a leaf node
For the leaf node, it is relatively easy, because it is the leaf node, so delete directly from the parent node to consider whether the imbalance, if there is no imbalance continue to judge the parent node, and then start nesting dolls…… The most conventional solution to the nesting doll problem is obvious, you dare nesting doll, I dare recurse! (Of course, not too deep recursion, dog head survival, recursion can use stack implementation).
A node can be deleted only from the left or right subtree
For only the left subtree or the right subtree is also relatively simple, that is, after deleting the node, deliver its subtree to its parent node and then perform the same nesting judgment.
The deleted node has both left and right subtrees
What if both the left and right subtrees of a node exist? In fact, do not panic, the meaning of deleting the node is to erase the node value of this point, in addition to deleting the node there is a way is to use other values to replace it! Because the deletion of the leaf node is the most easy, so you can consider the left child of the node in the tree’s largest leaf node (must be smaller than the current node, but is larger than other nodes left subtree) or right subtree minimum leaf node (certainly is bigger than the current node but smaller than other node right subtree), as to which one to use, or according to the height of course, When the replacement is finished, only need to delete in accordance with the mode of the leaf node to continue to delete, delete the doll…….
Java version
/* * delete node -- remove(tree,key) * params: * tree AVL root node * z Deleted node * return: * root node * */
private AVLNode remove(AVLNode tree,AVLNode z){
if(tree==null||z==null) return null;
int cmp = z.data - tree.data;
if(cmp<0) {// The deleted node is in the left subtree
tree.left = remove(tree.left,z);
if(getBalanceFactor(tree)== -2) {// Delete the left subtree node, the right subtree should be taller, adjust the right subtree node
AVLNode r = tree.right;
if(r.right.getHeight() > r.left.getHeight())
tree = rightLeftRotation(tree);
elsetree = rightRightRotation(tree); }}else if(cmp>0){
tree.right = remove(tree.right, z);
if(getBalanceFactor(tree) == 2) {
AVLNode l = tree.left;
if(l.right.getHeight() > l.left.getHeight()) {
tree =leftRightRotation(tree);
}else{ tree =leftLeftRotation(tree); }}}else {// This is also a process of looking for nodes to be deleted. Recursive searching means that the parent node is kept every time
if((tree.left ! =null) && (tree.right ! =null)) {
if(tree.left.getHeight() > tree.right.getHeight()) {
AVLNode max = maximum(tree.left);
tree.data = max.data;// Assign the maximum value to the node to be deleted
tree.left = remove(tree.left, max);// Delete the leaf node with the maximum value
}else{
AVLNode min = minimum(tree.right);/ / same as abovetree.data = min.data; tree.right = remove(tree.right, min); }}else{ AVLNode tmp = tree; tree = (tree.left ! =null)? tree.left : tree.right;// This operation has reduced the height of the current node!!
tmp = null;// Delete the original node}}return tree;
}
public void remove(int key) {
AVLNode z;
if((z = search(Root,key)) ! =null)
Root = remove(Root, z);
}
/* * Find the smallest node: returns the smallest node of the AVL tree whose root is tree. * /
private AVLNode minimum(AVLNode tree) {
if (tree == null)
return null;
while(tree.left ! =null)
tree = tree.left;
return tree;
}
/* * Find the largest node: returns the largest node of the AVL tree whose root is tree. * /
private AVLNode maximum(AVLNode tree) {
if (tree == null)
return null;
while(tree.right ! =null)
tree = tree.right;
return tree;
}
/* * Find node -- search(tree,key) * params: * tree AVL root node * key search node value * return: * found node * */
public AVLNode search(AVLNode tree, int key) {
AVLNode tmp = tree;
while(tmp ! =null) {
if(tmp.data == key) return tmp;
else if(tmp.data > key) tmp = tmp.left;
else tmp = tmp.right;
}
return tmp;
}
Copy the codeGo version
func(avlTree *AVLTree)removeNode(treeNode *AVLNode, del *AVLNode) *AVLNode {
if treeNode == nil || del == nil {
return nil
}
cmp := del.data - treeNode.data
if cmp > 0 {// The deleted point is in the right subtree
treeNode.left = avlTree.removeNode(treeNode.left, del)
if avlTree.getBalanceFactor(treeNode) == 2 {
l := treeNode.left
if l.right.height > l.left.height{
treeNode = avlTree.leftRightRotation(treeNode)
}else{
treeNode = avlTree.leftLeftRotation(treeNode)
}
}
}else if cmp < 0{
treeNode.right = avlTree.removeNode(treeNode.right, del)
if avlTree.getBalanceFactor(treeNode) == 2 - {
r := treeNode.right
if r.right.height > r.left.height{
treeNode = avlTree.rightRightRotation(treeNode)
}else{
treeNode = avlTree.rightLeftRotation(treeNode)
}
}
}else{
iftreeNode.left ! =nil&& treeNode.right ! =nil{
if treeNode.left.height > treeNode.right.height{
max := avlTree.findMaxNode(treeNode.left)
treeNode.data = max.data
treeNode.left = avlTree.removeNode(treeNode.left, max)
}else{
min := avlTree.findMinNode(treeNode.left)
treeNode.data = min.data
treeNode.left = avlTree.removeNode(treeNode.left, min)
}
}else{
iftreeNode.left ! =nil{
treeNode = treeNode.left
}else {
treeNode = treeNode.right
}
}
}
return treeNode
}
func(avlTree *AVLTree) remove(key int) {
tmp := avlTree.search(avlTree.root, key)
iftmp ! =nil{
avlTree.root = avlTree.removeNode(avlTree.root, tmp)
}
}
func(avlTree *AVLTree) findMaxNode(treeNode *AVLNode) *AVLNode{
if(treeNode == nil) {return nil
}
fortreeNode.right ! =nil{
treeNode = treeNode.right
}
return treeNode
}
func(avlTree *AVLTree) findMinNode(treeNode *AVLNode) *AVLNode{
if(treeNode == nil) {return nil
}
fortreeNode.left ! =nil{
treeNode = treeNode.left
}
return treeNode
}
func(avlTree *AVLTree) search(treeNode *AVLNode, key int) *AVLNode{
tmp := treeNode
fortmp ! =nil{
if tmp.data == key {
return tmp
}else if tmp.data > key{
tmp = tmp.right
}else{
tmp = tmp.left
}
}
return tmp
}
Copy the codeIt can be seen that the deletion operation is actually much more complex than the insertion operation, which is also the disadvantage of balanced binary tree. Therefore, on the basis of AVL tree, the legendary red-black tree is introduced.
conclusion
- Balanced binary tree is a highly balanced binary tree, so the extreme case of binary tree is avoided, and the time complexity of query is
O(logn). - Insert operation will introduce four kinds of imbalance :LL, RR, LR and RL. The most complicated case is only two rotations, so the time complexity is
O(1)(For the insert operation only). - The deletion operation is the disadvantage of balancing binary trees. The change of the parent node needs to be considered each time, resulting in a cumbersome process.
- Whether it’s an insert operation or a delete operation, we start with the first node that starts to get out of balance.