二叉搜索树的缺点:

既然标题写着最坏的二叉搜索树就来说下原因吧,随着元素的插入和删除,二叉搜索树的高度是变化的,如果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;
}