Definition of balanced binary tree:
In order to prevent the height of the tree from growing too fast and reduce the performance of the binary sorting tree, it is stipulated that when inserting and deleting binary tree nodes, the absolute value of the height difference between the left and right subtrees of any node must not exceed 1. Such an ambiguous tree is called a balanced binary tree AVL (Balanced Binary Tree), or a balanced tree for short.
Balanced binary tree insertion:
(1) LL balanced rotation (right single rotation)
Because a new node is inserted in the subtree (L of the left child of node A (L), the balance factor of A increases from 1 to 2, which causes the subtree rooted at A to be unbalanced, and it takes one time Rotation operation to the right. Rotate A’s left child B to the right to replace A as the root node, rotate A node to the right and down to become the root node of B’s right subtree, and B’s original right subtree as The left subtree of node A.
As shown in Figure 7.11, the value next to the node represents the balance factor of the node, and the subtree of the corresponding node is represented by a square, and the value below represents the height of the subtree.
(2) RR balance rotation (left single rotation)
Because a new node is inserted on the right subtree (R) of the right child (R) of node A, the balance factor of A is reduced from -1 to -2, causing the subtree rooted at A to lose balance , requires a left rotation operation. Rotate A’s right child B to the left instead of A to become the root node, rotate A node to the left and down to become the root node of B’s left subtree, and B’s original left subtree is used as the right subtree of A node .
(3) LR balance rotation (first left and then right rotation)
Because a new node is inserted on the right subtree (R) of the left child (L) of A, the balance factor of A increases from 1 to 2, causing the subtree rooted at A to lose balance, which needs to be performed twice Rotation operation, first rotate left and then right. First rotate the root node C of the right subtree of the left child B of the A node to the upper left to the position of the B node, and then rotate the C node to the upper right to the position of the A node.
(4) RL balance rotation (first right and then left double rotation)
Due to the insertion of a new node on the left subtree (L) of the right child (R) of A, the balance factor of A is reduced from -1 to -2, resulting in the imbalance of the subtree rooted at A, which needs to be performed Two rotation operations, first right and then left. First rotate the root node C of the left subtree of the right child B of the A node to the upper right to the position of the B node, and then rotate the C node to the upper left to the position of the A node.
1. Define the structure
typedef struct TreeNode
{
int data;//Define the data field
int height;//definition height
struct TreeNode *lchild;//left child
struct TreeNode *rchild;//right child
}TreeNode;
2. Get node height
int getHeight(TreeNode *node)
{
return node ? node->height : 0;//Judge whether the node is empty, return 0 if it is empty, return height if it is not empty
}
3. Take the maximum value
int max(int a,int b)
{
return a > b ? a : b;
}
4. RR balance rotation (rotate left once)
void rrRotation(TreeNode *node,TreeNode **root)
{/*parameter one node: represents the node
Parameter two root: represents the parent node */
TreeNode *temp = node->rchild;//The right child is saved to the middle pointer
node->rchild = temp->lchild;//The left child of node is assigned to the right child of node
temp->lchild = node;//node replaces the left child of node
node->height = max(getHeight(node->lchild),getHeight(node->rchild)) + 1;//Add one to the maximum value
temp->height = max(getHeight(temp->lchild),getHeight(temp->rchild)) + 1;
*root = temp;
}
5.LL balance rotation (rotate to the right once)
void llRotation(TreeNode *node,TreeNode **root)
{/*parameter one node: represents the node
Parameter two root: represents the parent node */
TreeNode *temp = node->lchild;
node->lchild = temp->rchild;
temp->rchild = node;
node->height = max(getHeight(node->lchild),getHeight(node->rchild)) + 1;
temp->height = max(getHeight(temp->lchild),getHeight(temp->rchild)) + 1;
*root = temp;
}
6. Establish a balanced binary tree
void avlInsert(TreeNode **T,int data)
{/*First parameter**T: double dereference, used to change the value in T
The second parameter data: used to pass elements and compare sizes*/
if(*T==NULL)//First judge whether the node is empty, if it is an empty node, create a new node and initialize it
{
*T = (TreeNode*)malloc(sizeof(TreeNode));//Apply for memory space
(*T)->data = data;//write data
(*T)->height = 0;//Height is initialized to 0
(*T)->lchild = NULL;//The left child is initially empty
(*T)->rchild = NULL;//The right child is initially empty
}
else if(data<(*T)->data)//data is less than the current node value
{
avlInsert( & amp;(*T)->lchild,data);//The element to be inserted is smaller than the element in the node, then go to the left subtree
// Get the height of the current left and right subtrees
int lHeight = getHeight((*T)->lchild);
int rHeight = getHeight((*T)->rchild);
if(lHeight-rHeight==2)//judging whether the binary tree is unbalanced
{//judgment height difference
if(data<(*T)->lchild->data)//The element to be inserted is smaller than the element of the left child of the current node
{//LL type
llRotation(*T,T);//rotate right once
}
else
{//LR type
rrRotation((*T)->lchild, & amp;(*T)->lchild);//Left first
llRotation(*T,T);//After right rotation
}
}
}
else if(data>(*T)->data)//data is greater than the current node value
{
avlInsert( & amp;((*T)->rchild),data);//The element to be inserted is larger than the element in the node, then go to the right subtree
// Get the height of the current left and right subtrees
int lHeight = getHeight((*T)->lchild);
int rHeight = getHeight((*T)->rchild);
if(rHeight-lHeight==2)//Judge whether the binary tree is unbalanced
{//judgment height difference
if (data>(*T)->rchild->data)
{//RR type
rrRotation(*T,T);//rotate left once
}
else
{//RL type
llRotation((*T)->rchild, & amp;(*T)->rchild);//Right rotation first
rrRotation(*T,T);//After left rotation
}
}
}
(*T)->height = max(getHeight((*T)->lchild),getHeight((*T)->rchild)) + 1;
}
7. Preorder traversal (root left and right)
void preOrder(TreeNode *T)
{
if(T)
{
printf("%d ",T->data);//output root node
preOrder(T->lchild);//recursively traverse the left subtree
preOrder(T->rchild);//Recursively traverse the right subtree
}
}
8. Main function
int main()
{
TreeNode *T = NULL;//Initial tree root node
int nums[5] = {1,2,3,4,5};
int i;
for(i=0;i<5;i ++ )
avlInsert( & amp;T,nums[i]);//Construct a balanced binary tree
preOrder(T);
printf("\\
");
return 0;
}
Full code:
#include#include /* define structure */ typedef struct TreeNode { int data;//Define the data field int height;//definition height struct TreeNode *lchild;//left child struct TreeNode *rchild;//right child }TreeNode; /*Get node height*/ int getHeight(TreeNode *node) { return node ? node->height : 0;//Judge whether the node is empty, return 0 if it is empty, return height if it is not empty } /*Take the maximum value*/ int max(int a,int b) { return a > b ? a : b; } /*RR balance rotation (rotate left once)*/ void rrRotation(TreeNode *node,TreeNode **root) {/*parameter one node: represents the node Parameter two root: represents the parent node */ TreeNode *temp = node->rchild;//The right child is saved to the middle pointer node->rchild = temp->lchild;//The left child of node is assigned to the right child of node temp->lchild = node;//node replaces the left child of node node->height = max(getHeight(node->lchild),getHeight(node->rchild)) + 1;//Add one to the maximum value temp->height = max(getHeight(temp->lchild),getHeight(temp->rchild)) + 1; *root = temp; } /*LL balance rotation (rotate to the right once)*/ void llRotation(TreeNode *node,TreeNode **root) {/*parameter one node: represents the node Parameter two root: represents the parent node */ TreeNode *temp = node->lchild; node->lchild = temp->rchild; temp->rchild = node; node->height = max(getHeight(node->lchild),getHeight(node->rchild)) + 1; temp->height = max(getHeight(temp->lchild),getHeight(temp->rchild)) + 1; *root = temp; } /* build a balanced binary tree */ void avlInsert(TreeNode **T,int data) {/*First parameter**T: double dereference, used to change the value in T The second parameter data: used to pass elements and compare sizes*/ if(*T==NULL)//First judge whether the node is empty, if it is an empty node, create a new node and initialize it { *T = (TreeNode*)malloc(sizeof(TreeNode));//Apply for memory space (*T)->data = data;//write data (*T)->height = 0;//Height is initialized to 0 (*T)->lchild = NULL;//The left child is initially empty (*T)->rchild = NULL;//The right child is initially empty } else if(data<(*T)->data)//data is less than the current node value { avlInsert( & amp;(*T)->lchild,data);//The element to be inserted is smaller than the element in the node, then go to the left subtree // Get the height of the current left and right subtrees int lHeight = getHeight((*T)->lchild); int rHeight = getHeight((*T)->rchild); if(lHeight-rHeight==2)//judging whether the binary tree is unbalanced {//judgment height difference if(data<(*T)->lchild->data)//The element to be inserted is smaller than the element of the left child of the current node {//LL type llRotation(*T,T);//rotate right once } else {//LR type rrRotation((*T)->lchild, & amp;(*T)->lchild);//Left first llRotation(*T,T);//After right rotation } } } else if(data>(*T)->data)//data is greater than the current node value { avlInsert( & amp;((*T)->rchild),data);//The element to be inserted is larger than the element in the node, then go to the right subtree // Get the height of the current left and right subtrees int lHeight = getHeight((*T)->lchild); int rHeight = getHeight((*T)->rchild); if(rHeight-lHeight==2)//Judge whether the binary tree is unbalanced {//judgment height difference if (data>(*T)->rchild->data) {//RR type rrRotation(*T,T);//rotate left once } else {//RL type llRotation((*T)->rchild, & amp;(*T)->rchild);//Right rotation first rrRotation(*T,T);//After left rotation } } } (*T)->height = max(getHeight((*T)->lchild),getHeight((*T)->rchild)) + 1; } /*Preorder traversal (root left and right)*/ void preOrder(TreeNode *T) { if(T) { printf("%d ",T->data);//output root node preOrder(T->lchild);//recursively traverse the left subtree preOrder(T->rchild);//Recursively traverse the right subtree } } int main() { TreeNode *T = NULL;//Initial tree root node int nums[5] = {1,2,3,4,5}; int i; for(i=0;i<5;i ++ ) avlInsert( & amp;T,nums[i]);//Construct a balanced binary tree preOrder(T); printf("\\ "); return 0; }
Running result:
