Extended tree (I) - concept and C implementation

Summary

This chapter introduces extended trees . It and " Binary search tree " and "AVL Trees " equally , Are special binary trees . In understanding " Binary search tree " and "AVL Trees " after , Learning to stretch trees is quite easy . As usual , This article will first give a brief introduction to the theoretical knowledge of extended trees , Then give C The realization of language . The following sequence will be given separately C++ and Java Implementation of version ; this 3 The principle of each implementation method is the same , Choose one of them to learn . If there are mistakes or deficiencies in the article , I hope you can point out ！

Catalog
1.  Introduction to the stretch tree
2.  Stretching the tree C Realization
3.  Stretching the tree C The test program

Reprint please indicate the source ： Stretch the tree ( 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)  Stretch the tree ( One ) And Graphic analysis and C The realization of language
(02)  Stretch the tree ( Two ) And C++ The implementation of the
(03)  Stretch the tree ( 3、 ... and ) And Java The implementation of the

Introduction to the stretch tree

Stretch the tree (Splay Tree) It's a binary sort tree , It can be in O(log n) Insert inside complete 、 Search and delete operations . It consists of Daniel Sleator and Robert Tarjan create .
(01) Stretch tree belongs to binary search tree , That is, it has the same properties as binary search tree ： hypothesis x Is any node in the tree ,x Nodes contain keywords key, node x Of key Value to key[x]. If y yes x A node in the left subtree of , be key[y] <= key[x]; If y yes x A node of the right subtree of , be key[y] >= key[x].
(02) In addition to the properties of binary search tree , Another feature of stretch trees is ： When a node is accessed , Stretching the tree will make the node become the root of the tree by rotation . The advantage of this is , The next time you want to access this node , Can quickly access the node .

Suppose you want to perform a series of lookup operations on a binary lookup tree . In order to make the whole search time smaller , The items that are checked frequently should always be near the root of the tree . So I thought of designing a simple method , Refactoring the tree after each lookup , Move the searched items closer to the root of the tree . Stretch tree came into being , It is a self-adjusting binary search tree , It follows the path from a node to the root of the tree , Move this node to the root of the tree through a series of rotations .

Compared with " Binary search tree " and "AVL Trees ", When learning to stretch a tree, you need to focus on " Rotation algorithm of extended tree ".

Stretching the tree C Realization

1. Node definition

typedef int Type;

typedef struct SplayTreeNode {
    Type key;                        //  keyword ( Key value )
    struct SplayTreeNode *left;        //  Left the child 
    struct SplayTreeNode *right;    //  The right child 
} Node, *SplayTree; 

The nodes of the extension tree include several constituent elements :
(01) key -- Is the key word , It is used to sort the nodes of the extended tree .
(02) left -- The left child. .
(03) right -- It's the right child .

External interface

//  The former sequence traversal " Stretch the tree "
void preorder_splaytree(SplayTree tree);
//  In the sequence traversal " Stretch the tree "
void inorder_splaytree(SplayTree tree);
//  After the sequence traversal " Stretch the tree "
void postorder_splaytree(SplayTree tree);

// ( Recursive implementation ) lookup " Stretch the tree x" The middle key value is key The node of 
Node* splaytree_search(SplayTree x, Type key);
// ( Non recursive implementation ) lookup " Stretch the tree x" The middle key value is key The node of 
Node* iterative_splaytree_search(SplayTree x, Type key);

//  Find the smallest node ： return tree The smallest node of an extended tree that is the root node .
Node* splaytree_minimum(SplayTree tree);
//  Find the largest node ： return tree The largest node of the extended tree that is the root node .
Node* splaytree_maximum(SplayTree tree);

//  rotate key The corresponding node is the root node .
Node* splaytree_splay(SplayTree tree, Type key);

//  Insert the node into the extended tree , And return the root node 
Node* insert_splaytree(SplayTree tree, Type key);

//  Delete node (key Is the value of the node ), And return the root node 
Node* delete_splaytree(SplayTree tree, Type key);

//  Destroy the stretch tree 
void destroy_splaytree(SplayTree tree);

//  Print stretch tree 
void print_splaytree(SplayTree tree, Type key, int direction);

2. rotate

Rotating code

/* 
 *  rotate key The corresponding node is the root node , And return the root node .
 *
 *  Be careful ：
 *   (a)： There are in the stretching tree " The key value is key The node of ".
 *           take " The key value is key The node of " Rotate to root node .
 *   (b)： It doesn't exist in the stretched tree " The key value is key The node of ", also key < tree->key.
 *      b-1 " The key value is key The node of " If the precursor node of exists , take " The key value is key The node of " The precursor node of is rotated to the root node .
 *      b-2 " The key value is key The node of " If the precursor node of exists , Means that the ,key Smaller than any key value in the tree , So at this time , Rotate the smallest node to the root node .
 *   (c)： It doesn't exist in the stretched tree " The key value is key The node of ", also key > tree->key.
 *      c-1 " The key value is key The node of " If the successor node of exists , take " The key value is key The node of " The subsequent node of is rotated to the root node .
 *      c-2 " The key value is key The node of " If the successor node of does not exist , Means that the ,key Larger than any key value in the tree , So at this time , Rotate the largest node to the root node .
 */
Node* splaytree_splay(SplayTree tree, Type key)
{
    Node N, *l, *r, *c;

    if (tree == NULL) 
        return tree;

    N.left = N.right = NULL;
    l = r = &N;

    for (;;)
    {
        if (key < tree->key)
        {
            if (tree->left == NULL)
                break;
            if (key < tree->left->key)
            {
                c = tree->left;                           /* 01, rotate right */
                tree->left = c->right;
                c->right = tree;
                tree = c;
                if (tree->left == NULL) 
                    break;
            }
            r->left = tree;                               /* 02, link right */
            r = tree;
            tree = tree->left;
        }
        else if (key > tree->key)
        {
            if (tree->right == NULL) 
                break;
            if (key > tree->right->key) 
            {
                c = tree->right;                          /* 03, rotate left */
                tree->right = c->left;
                c->left = tree;
                tree = c;
                if (tree->right == NULL) 
                    break;
            }
            l->right = tree;                              /* 04, link left */
            l = tree;
            tree = tree->right;
        }
        else
        {
            break;
        }
    }

    l->right = tree->left;                                /* 05, assemble */
    r->left = tree->right;
    tree->left = N.right;
    tree->right = N.left;

    return tree;
}

The function of the above code ： take " The key value is key The node of " Rotate to root node , And return the root node . Its handling includes ：
(a)： There are in the stretching tree " The key value is key The node of ".
        take " The key value is key The node of " Rotate to root node .
(b)： It doesn't exist in the stretched tree " The key value is key The node of ", also key < tree->key.
        b-1) " The key value is key The node of " If the precursor node of exists , take " The key value is key The node of " The precursor node of is rotated to the root node .
        b-2) " The key value is key The node of " If the precursor node of exists , Means that the ,key Smaller than any key value in the tree , So at this time , Rotate the smallest node to the root node .
(c)： It doesn't exist in the stretched tree " The key value is key The node of ", also key > tree->key.
        c-1) " The key value is key The node of " If the successor node of exists , take " The key value is key The node of " The subsequent node of is rotated to the root node .
        c-2) " The key value is key The node of " If the successor node of does not exist , Means that the ,key Larger than any key value in the tree , So at this time , Rotate the largest node to the root node .

The following are examples of a To illustrate .

Look in the stretched tree below 10, Including " Right hand "  --> " Right link "  --> " Combine " this 3 Step .

Uploading … Re upload cancel

First step ： Right hand
Corresponding to "rotate right" part

Uploading … Re upload cancel

The second step ： Right link
Corresponding to "link right" part

Uploading … Re upload cancel

The third step ： Combine
Corresponding to "assemble" part

Uploading … Re upload cancel

Tips ： If you look in the stretched tree above "70", Is exactly the same as " Example 1" symmetry , The corresponding operations are "rotate left", "link left" and "assemble".
Other things , for example " lookup 15 yes b-1 The situation of , lookup 5 yes b-2 The situation of " wait , These are relatively simple , You can analyze by yourself .

3. Insert

/* 
 *  Insert the node into the extended tree ( No rotation )
 *
 *  Parameter description ：
 *     tree  Extend the root node of the tree 
 *     z  Inserted node 
 *  Return value ：
 *      The root node 
 */
static Node* splaytree_insert(SplayTree tree, Node *z)
{
    Node *y = NULL;
    Node *x = tree;

    //  lookup z Where to insert 
    while (x != NULL)
    {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else if (z->key > x->key)
            x = x->right;
        else
        {
            printf(" Inserting the same node is not allowed (%d)!\n", z->key);
            //  Release the requested node , And back to tree.
            free(z);
            return tree;
        }
    }

    if (y==NULL)
        tree = z;
    else if (z->key < y->key)
        y->left = z;
    else
        y->right = z;

    return tree;
}

/*
 *  Create and return the extended tree node .
 *
 *  Parameter description ：
 *     key  Is the key value .
 *     parent  Is the parent node .
 *     left  The left child. .
 *     right  It's the right child .
 */
static Node* create_splaytree_node(Type key, Node *left, Node* right)
{
    Node* p;

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

    return p;
}

/* 
 *  New node (key), Then insert it into the extended tree , And rotate the inserted node into the root node 
 *
 *  Parameter description ：
 *     tree  Extend the root node of the tree 
 *     key  Insert the key value of the node 
 *  Return value ：
 *      The root node 
 */
Node* insert_splaytree(SplayTree tree, Type key)
{
    Node *z;    //  New node 

    //  If the new node fails , Then return to .
    if ((z=create_splaytree_node(key, NULL, NULL)) == NULL)
        return tree;

    //  Insert node 
    tree = splaytree_insert(tree, z);
    //  The nodes (key) Rotate to root node 
    tree = splaytree_splay(tree, key);
}

External interface : insert_splaytree(tree, key) It is an interface provided to the outside , Its function is to create new nodes ( The key value of the node is key), And insert the node into the extended tree ; then , Rotate this node to the root node .

Internal interface : splaytree_insert(tree, z) It's the internal interface , Its function is to connect nodes z Insert into tree in .splaytree_insert(tree, z) Will be z Insert into tree In the middle of the day , Only will tree Think of it as a binary search tree , And it is not allowed to insert the same node .

4. Delete

Delete interface

/* 
 *  Delete node (key Is the key value of the node ), And return the root node .
 *
 *  Parameter description ：
 *     tree  Extend the root node of the tree 
 *     z  Deleted nodes 
 *  Return value ：
 *      The root node ( The root node is the precursor node of the deleted node )
 *
 */
Node* delete_splaytree(SplayTree tree, Type key)
{
    Node *x;

    if (tree == NULL) 
        return NULL;

    //  The search key value is key The node of , If it cannot be found, return directly .
    if (splaytree_search(tree, key) == NULL)
        return tree;

    //  take key The corresponding node is rotated to the root node .
    tree = splaytree_splay(tree, key);

    if (tree->left != NULL)
    {
        //  take "tree The precursor node of " Rotate to root node 
        x = splaytree_splay(tree->left, key);
        //  remove tree node 
        x->right = tree->right;
    }
    else
        x = tree->right;

    free(tree);

    return x;
}

delete_splaytree(tree, key) The role of is ： Delete the key value of key The node of .
It will first find the key value of key The node of . If not found , Then return directly . If found , Then rotate the node to the root node , Then delete the node .

Be careful ： About stretching trees " 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 complete source code of the extended tree given later , Have given these API Implementation code . These interfaces are simple ,Please RTFSC(Read The Fucking Source Code)！

Stretching the tree C Realization ( Complete source code )

Stretch the header file of the tree (splay_tree.h)

 View Code

Implementation file of extension tree (splay_tree.c)

 View Code

Test program of stretching tree (splaytree_test.c)

 View Code

Stretching the tree C The test program

The test program running results of the extended tree are as follows ：

==  Add... In turn : 10 50 40 30 20 60 
==  The former sequence traversal : 60 30 20 10 50 40 
==  In the sequence traversal : 10 20 30 40 50 60 
==  After the sequence traversal : 10 20 40 50 30 60 
==  minimum value : 10
==  Maximum : 60
==  Tree details : 
60 is root
30 is 60's   left child
20 is 30's   left child
10 is 20's   left child
50 is 30's  right child
40 is 50's   left child

==  Rotate nodes (30) Root node 
==  Tree details : 
30 is root
20 is 30's   left child
10 is 20's   left child
60 is 30's  right child
50 is 60's   left child
40 is 50's   left child

The main flow of the test program is ： Create a new stretch tree , Then insert into the extended tree one by one 10,50,40,30,20,60. After inserting these data , The nodes of the extended tree are 60; here , Then rotate the node , bring 30 Become the root node .
Insert... In turn 10,50,40,30,20,60 The schematic diagram is as follows ：

Uploading … Re upload cancel

take 30 The schematic diagram of rotating to root node is as follows ：

Uploading … Re upload cancel