DataStruct in c(二)BST树

BST树(Binary Search Tree)即二叉搜索树。二叉搜索树的结构表现为左子树中所有节点的值一定小于根节点的值,而右子树所有节点的值大于根节点的值。二叉搜索树是一种基本的查找树ADT,其可以应用在查找上,感觉类似于二分查找,在二叉搜索树的基础上也延伸出许多其他查找树。《数据结构与算法分析 ————C语言描述》一书中对BST有详细的讲解。由于树本身是一个递归的概念,通过学习树这一结构,对递归和有了更深入的理解。之前最开始用C实现链表时,大部分和C指针有关的内容都忘的一干二净了,更着书过了一边后大概能想起来指针是个什么东西了。。。

对 BST 基本实现创建、插入、查找、删除等操作。

  • BST.h

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    //左小右大
    //BST binarySearchTree 二叉搜索树,二叉排序树

    typedef struct Node *BSTree;
    typedef struct Node *Position;
    typedef int ElementType;

    struct Node {
    ElementType element;
    BSTree left;
    BSTree right;
    };

    BSTree makeEmpty ();
    BSTree create ();
    BSTree insert (BSTree T, ElementType e);
    BSTree find (BSTree T, ElementType e);
    BSTree findMax (BSTree T);
    BSTree findMin (BSTree T);
    BSTree del (BSTree T, ElementType e);

    char* strmlt (int d);
    void preOrder (BSTree T, int depth);
    void inOrder (BSTree T, int depth);
    void postOrder (BSTree T, int depth);
  • BST.c

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    #include "Tree.h"

    int main (void)
    {
    BSTree T = create();
    return 0;
    }


    BSTree makeEmpty ()
    {
    BSTree T = (BSTree) malloc ( sizeof(struct Node) );

    T->element = 0;
    T->left = NULL;
    T->right = NULL;

    return T;
    }


    BSTree create ()
    {
    BSTree T = makeEmpty();

    printf("input some integer into Tree in turn: (q to quit) \n");
    while(1){
    ElementType val;
    if(scanf("%d", &val) == 0)
    break;
    else
    insert(T, val);
    }

    return T;
    }

    BSTree insert (BSTree T, ElementType e)
    {
    if(T == NULL){
    T = malloc( sizeof(struct Node) );
    T->element = e;
    T->left = NULL;
    T->right = NULL;
    }else if(e < T->element){
    T->left = insert(T->left, e);
    }else if(e > T->element){
    T->right = insert(T->right, e);
    }

    return T;
    }

    BSTree find (BSTree T, ElementType e)
    {
    if (T == NULL)
    return NULL;

    if(e == T->element)
    return T;
    else if(e < T->element)
    return find(T->left, e);
    else
    return find(T->right, e);
    }

    BSTree findMax (BSTree T)
    {
    if(T->right == NULL)
    return T;
    else
    return findMax(T->right);
    }

    BSTree findMin (BSTree T)
    {
    if(T->left == NULL)
    return T;
    else
    return findMin(T->left);
    }


    BSTree del (BSTree T, ElementType e)
    {
    Position TmpNode = NULL;

    if( T == NULL ){
    printf( "ELEMENT NOT FOUND" );
    return NULL;
    } else if ( e < T->element )
    T->left = del(T->left, e);
    else if( e > T->element )
    T->right = del(T->right, e);
    // e不大于 T->ele,不小于 T->ele,同时T != NULL
    // 此时即找到了要删除的元素,对该节点含有两个子节点和单个节点或没有节点进行分析
    else if( T->left && T->right ){
    /* 含有两个字节点的情况 */
    /* 应当选择左子树最大的元素或右字数最小的元素代替改节点,这里我们对右子树操作*/
    /* 随后递归对子树执行删除的例程 */
    TmpNode = findMin( T->right );
    T->element = TmpNode->element;
    T->right = del( T->element, T->right );
    } else {
    /* 一个子节点或没有子节点 */
    TmpNode = T;

    if (T->left == NULL)
    T = T->right;
    else if (T->right == NULL)
    T = T->left;

    free(TmpNode);
    }

    return T;
    }

    //先序遍历 根节点,左,右
    //遍历的 depth 参数用作将深度为 depth 的元素前输出 {depth} 个 TAB 用以表示缩进
    void preOrder (BSTree T, int depth)
    {
    if(T != NULL){
    printf("%s%d\n", strmlt(depth), T->element);
    preOrder(T->left, depth + 1);
    preOrder(T->right, depth + 1);
    }
    }

    void inOrder (BSTree T, int depth)
    {
    if(T != NULL){
    preOrder(T->left, depth + 1);
    printf("%s%d\n", strmlt(depth), T->element);
    preOrder(T->right, depth + 1);
    }
    }

    void postOrder (BSTree T, int depth)
    {
    if(T != NULL){
    preOrder(T->left, depth + 1);
    preOrder(T->right, depth + 1);
    printf("%s%d\n", strmlt(depth), T->element);
    }
    }


    //配合遍历函数使用,使输出格式化
    char* strmlt (int depth){
    char* r = (char*) malloc ( sizeof(char) * 255 );
    for(int i = 0; i < depth; ++i){
    strcat(r, " ");
    }

    return r;
    }

时间复杂度分析

对于一颗有7个 Node 的BST(元素为[1, 2, 3, 4, 5, 6, 7]),可能有多种不同的排列方式,如下图。

对于上图情况,如需查找element值为7的元素,根据 find() 例程可知,图二需要话费更多的次数去查找该元素。由此可知,对于 BST 的大部分操作,其时间复杂度为 O(d)(d代表树的深度)。在平均情况下,树的深度为 O(logN)(可用递推关系证明,具体也没有看懂,数学渣QAQ)。

但是,对于 del() 删除例程,由于我们总是用右子树中的一个节点来代替被删除的节点。会造成右边的树结构变得稀疏。实际可以通过随机地使用左子树中节点或右子树中的节点来代替被删除的节点。或通过 懒惰删除 来进行优化。即便是存在不平衡的问题,也可以通过其他的方式来优化。(未完待续)

懒惰删除( lazy deletion ):当一个元素被删除时,它仍留在树中,只是做了一个被删除的机号。这种做法在有重复关键字的时候特别流行,因为次记录出现频率数的域可以减少1。如果树种实际节点树和 “被删除” 的节点数相同,那么树的深度预计只上升了一个小的常数,因此,存在一个与懒惰删除相关的非常小的时间损耗。再有,如果被删除的关键字是重新插入的,那么分配一个新单元的开销就减少了。

————《数据结构与算法分析 ————C语言描述》