Author: Lao Jiu – technology big millet

Product: Check the original article

Socializing: Zhihu

Public account: Old Nine School (beginners have benefits)

Special statement: the original is not easy, without authorization shall not be reproduced or copied, if you need to reproduce can contact the author authorized

preface

I first referenced O’Reilly’s Mastering Algorithms with C, the Wiki, and Weimin Yan’s Data Structures (C Edition). Because, you know, we want to go through a lot of professional references, and we want to learn algorithms very rigorously.

Summary of AVL tree

O ‘reilly described

I found no Description of the AVL tree concept in Mastering Algorithms with C, and the Description of Binary Trees in its Trees section reads as follows:

Traversal Methods
- Preorder traversal
- Inorder traversal
- Postorder traversal
- Level-order traversal
Tree Balancing

Screenshots of the original description are as follows:

I will not refer to the translation here, please baidu to understand, or find other ways to understand, because at last we refer to Lao Yan’s book to give a statement of self-cognition.

Wikipedia describes

I am not going to do the reference translation here, but I have listed it here to help you understand the correct concept of AVL tree in multiple dimensions. I hope it can help you. If you have any more professional books, I hope you can share them.

Data structure (C language version) interpretation

The following description is based on Lao Yan’s data structure teaching materials, combined with their own understanding to interpret the statement, please do not as a standard, if there is insufficient, please correct and supplement.

Definition of balanced binary tree (AVL tree)

It is either an empty tree, or a binary tree with the property that the absolute value of the difference in depth between its left and right subtrees (the balance factor) is no more than 1, and that both its left and right subtrees are balanced binary trees.

Definition of equilibrium factor

The depth of the left subtree of the node minus the depth of the right subtree, so obviously minus 1 is less than or equal to the equilibrium factor is less than or equal to 1.

The AVL tree is named after its inventors g.M. Adelson-Velsky and E.M.Landis. It is the first self-balanced binary search tree, also known as highly balanced tree. Compared with “binary search tree”, the maximum difference in height between two subtrees of any node in AVL tree is 1.

AVL trees are strictly balanced binary trees, and the equilibrium condition must be satisfied (the height difference between the left and right subtrees of all nodes is no more than 1). No matter whether we perform insert or delete operations, as long as the above conditions are not met, we need to maintain balance through rotation, which is very time-consuming, so we can know that AVL tree is suitable for the case of less insert and delete times, but more search.

Because the cost of maintaining such a high balance is greater than the efficiency gain from it, there are few practical applications, more in the form of red-black trees that pursue local rather than very strict global balance (as shown in the figure below). Of course, AVL trees are better than red-black trees in scenarios where insertion and deletion are not frequent and lookups are high.

The realization principle of AVL tree

Balance testing

AVL trees operate basically the same as binary search trees, focusing on two highly variable operations: insert and delete.

For a binary sort tree, each insertion can only be placed on a leaf node. So it only affects the balance of one subtree, not the other subtrees. In this case, we just need to follow the search path from the child to the ancestor, and if there are unbalanced nodes, they can be found; If no unbalanced nodes are found all the way to the root, then the insertion is not considered to have caused an imbalance in the tree.

When deleting elements each time, we can also search from children to ancestors according to the search path. If there are unbalanced nodes, they can be found. If no unbalanced nodes are found all the way to the root, then the insertion is not considered to have caused an imbalance in the tree.

Such a search process is called equilibrium detection.

Weight balance

In the process of balance detection, according to the definition of AVL tree, the calculated balance factor will appear in two situations:

If the balance factor is 0,1 and -1, it can be considered that the node conforms to the definition of the balance tree.
Otherwise, the node is unbalanced and needs to be rebalanced.

If an unbalanced node is found, it needs to be rebalanced. You can do this by rotating the node’s subtree.

There are theoretically two cases of rotation:

One is called left rotation (left rotation about X nodes);
One is called right rotation (right rotation of Y nodes).

In the real world, there are four possible scenarios:

The meanings of N,X,Y and Z in the figure are as follows:

N represents the newly inserted element node;
Z represents the sequence of nodes to be accessed from the position where the element is inserted, and the first unbalanced node discovered when the child detects the balance factor from the direction of the ancestor.
Y represents the access node at the time the element is inserted, the node that is accessed after the z node is accessed;
X represents the access node at the time the element was inserted, the node that was accessed after y was accessed.

In all four cases, you can make an unbalanced node equilibrate by one or two rotations. Cases 1 and 4 can be rebalanced by a single rotation, and cases 2 and 3 can be rebalanced by a double rotation.

Singly Rotation

The diagram of the rebalanced subtree resulting from a single rotation is shown below. It is important to distinguish the corresponding nodes.

Doubly-rotation.

A double rotation, as the name implies, requires two rotations to rebalance the subtree, as shown below:

In the first case, a left rotation of y node is required, followed by a right rotation of Z node;
In the third case, a right rotation of y is required, followed by a left rotation of Z.

AVL tree C language implementation

Node of AVL tree

struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
typedef int ElementType;

struct AvlNode
{
    ElementType Element;
    AvlTree Left;
    AvlTree Right;
    int Height;
};
Copy the code

Data structure of AVL tree

AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType X, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
ElementType Retrieve(Position P);
static int Height(Position P);
static int Max(int.int);
static Position SingleRotateWithLeft(Position P);
static Position StingleRotateWithRight(Position P);
static Position DoubleRotateWithLeft(Position P);
static Position DoubleRotateWithRight(Position P);
AvlTree Delete(Position P, AvlTree T);
Copy the code

left-handed

static Position SingleRotateWithLeft(Position P)
{
    Position K1;
    K1 = P->Left;
    P->Left = K1->Right;
    K1->Right = P;

    P->Height = Max(Height(P->Left), Height(P->Right)) + 1;
    K1->Height = Max(Height(K1->Left), Height(P->Height)) + 1;

    return K1;
}
Copy the code

Right hand

static Position StingleRotateWithRight(Position P)
{
    Position K1;
    K1 = P->Right;
    P->Right = K1->Left;
    K1->Left = P;

    P->Height = Max(Height(P->Left), Height(P->Right)) + 1;
    K1->Height = Max(Height(K1->Left), Height(P->Height)) + 1;
    
    return K1;
}
Copy the code

Double rotation

static Position DoubleRotateWithLeft(Position P)
{
    P->Left = StingleRotateWithRight(P->Left);
    return SingleRotateWithLeft(P);
}

static Position DoubleRotateWithRight(Position P)
{
    P->Right = StingleRotateWithRight(P->Right);
    return StingleRotateWithRight(P);
}
Copy the code

Insert elements

AvlTree Insert(ElementType X, AvlTree T)
{
    if (T == NULL)
    {
        T = malloc(sizeof(struct AvlNode));
        if (T == NULL)
        {
            Error("Error: out of space!!");
        }
        else
        {
            T->Element = X;
            T->Left = T->Right = NULL;
            T->Height = 0; }}else if (X < T->Element)
    {
        T->Left = Insert(X, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2)
        {
            if (X < T->Left->Element)
            {
                T = SingleRotateWithLeft(T);
            }
            else{ T = DoubleRotateWithLeft(T); }}}else
    {
        T->Right = Insert(X, T->Right);
        if (Height(T->Right) - Height(T->Right) == 2)
        {
            if (X < T->Right->Element)
            {
                T = StingleRotateWithRight(T);
            }
            else
            {
                T = DoubleRotateWithRight(T);
            }
        }
    }
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}
Copy the code

Delete elements (Delete)

AvlTree Delete(Position P, AvlTree T)
{
    Position PMix; 
    Position Tmp;
    if(T ! =NULL)
    {
        if (T->Element > P->Left)
        {
            T->Left = Delete(P, T->Left);
            T->Height = Max(Height(T->Right), Height(T->Left)) + 1;
            if (Height(T->Right) - Height(T->Left) == 2)
            {
                if (T->Right->Element < P->Element)
                {
                    return StingleRotateWithRight(T);
                }
                else
                {
                    returnDoubleRotateWithRight(T); }}}else if (T->Element < P->Left)
        {
            T->Right = Delete(P, T->Right);
            T->Height = Max(Height(T->Right), Height(T->Left)) + 1;
            if (Height(T->Left) - Height(T->Right) == 2)
            {
                if (T->Left->Element > P->Element)
                {
                    return SingleRotateWithLeft(T);
                }
                else
                {
                    returnDoubleRotateWithLeft(T); }}}else
        {
            if(T->Right ! =NULL&& T->Left ! =NULL)
            {
                if (Height(T->Right) > Height(T->Left))
                {
                    PMix = FindMin(T->Right);
                    T->Element = PMix->Element;
                    T->Right = Delete(PMix,T->Right);
                }
                else
                {
                    PMix = FindMax(T->Left);
                    T->Element = PMix->Element;
                    T->Left = Delete(PMix,T->Left);
                }
                T->Height = Max(Height(T->Right), Height(T->Left)) + 1;
            }
            else
            {
                Tmp = P;
                T = P->Right ? P->Right: P->Left;
                free(Tmp); }}}return T;
}
Copy the code

Search (Search)

Position Find(ElementType X, AvlTree T)
{
    if (T == NULL)
    {
        return NULL;
    }
    else if(X < T->Element)
    {
        return Find(X, T->Left);
    }
    else if (X > T->Element)
    {
        return Find(X, T->Right);
    }
    else
    {
        returnT; }}Position FindMax(AvlTree T)
{
    Position pL = T;
    Position pR = T;
    if(T->Left ! =NULL)
    {
        pL = findMax(T->Left);
    }

    if(T->Right ! =NULL)
    {
        pR = findMax(T->Right);
    }

    return pL->Height > pR->Height ? pL : pR;
}

Position FindMin(AvlTree T)
{
    Position pL = T;
    Position pR = T;

    if(T->Left ! =NULL)
    {
        pL = findMin(T->Left);
    }

    if(T->Right ! =NULL)
    {
        pR = findMin(T->Right);
    }

    return pL->Height < pR->Height ? pL : pR;
}
Copy the code

Auxiliary function

void MakeEmpty(AvlTree T)
{
    *T = (AvlTree)malloc(sizeof(AvlNode));
    (*T).Left = NULL;
    (*T).Right = NULL;
}

static int Height(Position P)
{
    return P->Height;
}

ElementType Retrieve(Position P)
{
    return P->Element;
}

static int Max(int x, int y)
{
    return x > y ? x : y;
}
Copy the code

conclusion

In the book Essential Algorithms, the characteristics of Algorithms are described as follows:

Our C language implementation is certainly not the best, here is just a piece of advice, hope and give you in the learning algorithm to provide ideas and help. If there are shortcomings, please correct and supplement.

The last

Feel useful students, please remember to big millet ❤️ attention + like + collection + comment + forward ❤️

Author: Lao Jiu School – technology big millet

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Balance of AVL tree

preface

Summary of AVL tree

O ‘reilly described

Wikipedia describes

Data structure (C language version) interpretation

Definition of balanced binary tree (AVL tree)

Definition of equilibrium factor

The realization principle of AVL tree

Balance testing

Weight balance

Singly Rotation

Doubly-rotation.

AVL tree C language implementation

Node of AVL tree

Data structure of AVL tree

left-handed

Right hand

Double rotation

Insert elements

Delete elements (Delete)

Search (Search)

Auxiliary function

conclusion

The last

Balance of AVL tree

preface

Summary of AVL tree

O ‘reilly described

Wikipedia describes

Data structure (C language version) interpretation

Definition of balanced binary tree (AVL tree)

Definition of equilibrium factor

The realization principle of AVL tree

Balance testing

Weight balance

Singly Rotation

Doubly-rotation.

AVL tree C language implementation

Node of AVL tree

Data structure of AVL tree

left-handed

Right hand

Double rotation

Insert elements

Delete elements (Delete)

Search (Search)

Auxiliary function

conclusion

The last

Related Posts

Technical growth planning for PHP programmers

HelloGitHub # 42

One of the simplest UITableView projects