AVL balanced binary tree (I) - concept and C language implementation

Summary

This chapter is an introduction. AVL Trees . And the introduction " Binary search tree " The process is the same , This chapter begins with AVL A brief introduction to the theoretical knowledge of trees , Then give C The realization of language . The binary search tree implemented in this article is C Language version of the , In the following chapters C++ and Java Implementation of version .
Suggest ： If you are on " Binary search tree " Not familiar with , It is suggested to finish learning first " Binary search tree " Let's learn AVL Trees .

Catalog

1. AVL Introduction to the tree
2. AVL Treelike C Realization
3. AVL Treelike C Realization ( Complete source code )
4. AVL Treelike C The test program

Reprint please indicate the source ：AVL Trees ( One ) And Graphic analysis and C The realization of language - If the sky doesn't die - Blog Garden

---

More :  Data structure and algorithm series Catalog  

(01) AVL Trees ( One ) And Graphic analysis and C The realization of language
(02) AVL Trees ( Two ) And C++ The implementation of the
(03) AVL Trees ( 3、 ... and ) And Java The implementation of the

AVL Introduction to the tree

AVL The tree is based on its inventor G.M. Adelson-Velsky and E.M. Landis Named .
It is the first self balancing binary search tree , Also known as height balanced tree . Compared with " Binary search tree ", It is characterized by ：AVL The maximum height difference between two subtrees of any node in the tree is 1. ( On the height of the tree and other basic concepts , Please refer to " Binary search tree ( One ) And Graphic analysis and C The realization of language  ")

The two pictures above , On the left is AVL Trees , The height difference between the two subtrees of any node is <=1; And the one on the right is not AVL Trees , because 7 The height difference between the two subtrees is 2( With 2 The height of the tree that is the root node is 3, And then 8 The height of the tree that is the root node is 1).

AVL Tree search 、 Insert and delete are... On average and at worst O(logn).
If in AVL After inserting or deleting nodes in the tree , Make the difference in height greater than 1. here ,AVL The balance of the tree is destroyed , It is no longer a binary tree ; To keep it in balance again , It needs to be rotated . learn AVL Trees , The key point is its rotation algorithm ; In the following introduction , Let's introduce it in detail .

AVL Treelike C Realization

1. node

1.1 Definition

typedef int Type;

typedef struct AVLTreeNode{
    Type key;                    //  keyword ( Key value )
    int height;
    struct AVLTreeNode *left;    //  Left the child 
    struct AVLTreeNode *right;    //  The right child 
}Node, *AVLTree;

AVL The nodes of the tree include several constituent objects :
(01) key -- Is the key word , It's for the right AVL The nodes of the tree are sorted .
(02) left -- The left child. .
(03) right -- It's the right child .
(04) height -- It's height .

1.2 Node creation

/*
 *  establish AVL Tree nodes .
 *
 *  Parameter description ：
 *     key  Is the key value .
 *     left  The left child. .
 *     right  It's the right child .
 */
static Node* avltree_create_node(Type key, Node *left, Node* right)
{
    Node* p;

    if ((p = (Node *)malloc(sizeof(Node))) == NULL)
        return NULL;
    p->key = key;
    p->height = 0;
    p->left = left;
    p->right = right;

    return p;
}

1.3 The height of the tree

#define HEIGHT(p)    ( (p==NULL) ? 0 : (((Node *)(p))->height) )

/*
 *  obtain AVL The height of the tree 
 */
int avltree_height(AVLTree tree)
{
    return HEIGHT(tree);
}

About height , Some articles will " The height of an empty binary tree is defined as -1", This paper adopts Wikipedia The definition on ： The height of the tree is the maximum level . That is, the height of an empty binary tree is 0, The height of a non empty tree is equal to its maximum level ( The root level is 1, The child node of the root is the 2 layer , By analogy ).

1.4 Compare the size

#define MAX(a, b)    ( (a) > (b) ? (a) : (b) )

2. rotate
As I said before , If in AVL After inserting or deleting nodes in the tree , May lead to AVL Tree out of balance . This imbalance can be summarized as 4 It's a gesture ：LL( Left, left ),LR( about ),RR( Right, right ) and RL( Right to left ). Their schematic diagram is given below ：

In the picture above 4 Every tree is " Out of balance AVL Trees ", The order from left to right is ：LL、LR、RL、RR. In addition to the above , There are others out of balance AVL Trees , Here's the picture ：

The above two figures are for ease of understanding , And the list is about " Out of balance AVL Trees " Example . in general ,AVL What happens when a tree loses its balance must be LL、LR、RL、RR this 4 One of the species , They all have their own definitions ：

(1) LL：LeftLeft, Also known as " Left, left ". After inserting or deleting a node , The left subtree of the root node has non empty child nodes , Lead to " The height of the left subtree of the root " Than " The height of the right subtree of the root " Big 2, Lead to AVL The tree lost its balance .
      for example , on top LL In the case , because " The root node (8) The left subtree (4) The left subtree (2) There are also non empty child nodes ", and " The root node (8) The right subtree (12) No child node "; Lead to " The root node (8) The left subtree (4) Height " Than " The root node (8) The right subtree (12)" high 2.

(2) LR：LeftRight, Also known as " about ". After inserting or deleting a node , The left subtree and the right subtree of the root node have non empty child nodes , Lead to " The height of the left subtree of the root " Than " The height of the right subtree of the root " Big 2, Lead to AVL The tree lost its balance .
      for example , on top LR In the case , because " The root node (8) The left subtree (4) The left subtree (6) There are also non empty child nodes ", and " The root node (8) The right subtree (12) No child node "; Lead to " The root node (8) The left subtree (4) Height " Than " The root node (8) The right subtree (12)" high 2.

(3) RL：RightLeft, be called " Right to left ". After inserting or deleting a node , The right subtree of the root node and the left subtree have non empty child nodes , Lead to " The height of the right subtree of the root " Than " The height of the left subtree of the root " Big 2, Lead to AVL The tree lost its balance .
      for example , on top RL In the case , because " The root node (8) The right subtree (12) The left subtree (10) There are also non empty child nodes ", and " The root node (8) The left subtree (4) No child node "; Lead to " The root node (8) The right subtree (12) Height " Than " The root node (8) The left subtree (4)" high 2.

(4) RR：RightRight, be called " Right, right ". After inserting or deleting a node , The right subtree of the root node has non empty child nodes , Lead to " The height of the right subtree of the root " Than " The height of the left subtree of the root " Big 2, Lead to AVL The tree lost its balance .
      for example , on top RR In the case , because " The root node (8) The right subtree (12) The right subtree (14) There are also non empty child nodes ", and " The root node (8) The left subtree (4) No child node "; Lead to " The root node (8) The right subtree (12) Height " Than " The root node (8) The left subtree (4)" high 2.

As I said before , If in AVL After inserting or deleting nodes in the tree , May lead to AVL Tree out of balance .AVL After losing balance , It can be balanced by rotation , Here are the introduction "LL( Left, left ),LR( about ),RR( Right, right ) and RL( Right to left )" this 4 The rotation method corresponding to each case .

2.1 LL The rotation of the

LL Out of balance , It's possible to make AVL The tree is back in balance . Here's the picture ：

On the left is the tree before rotation , On the right is the tree after rotation . You can find , After the rotation, the tree becomes AVL Trees , And the rotation only needs one time to complete .
about LL rotate , You can think of it this way ：LL Rotation is about " Out of balance AVL The root node " On going , That is, nodes k2; And because of LL situation , That is, the left left case , Just hold it with your hands " Left the child , namely k1" Shake hard . take k1 Become a root node ,k2 become k1 The right subtree ,"k1 The right subtree " become "k2 The left subtree ".

LL Rotation code for

/*
 * LL： The left corresponds to the left ( Left single rotation ).
 *
 *  Return value ： Root node after rotation 
 */
static Node* left_left_rotation(AVLTree k2)
{
    AVLTree k1;

    k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;

    k2->height = MAX( HEIGHT(k2->left), HEIGHT(k2->right)) + 1;
    k1->height = MAX( HEIGHT(k1->left), k2->height) + 1;

    return k1;
}

2.2 RR The rotation of the

I understand LL after ,RR It's pretty easy to understand .RR Is with the LL In the case of symmetry ！RR The rotation method to restore balance is as follows ：

On the left is the tree before rotation , On the right is the tree after rotation .RR The rotation can be completed only once .

RR Rotation code for

/*
 * RR： Right right corresponds to ( Right single rotation ).
 *
 *  Return value ： Root node after rotation 
 */
static Node* right_right_rotation(AVLTree k1)
{
    AVLTree k2;

    k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;

    k1->height = MAX( HEIGHT(k1->left), HEIGHT(k1->right)) + 1;
    k2->height = MAX( HEIGHT(k2->right), k1->height) + 1;

    return k2;
}

2.3 LR The rotation of the

LR Out of balance , It takes two rotations to make AVL The tree is back in balance . Here's the picture ：

The first rotation is around "k1" On going "RR rotate ", The second time is around "k3" On going "LL rotate ".

LR Rotation code for

/*
 * LR： Left right correspondence ( Left double rotation ).
 *
 *  Return value ： Root node after rotation 
 */
static Node* left_right_rotation(AVLTree k3)
{
    k3->left = right_right_rotation(k3->left);

    return left_left_rotation(k3);
}

2.4 RL The rotation of the
RL Is with the LR The symmetry of ！RL The rotation method to restore balance is as follows ：

The first rotation is around "k3" On going "LL rotate ", The second time is around "k1" On going "RR rotate ".

RL Rotation code for

/*
 * RL： The case of right and left ( Right double rotation ).
 *
 *  Return value ： Root node after rotation 
 */
static Node* right_left_rotation(AVLTree k1)
{
    k1->right = left_left_rotation(k1->right);

    return right_right_rotation(k1);
}

3. Insert
Insert the code of the node

/* 
 *  Insert node into AVL In the tree , And return the root node 
 *
 *  Parameter description ：
 *     tree AVL Root node of tree 
 *     key  The key value of the inserted node 
 *  Return value ：
 *      The root node 
 */
Node* avltree_insert(AVLTree tree, Type key)
{
    if (tree == NULL) 
    {
        //  The new node 
        tree = avltree_create_node(key, NULL, NULL);
        if (tree==NULL)
        {
            printf("ERROR: create avltree node failed!\n");
            return NULL;
        }
    }
    else if (key < tree->key) //  Should be key Insert into "tree The left subtree " The situation of 
    {
        tree->left = avltree_insert(tree->left, key);
        //  After inserting the node , if AVL Tree out of balance , Adjust accordingly .
        if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
        {
            if (key < tree->left->key)
                tree = left_left_rotation(tree);
            else
                tree = left_right_rotation(tree);
        }
    }
    else if (key > tree->key) //  Should be key Insert into "tree The right subtree " The situation of 
    {
        tree->right = avltree_insert(tree->right, key);
        //  After inserting the node , if AVL Tree out of balance , Adjust accordingly .
        if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)
        {
            if (key > tree->right->key)
                tree = right_right_rotation(tree);
            else
                tree = right_left_rotation(tree);
        }
    }
    else //key == tree->key)
    {
        printf(" Add failure ： Adding the same node... Is not allowed ！\n");
    }

    tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;

    return tree;
}

4. Delete
Delete node code

/* 
 *  Delete node (z), Return root node 
 *
 *  Parameter description ：
 *     ptree AVL Root node of tree 
 *     z  The node to be deleted 
 *  Return value ：
 *      The root node 
 */
static Node* delete_node(AVLTree tree, Node *z)
{
    //  Root is empty   perhaps   There are no nodes to delete , Go straight back to NULL.
    if (tree==NULL || z==NULL)
        return NULL;

    if (z->key < tree->key)        //  The node to be deleted is in "tree The left subtree " in 
    {
        tree->left = delete_node(tree->left, z);
        //  After deleting a node , if AVL Tree out of balance , Adjust accordingly .
        if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)
        {
            Node *r =  tree->right;
            if (HEIGHT(r->left) > HEIGHT(r->right))
                tree = right_left_rotation(tree);
            else
                tree = right_right_rotation(tree);
        }
    }
    else if (z->key > tree->key)//  The node to be deleted is in "tree The right subtree " in 
    {
        tree->right = delete_node(tree->right, z);
        //  After deleting a node , if AVL Tree out of balance , Adjust accordingly .
        if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
        {
            Node *l =  tree->left;
            if (HEIGHT(l->right) > HEIGHT(l->left))
                tree = left_right_rotation(tree);
            else
                tree = left_left_rotation(tree);
        }
    }
    else    // tree It corresponds to the node to be deleted .
    {
        // tree My left and right children are not empty 
        if ((tree->left) && (tree->right))
        {
            if (HEIGHT(tree->left) > HEIGHT(tree->right))
            {
                //  If tree The left subtree is taller than the right subtree ;
                //  be (01) find tree The largest node in the left subtree of 
                //   (02) Assign the value of the largest node to tree.
                //   (03) Delete the largest node .
                //  This is similar to using "tree The largest node in the left subtree of " do "tree" Surrogate ;
                //  The advantage of this approach is ： Delete "tree The largest node in the left subtree of " after ,AVL The tree is still balanced .
                Node *max = avltree_maximum(tree->left);
                tree->key = max->key;
                tree->left = delete_node(tree->left, max);
            }
            else
            {
                //  If tree The left subtree of is no higher than the right subtree ( That is, they are equal , Or the right subtree is higher than the left subtree 1)
                //  be (01) find tree The smallest node in the right subtree of 
                //   (02) Assign the value of the smallest node to tree.
                //   (03) Delete the smallest node .
                //  This is similar to using "tree The smallest node in the right subtree of " do "tree" Surrogate ;
                //  The advantage of this approach is ： Delete "tree The smallest node in the right subtree of " after ,AVL The tree is still balanced .
                Node *min = avltree_maximum(tree->right);
                tree->key = min->key;
                tree->right = delete_node(tree->right, min);
            }
        }
        else
        {
            Node *tmp = tree;
            tree = tree->left ? tree->left : tree->right;
            free(tmp);
        }
    }

    return tree;
}

/* 
 *  Delete node (key Node value ), Return root node 
 *
 *  Parameter description ：
 *     tree AVL Root node of tree 
 *     key  The key value of the node to be deleted 
 *  Return value ：
 *      The root node 
 */
Node* avltree_delete(AVLTree tree, Type key)
{
    Node *z; 

    if ((z = avltree_search(tree, key)) != NULL)
        tree = delete_node(tree, z);
    return tree;
}

Be careful ： About AVL Treelike " The former sequence traversal "、" In the sequence traversal "、" After the sequence traversal "、" Maximum "、" minimum value "、" lookup "、" Print "、" The destruction " Equal interface and " Binary search tree " Is essentially the same , These operations are in " Binary search tree " Has been introduced in , Here is no longer a separate introduction . Of course , The following AVL The complete source code of the tree , Have given these API Implementation code . These interfaces are simple ,Please RTFSC(Read The Fucking Source Code)！

AVL Treelike C Realization ( Complete source code )

AVL Tree header file (avltree.h)

 View Code

AVL Tree implementation file (avltree.c)

 View Code

AVL Tree test program (avltree_test.c) 

 View Code

AVL Treelike C The test program

AVL The test results of the tree are as follows ：

==  Add... In turn : 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9 
==  The former sequence traversal : 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16 
==  In the sequence traversal : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
==  After the sequence traversal : 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7 
==  Height : 5
==  minimum value : 1
==  Maximum : 16
==  Tree details : 
 7 is root
 4 is  7's   left child
 2 is  4's   left child
 1 is  2's   left child
 3 is  2's  right child
 6 is  4's  right child
 5 is  6's   left child
13 is  7's  right child
11 is 13's   left child
 9 is 11's   left child
 8 is  9's   left child
10 is  9's  right child
12 is 11's  right child
15 is 13's  right child
14 is 15's   left child
16 is 15's  right child

==  Delete root node : 8
==  Height : 5
==  In the sequence traversal : 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 
==  Tree details : 
 7 is root
 4 is  7's   left child
 2 is  4's   left child
 1 is  2's   left child
 3 is  2's  right child
 6 is  4's  right child
 5 is  6's   left child
13 is  7's  right child
11 is 13's   left child
 9 is 11's   left child
10 is  9's  right child
12 is 11's  right child
15 is 13's  right child
14 is 15's   left child
16 is 15's  right child

below , We analyze the flow of the test program ！

1. newly build AVL Trees
    newly build AVL Root node of tree root.

2. Add... In turn "3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9" To AVL In the tree , The process is as follows .
2.01 add to 3,2
add to 3,2 Will not destroy AVL The balance of the tree .

2.02 add to 1
add to 1 after ,AVL Tree out of balance (LL), You need to be right at this time AVL The tree rotates (LL rotate ). The rotation process is as follows ：

2.03 add to 4
add to 4 Will not destroy AVL The balance of the tree .

2.04 add to 5
add to 5 after ,AVL Tree out of balance (RR), You need to be right at this time AVL The tree rotates (RR rotate ). The rotation process is as follows ：

2.05 add to 6
add to 6 after ,AVL Tree out of balance (RR), You need to be right at this time AVL The tree rotates (RR rotate ). The rotation process is as follows ：

2.06 add to 7
add to 7 after ,AVL Tree out of balance (RR), You need to be right at this time AVL The tree rotates (RR rotate ). The rotation process is as follows ：

2.07 add to 16
add to 16 Will not destroy AVL The balance of the tree .

2.08 add to 15
add to 15 after ,AVL Tree out of balance (RR), You need to be right at this time AVL The tree rotates (RR rotate ). The rotation process is as follows ：

2.09 add to 14
add to 14 after ,AVL Tree out of balance (RL), You need to be right at this time AVL The tree rotates (RL rotate ). The rotation process is as follows ：

2.10 add to 13
add to 13 after ,AVL Tree out of balance (RR), You need to be right at this time AVL The tree rotates (RR rotate ). The rotation process is as follows ：

2.11 add to 12
add to 12 after ,AVL Tree out of balance (LL), You need to be right at this time AVL The tree rotates (LL rotate ). The rotation process is as follows ：

2.12 add to 11
add to 11 after ,AVL Tree out of balance (LL), You need to be right at this time AVL The tree rotates (LL rotate ). The rotation process is as follows ：

2.13 add to 10
add to 10 after ,AVL Tree out of balance (LL), You need to be right at this time AVL The tree rotates (LL rotate ). The rotation process is as follows ：

2.14 add to 8
add to 8 Will not destroy AVL The balance of the tree .

2.15 add to 9
But add 9 after ,AVL Tree out of balance (LR), You need to be right at this time AVL The tree rotates (LR rotate ). The rotation process is as follows ：

3. Print tree information
Output the information of the following tree ：

The former sequence traversal : 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16
In the sequence traversal : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
After the sequence traversal : 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7
Height : 5
minimum value : 1
Maximum : 16

4. Delete node 8

Deleting does not result in AVL The imbalance of the tree .

Delete node 8 after , Before printing this AVL Tree information .
Height : 5
In the sequence traversal : 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16