最坏的二叉搜索树(Binary Search Tree)



  • 二叉搜索树的缺点:

    既然标题写着最坏的二叉搜索树就来说下原因吧,随着元素的插入和删除,二叉搜索树的高度是变化的,如果n格关键字按严格递归的次序被插入,则这棵树一定是高度为n-1的一条链。而二叉树的时间复杂度是0(h),这种最坏情况的搜索速度等同遍历链表。
    那既然二叉搜索树存在着这么『严重』的缺点我们为什么还要提到并去学习他呢?因为它是红黑树,B树的基础知识😀

    /* 
     * File:   bistree.h
     * Author: guluting
     *
     * Created on 2018年7月18日, 下午1:28
     */
    
    #ifndef BITREE_H
    #define BITREE_H
    
    
    #ifdef __cplusplus
    extern "C" {
    #endif
    #define KEY_SIZE 20
    #define TREE_NODE(tree) (tree->root)
        
        typedef struct _bistree_node_t{
            char key[KEY_SIZE];
            struct _bistree_node_t *parent;
            struct _bistree_node_t *left;
            struct _bistree_node_t *right;
            int size;
            char data[0];
        }bistree_node_t;
        
        typedef struct _bistree_t{
            int size;
            bistree_node_t *root;
        }bistree_t;
        
        
        typedef void (*walk_callback)(bistree_node_t *node);
        
        bistree_t* bistree_create(void);
        bistree_node_t* bistree_create_node(const char *key,const void *data,int size);
        bistree_node_t* bistree_search(bistree_node_t *node,const char *key);
        bistree_node_t* bistree_minimum(bistree_node_t *node);
        void bistree_insert(bistree_t *tree,bistree_node_t *node);
        void bistree_inorder_walk(bistree_node_t *node,walk_callback callback);
        void bistree_delete(bistree_t *tree,bistree_node_t *node);
        
    #ifdef __cplusplus
    }
    #endif
    
    #endif /* BITREE_H */
    

    /*
     * 二叉搜索树(非线程安全)
     */
    #include <assert.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include "bistree.h"
    
    
    /**
     * 用V子树替换U子树
     * @param [in] tree : 树结构体
     * @param [in] u : 需要被替换的节点
     * @param [in] v : 
     */
    static void bistree_transplant(bistree_t *tree,bistree_node_t *u,bistree_node_t *v){
        if(u->parent == NULL){
            // 一个节点没有父节点,证明它就是root节点
            tree->root = v;
        }else if(u == u->parent->left){ 
            u->parent->left = v;
        }else{
            u->parent->right = v;
        }
        
        if (v != NULL){
            v->parent = u->parent;
        }
    }
    
    
    /**
     * 创建二叉搜索树结构体
     * @retval : 树结构体
     */
    bistree_t* bistree_create(void){
        bistree_t *tree = malloc(sizeof(bistree_t));
        if(tree){
            memset(tree,0,sizeof(bistree_t));
        }
        return tree;
    }
    
    
    /**
     * 创建并初始化树节点
     * @param [in] key  : 键
     * @param [in] data : 数据指针
     * @param [in] size : 数据长度
     * @retval : 节点结构体指针
     */
    bistree_node_t* bistree_create_node(const char *key,const void *data,int size){
        assert(size>=0 && strlen(key)<=KEY_SIZE);
        bistree_node_t *node = malloc(sizeof(bistree_node_t)+size);
        if(node){
            memcpy(node->data,data,size);
            strcpy(node->key,key);
            node->size = size;
            node->parent = NULL;
            node->left = NULL;
            node->right = NULL;
        }
        return node;
    }
    
    
    /**
     * 在树中插入新节点
     * @param [in] tree : 树结构体
     * @param [in] node : 待插入的节点
     */
    void bistree_insert(bistree_t *tree,bistree_node_t *node){
        bistree_node_t *parent,*child;
        parent = NULL;
        child = tree->root;
        while (child) {
            parent = child;
            if (strcmp(node->key,child->key) < 0){
                child = child->left;
            }else{
                child = child->right;
            }
        }
        node->parent = parent;
        if(parent == NULL){
            tree->root = node;
        }else if(strcmp(node->key,parent->key) < 0){
            parent->left = node;
        }else{
            parent->right = node;
        }
    }
    
    
    /**
     * 中序遍历树(子树)
     * @param [in] node     : 起始节点
     * @param [in] callback : 遍历每个节点时的回调函数
     */
    void bistree_inorder_walk(bistree_node_t *node,walk_callback callback){
        if(node){
            bistree_inorder_walk(node->left,callback);
            if(callback){
                callback(node);
            }
            bistree_inorder_walk(node->right,callback); 
        }
    }
    
    
    /**
     * 通过KEY搜索几诶但
     * @param [in] node : 起始节点
     * @param [in] key  : 键
     * @retval : 搜索成功返回node指针,失败返回NULL
     */
    bistree_node_t* bistree_search(bistree_node_t *node,const char *key){
        if(node == NULL || strcmp(key,node->key) == 0){
            return node;
        }
        if (strcmp(key,node->key) < 0){
            return bistree_search(node->left,key);
        }else{
            return bistree_search(node->right,key);
        }
    }
    
    
    /**
     * 返回树中key最小的节点
     * @param [in] node : 起始节点
     * @retval : 以起始节点为起点的最小的key值
     */
    bistree_node_t* bistree_minimum(bistree_node_t *node){
        while (node != NULL) {
            node = node->left;
        }
        return node;
    }
    
    
    /**
     * 删除节点
     * @param [in] tree : 树结构体
     * @param [in] node : 待删除的节点
     */
    void bistree_delete(bistree_t *tree,bistree_node_t *node){
        if(node->left == NULL){
            bistree_transplant(tree,node,node->right);
        }else if(node->right == NULL){
            bistree_transplant(tree,node,node->left);
        }else{
            // 获取待删除节点右子树中的最小节点(遍历到没有左子树的节点为止)
            bistree_node_t *child = bistree_minimum(node->right);
            if(child->parent != node){
                // 只有当前node的右子树的parent才会==node
                bistree_transplant(tree,child,child->right);
                child->right = node->right;
                child->right->parent = child;
            }
            bistree_transplant(tree,node,child);
            child->left = node->left;
            child->left->parent = child;
        }
        free(node);
    }
    

    测试代码:

    /* 
     * File:   main.cpp
     * Author: guluting
     *
     * Created on 2018年7月18日, 上午10:51
     */
    
    #include <cstdlib>
    #include <stdio.h>
    #include "mem/bistree.h"
    
    using namespace std;
    
    void callback(bistree_node_t *node){
        printf("%s->%s\n",node->key,node->data);
    }
    
    /*
     * 
     */
    int main(int argc, char** argv) {
        bistree_t *tree = bistree_create();
        bistree_node_t *node = NULL;
        node = bistree_create_node("15","15",3);
        bistree_insert(tree,node);
        node = bistree_create_node("06","06",3);
        bistree_insert(tree,node);
        node = bistree_create_node("03","03",3);
        bistree_insert(tree,node);
        node = bistree_create_node("07","07",3);
        bistree_insert(tree,node);
        node = bistree_create_node("02","02",3);
        bistree_insert(tree,node);
        node = bistree_create_node("04","04",3);
        bistree_insert(tree,node);
        node = bistree_create_node("13","13",3);
        bistree_insert(tree,node);
        node = bistree_create_node("09","09",3);
        bistree_insert(tree,node);
        node = bistree_create_node("18","18",3);
        bistree_insert(tree,node);
        node = bistree_create_node("17","17",3);
        bistree_insert(tree,node);
        node = bistree_create_node("20","20",3);
        bistree_insert(tree,node);
        
        bistree_inorder_walk(TREE_NODE(tree),callback);
        printf("######################\n");
        
        bistree_delete(tree,bistree_search(tree->root,"20"));
        bistree_delete(tree,bistree_search(tree->root,"18"));
        bistree_inorder_walk(TREE_NODE(tree),callback);
        
        return 0;
    }
    

Log in to reply