DSAA之二叉查找树（一）

1. 回顾

　　笔者之前记录的通用树的概念(一)和The Search Tree的Python实现(二)，已经大体上涵盖二叉树的种种，现在重新再针对一些方面做补充。

2. C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#define handle_error(msg) do {perror(msg); exit(-1);}while(0);
typedef struct node{
    int key;
    struct node * leftree;
    struct node * rigtree;
} NODE;

typedef NODE * TREE;

NODE * delete(TREE tree, int key );
NODE * find( TREE tree, int key );
NODE * find_premin(TREE tree);
NODE * find_max(TREE tree);
NODE * insert(int key,TREE tree);
void printf_inorder(TREE tree);
void printf_preorder(TREE tree);
void printf_postorder(TREE tree);

int main (void){
   int key;
   TREE tree;
   printf("input some number to create a tree : (\"done\" to end)");
   for(;;){
     if(scanf("%d",&key) != 1)
        break;
     tree=insert(key,tree);
   }

   printf("inorder : ");
   printf_inorder(tree);
   printf("\n");

   printf("please choose a number you want to delete:\n");
   while(getchar() != '\n');
   scanf("%d",&key);
   delete(tree,key);

   printf("inorder after deleted : ");
   printf_inorder(tree);
   printf("\n");

}



NODE * delete(TREE tree, int key){
    NODE * tmp;
    NODE * tmp2;
    if( tree == NULL)
        return NULL;
    else if( key < tree->key)
        tree->leftree=delete(tree->leftree, key);
    else if( key > tree->key)
        tree->rigtree=delete(tree->rigtree, key);
    else if( tree->leftree && tree->rigtree){
        if((tmp=find_premin(tree->rigtree)) == NULL){
        tmp=tree->rigtree;
            tree->rigtree=tmp->rigtree;
            tree->key=tmp->key;
            free(tmp);
        }
        else{
            tmp2=tmp->leftree;
            tree->key = tmp->leftree->key;
            tmp->leftree=tmp->leftree->rigtree;
            free(tmp2);
        }
    }
    else{
        tmp = tree;
        if( tree->leftree == NULL)
            tree=tree->rigtree;
        else if( tree->rigtree == NULL)
            tree=tree->leftree;
        free(tmp);
    }

    return tree;
}

NODE * find( TREE tree, int key ){
    if( tree == NULL)
        return NULL;
    if( key < tree->key)
        return find( tree->leftree, key);
    else if( key > tree->key)
        return find( tree->leftree, key);
    else
        return tree;
}

NODE * find_premin(TREE tree){
    if( tree->leftree == NULL)
        return NULL;
    if(tree->leftree->leftree == NULL){
    return tree;
    }
    else
        return find_premin(tree->leftree);

}


NODE * find_max(TREE tree){
   if(tree == NULL)
      return NULL;
   if(tree->rigtree == NULL)
      return tree;
   else
      return find_max(tree->rigtree);
}

NODE * insert(int key,TREE tree){
     if( tree == NULL ){
         if((tree =malloc(sizeof(NODE))) == NULL)
            handle_error("malloc");
         tree->key=key;
     }
     else if( key < tree->key)
         tree->leftree=insert(key,tree->leftree);
     else if( key > tree->key)
         tree->rigtree=insert(key,tree->rigtree);
     return tree;
}


void printf_inorder(TREE tree){
     if( tree != NULL){
         printf_inorder(tree->leftree);
         printf("%d ",tree->key);
         printf_inorder(tree->rigtree);
     }
}


void printf_preorder(TREE tree){
     if( tree != NULL){
         printf("%d ",tree->key);
         printf_preorder(tree->leftree);
         printf_preorder(tree->rigtree);
     }
}


void printf_postorder(TREE tree){
     if( tree != NULL){
         printf_postorder(tree->leftree);
         printf_postorder(tree->rigtree);
         printf("%d ",tree->key);
     }
}

　　结果：

[root@localhost ~]# ./4_1 
input some number to create a tree : ("done" to end)6 2 8 1 4 3 done
inorder : 1 2 3 4 6 8 
please choose a number you want to delete:
2
inorder after deleted : 1 3 4 6 8 
[root@localhost ~]# 
[root@localhost ~]# ./4_1 
input some number to create a tree : ("done" to end)6 2 8 1 4 done
inorder : 1 2 4 6 8 
please choose a number you want to delete:
2
inorder after deleted : 1 4 6 8 
[root@localhost ~]# 

　　以上代码将所有删除的情况都考虑了，特别的笔者优化了删除的代码。

3. 删除实现

　　以下是DSAA的实现：

tree_ptr delete( element_type x, SEARCH_TREE T )
{
    tree_ptr tmp_cell, child;
    if( T == NULL )
        error("Element not found");
    else if( x < T->element ) /* Go left */
        T->left = delete( x, T->left );
    else if( x > T->element ) /* Go right */
        T->right = delete( x, T->right );
    else if( T->left && T->right ) /* Two children */
    { /* Replace with smallest in right subtree */
        tmp_cell = find_min( T->right );
        T->element = tmp_cell->element;
        T->right = delete( T->element, T->right );
    }
    else /* One child */
    {
        tmp_cell = T;
        if( T->left == NULL ) /* Only a right child */
            child = T->right;
        if( T->right == NULL ) /* Only a left child */
            child = T->left;
        free( tmp_cell );
        return child;
    }
    return T;
}

　　可以看到else if( T->left && T->right )里面又一次调用了T->right = delete( T->element, T->right );，造成了性能的下降，毕竟find_min已经搜索到了右子树中最小的节点，笔者优化的代码如下：

else if( tree->leftree && tree->rigtree){
       //如果返回NULL，说明该tree->leftree就是最小节点
       if((tmp=find_premin(tree->rigtree)) == NULL){
           tmp=tree->rigtree;
           tree->rigtree=tmp->rigtree;
           tree->key=tmp->key;
           free(tmp);
       }
       else{
           //否则tmp->leftree为tree右子树的最小节点
           tmp2=tmp->leftree;
           tree->key = tmp->leftree->key;
           tmp->leftree=tmp->leftree->rigtree;
           free(tmp2);
       }
 }

　　假设待删除节点的右子树总共有 M $M$个节点，这样将该else if块的时间复杂度从原来的 2O(logM) $2O(logM)$降低为 O(logM) $O(logM)$.

4. 时间复杂度分析

　　DSAA的分析比较繁琐，有一种比较简单的理解：假设我们访问关键字的总共调用了 f $f$次函数，该二叉树总共有N个节点。根据二叉查找树的特点，那么应满足公式：

2f=N,f=log2N $$2^f=N,f=lo{g}_{2}N$$

　　每查找一次，树的深度降低一层。所以二叉树查找树的平均深度为 O(logN) $O(logN)$ ，包括删除在内的所有操作的时间复杂度 O(T)=O(1∗logN)=O(logN) $O(T)=O(1\ast logN)=O(logN)$ ，特别的对于删除操作的中可能出现的 O(logM) $O(logM)$ 的情况，非常清楚的是只有一次会执行 O(logM) $O(logM)$ 的语句块，所以删除操作的时间复杂度为：

O(T)=O(1∗logN−1+logM)=O(logN) $$O(T)=O(1\ast logN-1+logM)=O(logN)$$

　　以上分析为笔者的思考过程，与DSAA或者算法导论的详细论证相比，这种方式更加便捷快速。