current position:Home>Data structure_ Balanced binary tree (C language)

Data structure_ Balanced binary tree (C language)

2022-06-24 09:56:28Small dark

General directory of data structures

Balanced binary trees

Balanced binary trees ( English names are also called AVL Trees ), Is in Sort binary trees A binary tree optimized on the basis of the structure of , The nature of the tree is The height difference between the left and right subtrees of any node is no more than 1

1. Graphic analysis

In balanced binary tree , It is mainly divided into four situations that need to adjust the balance state
(1)A The equilibrium factor of the node = 【A The height of the left subtree of the node 】 - 【A The height of the right subtree of the node 】 = 2, There's an imbalance , And the newly inserted node is the left child (A), Rotate the subtree to the right , And update the node height after rotation .
 Insert picture description here
(2)A The equilibrium factor of the node = 【A The height of the left subtree of the node 】 - 【A The height of the right subtree of the node 】 = -2, There's an imbalance , And the newly inserted node is the right child (C), Rotate the subtree to the left , And update the node height after rotation .
 Insert picture description here
(3)A The equilibrium factor of the node = 【A The height of the left subtree of the node 】 - 【A The height of the right subtree of the node 】 = 2, There's an imbalance , And the newly inserted node is the right child (B), Rotate left first p node , Again right node node , Complete the balancing operation .
 Insert picture description here
(4)A The equilibrium factor of the node = 【A The height of the left subtree of the node 】 - 【A The height of the right subtree of the node 】 = -2, There's an imbalance , And the newly inserted node is the left child (B), Rotate right first p node , Then left rotation node node , Complete the balancing operation .
 Insert picture description here

2. Source code

#include<stdio.h>
#include<stdlib.h>
#define max(a,b) ((a>b)?(a):(b))

typedef char DataType;
typedef struct AVLNode
{
    
    DataType data;          //  Data fields 
    struct AVLNode *lchild; //  Pointer to the domain , Point to the left child node 
    struct AVLNode *rchild; //  Pointer to the domain , Point to the right child node 
    int height;             //  Indicates the height of the current node as the root node subtree 
}AVLNode, *AVLTree;

//  initialization 
void InitAVLTree(AVLTree *T)
{
    
    (*T) = NULL;   //  The initialization root node is empty 
    printf(" Binary tree initialized !\n");
}

//  Get subtree height 
int getHeight(AVLNode *node)
{
    
    return node == NULL ? 0: node->height;
}

//  Right rotation 
AVLNode* Rotate_R(AVLNode *node)
{
    
    AVLNode *p = node->lchild;
    node->lchild = p->rchild;
    p->rchild = node;

    //  Update height ( Order of attention )
    node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
    p->height = max(getHeight(p->lchild), getHeight(p->rchild)) + 1;

    return p;
}

//  Left rotation 
AVLNode* Rotate_L(AVLNode *node)
{
    
    AVLNode *p = node->rchild;
    node->rchild = p->lchild;
    p->lchild = node;

    //  Update height ( Order of attention )
    node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
    p->height = max(getHeight(p->lchild), getHeight(p->rchild)) + 1;

    return p;
}

//  First left rotation , Again right 
AVLNode* Rotate_LR(AVLNode *node)
{
    
    AVLNode *p = node->lchild;
    node->lchild = Rotate_L(p);
    return Rotate_R(node);
}

//  First right rotation , Then left rotation 
AVLNode* Rotate_RL(AVLNode *node)
{
    
    AVLNode *p = node->rchild;
    node->rchild = Rotate_R(p);
    return Rotate_L(node);
}

//  Calculate the equilibrium factor 
int getBalance(AVLNode *node)
{
    
    if (node == NULL)
    {
    
        return 0;
    }
    return getHeight(node->lchild) - getHeight(node->rchild);
}

//  Insert operation of sorting binary tree 
void AVLTreeInsert(AVLTree *T, DataType x)
{
    
    if ((*T) == NULL)
    {
    
        //  If the current binary tree node is empty ,  That is, the insertion position , Then a new node space is allocated 
        (*T) = (AVLNode *)malloc(sizeof(AVLNode));
        (*T)->data = x;
        (*T)->height = 1;
        (*T)->lchild = (*T)->rchild = NULL;
    }
    else if (x < (*T)->data)
    {
    
        //  Recursive left subtree to find the insertion position 
        AVLTreeInsert(&(*T)->lchild, x);
    }
    else if(x > (*T)->data)
    {
    
        //  Recursive right subtree to find the insertion position 
        AVLTreeInsert(&(*T)->rchild, x);
    }
    else
    {
    
        printf(" Insert the failure ! The same data exists !\n");
        return;
    }

    //  Update the height of the parent node during recursive insertion 
    (*T)->height = max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;
    
    //  Get the balance factor 
    int balance = getBalance((*T));
    
    printf(" node :%c,  Height  = %d,  Balance factor  = %d\t",(*T)->data, (*T)->height, balance);
    
    //  Select according to the balance factor   Rotating way 
    if (balance > 1 && x < (*T)->lchild->data)
    {
    
        printf(" Right hand ");
        (*T) = Rotate_R((*T));
    }
    else if (balance < -1 && x > (*T)->rchild->data)
    {
    
        printf(" left-handed ");
        (*T) = Rotate_L((*T));
    }
    else if (balance > 1 && x > (*T)->lchild->data)
    {
    
        printf(" Left right rotation ");
        (*T) = Rotate_LR((*T));
    }
    else if (balance < -1 && x < (*T)->rchild->data)
    {
    
        printf(" Right left ");
        (*T) = Rotate_RL((*T));
    }
    printf("\n");
}

//  The first sequence traversal 
void PreOrderTraverse(AVLTree T)
{
    
    if (T)
    {
    
        printf("%c ", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

int main()
{
    
    AVLTree T;
    InitAVLTree(&T);
    DataType x;
    while (1)
    {
    
        printf(" Input insert data :");
        fflush(stdin);
        scanf("%c", &x);
        if (x == '#')
        {
    
            break;
        }
        AVLTreeInsert(&T, x);
        printf(" The first sequence traversal :");
        PreOrderTraverse(T);
        printf("\n");
    }
    system("pause");
    return 0;
}

3. test result

Right rotation
 Insert picture description here
Left rotation
 Insert picture description here
First left rotation , Again right
 Insert picture description here
First right rotation , Rotate left
 Insert picture description here

copyright notice
author[Small dark],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/175/202206240832108121.html

Random recommended