【二叉树（二）】：二叉搜索树

1、定义

二叉搜索树是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：

二叉搜索树是以一棵二叉树来组织，每个节点就是一个对象，包括key、卫星数据，除此之外还包括一些为了维持树结构所需要的信息：left、right、parent，分别指向左孩子、右孩子、父节点。其中如果孩子节点或者父节点不存在时，用NULL表示。根节点是树中唯一一个父节点为NULL的节点。

性质：

每个元素都有一个关键字，并且任意两个元素的关键字都不同；因此，所有关键字都是唯一的；
如果节点的左子树不空，则左子树上所有结点的值均小于等于它的根结点的值；
如果节点的右子树不空，则右子树上所有结点的值均大于等于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树；

二叉搜索树的结构如下图所示：

【二叉树（二）】：二叉搜索树

2、基本操作

2.1、插入

确定该搜索数中是否存在该元素，如果存在直接替换；如果不存在，将该元素插入最终搜索点的左、右

孩子节点中。

复杂度：O(log2n）~O(n)

二叉搜索树的两种极端情况：

【1】完全二叉树，所有节点尽量填满树的每一层，上一层填满后还有剩余节点的话，则由左向右尽量填满下一层。如上图BST所示，即为一颗完全二叉树；

【2】每一层只有一个节点的二叉树。如下图SP_BST所示：

【二叉树（二）】：二叉搜索树

第【1】种情况下的查找次数分析：完美二叉树中树的深度与节点个数的关系为：n=2^(d+1)-1。设深度为 d的完全二叉树节点总数为nc ，因为完全二叉树中深度为 d的叶子节点层不一定填满，所以有nc<2^(d+1)-1 ，即：d+1>log2(nc+1)，因为d+1 为查找次数，所以完全二叉树中查找次数为：logx(nc+1)。

第【2】种情况下，树中每层只有一个节点，该状态的树结构更倾向于一种线性结构，节点的查询类似于数组的遍历，查询复杂度为O(n) 。

所以二叉搜索树的查询复杂度为 O(log2(n))~O(n)。

作者：zhipingChen

链接：https://www.jianshu.com/p/ff4b93b088eb

来源：简书

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.2、删除

1）如果删除点为叶子节点 ,直接释放叶子节点；如果该节点为根，则令根为NULL;

2）如果删除的节点只有一颗非空的子树 ,如果p没有父节点（p为根节点），则p的唯一子树的

根节点成为搜索树的根节点；如果p有父节点pp，则修改pp的指针域，使其指向p唯一的孩子，并释放p;

3）如果删除的节点p具有两颗非空的子树 ,将该节点元素替换为左子树的最大元素或右子树的最小元素，然后将该节点删除。

注意：如何查找左子树的最小值或右子树的最大值？

左子树的最大值：沿着右子树的左孩子指针移动，直到指针为NULL。

右子树的最小值：沿着左子树的右孩子指针移动，直到指针为NULL。

复杂度：O(log2n）~O(n)

2.3、查询

查询节点过程是，比较元素值是否相等，相等则返回，不相等则判断大小情况，迭代查询左、右子树，直到找到相等的元素，或子节点为空，返回节点不存在
插入节点的过程是，比较元素值是否相等，相等则返回，表示已存在，不相等则判断大小情况，迭代查询左、右子树，直到找到相等的元素，或子节点为空，则将节点插入该空节点位置。
复杂度：O(log2n）~O(n)

3、代码实现

//二叉树节点的定义
template <class T>
class BTreeNode
{
public:
    T element_;             //存储的元素
    BTreeNode<T> *left_;    //指向左子树
    BTreeNode<T> *right_;   //指向右子树
    BTreeNode<T> *parent_;  //指向父节点
    int height_;            //以当前节点为根树的高度（用于AVL树的节点）
    RBTColor color_;        //当前节点的颜色（用于红黑树的节点）
public:
    BTreeNode():height_(0),color_(BLACK){left_=right_=parent_= nullptr;}

    BTreeNode(const BTreeNode<T> &theClass)
            :element_(theClass.element_),
             left_(theClass.left_),
             right_(theClass.right_),
             parent_(theClass.parent_),
             height_(0),
             color_(BLACK){}

    BTreeNode(const T &theElement):element_(theElement),
                                   left_(nullptr),right_(nullptr),parent_(nullptr),height_(0),color_(BLACK){}

    BTreeNode(const T &theElement,BTreeNode<T> *left,BTreeNode<T> *right)
            :element_(theElement),left_(left),right_(right),parent_(nullptr),height_(0),color_(BLACK){}

    BTreeNode(const T &theElement,BTreeNode<T> *left,BTreeNode<T> *right,BTreeNode<T> *parent)
            :element_(theElement),left_(left),right_(right),parent_(parent),height_(0),color_(BLACK){}

    BTreeNode(const T &theElement,BTreeNode<T> *left,BTreeNode<T> *right, RBTColor c)
            :element_(theElement),left_(left),right_(right),parent_(nullptr),height_(0),color_(c){}

    BTreeNode(const T &theElement,BTreeNode<T> *left,BTreeNode<T> *right,BTreeNode<T> *parent,RBTColor c)
            :element_(theElement),left_(left),right_(right),parent_(parent),height_(0),color_(c){}
};

/*******************************************
*                二叉搜索树的实现              *
/*******************************************/
template <class K,class E>
class BinarySearchTree
{
public:
    BinarySearchTree():phead_(nullptr),size_(0){}
    ~BinarySearchTree();

    //判断字典是否为空
    bool empty() const{return size_==0;}
    //返回字典的大小
    int size() const{return size_;}
    //返回根节点
    BTreeNode<pair<const K,E>> *get_root(){return phead_;}

    // 搜索字典
    pair<const K, E>* find(const K&);

    //删除字典
    void erase(const K&);

    //插入字典
    void insert(const pair<const K, E>&);

    //关键字按升序输出
    void ascend();
private:
    void delete_(BTreeNode<pair<const K,E>> *node);//删除搜索二叉树
    void inorder_(BTreeNode<pair<const K,E>> *node);//中序遍历
private:
    BTreeNode<pair<const K,E>> *phead_;
    size_t  size_;
};

template <class K,class E>
void BinarySearchTree<K,E>::delete_(BTreeNode<pair<const K, E>> *node)
{
    if(node!= nullptr){
        BTreeNode<pair<const K,E>> *cur=node;
        delete_(node->left_);
        delete_(node->right_);
        delete cur;
        cur= nullptr;
    }
}

template <class K,class E>
BinarySearchTree<K,E>::~BinarySearchTree()
{
    if(phead_!= nullptr){
        delete_(phead_);
        size_=0;
    }
}

template <class K,class E>
pair<const K, E>* BinarySearchTree<K,E>::find(const K &theKey)
{
    BTreeNode<pair<const K,E>> *p= phead_;

    while(p!= nullptr){
        if(theKey < p->element_.first){
            p=p->left_;
        }else if(theKey > p->element_.first){
            p=p->right_;
        }else{
            return &p->element_;
        }
    }

    return nullptr;
}

template <class K,class E>
void BinarySearchTree<K,E>::insert(const pair<const K, E> &theValue)
{
    //获取根节点
    BTreeNode<pair<const K,E>> *p=phead_,*pp= nullptr;

    //在搜索树中搜索吧该节点
    while(p!= nullptr){
        //保存当前节点父节点
        pp=p;
        if(theValue.first < p->element_.first){
            p=p->left_;
        }else if(theValue.first > p->element_.first){
            p=p->right_;
        }else{//如果存在搜索树种，直接替换
            p->element_.second=theValue.second;
            return ;
        }
    }

    //创建节点
    BTreeNode<pair<const K,E>> *newNode=
            new BTreeNode<pair<const K,E>>(theValue);

    //插入节点
    if(phead_!= nullptr){//获取当前节点的子节点，并插入节点
        if(theValue.first<pp->element_.first){
            pp->left_=newNode;
        }else{
            pp->right_=newNode;
        }
    }else{//如果根节点为空，直接在根节点插入节点
        phead_=newNode;
    }

    ++size_;
}

template <class K,class E>
void BinarySearchTree<K,E>::erase(const K &theKey)
{
    //查找关键字
    BTreeNode<pair<const K,E>> *p=phead_,
            *pp= nullptr;

    while(p!= nullptr && p->element_.first!=theKey){
        pp=p;
        if(theKey < p->element_.first){
            p=p->left_;
        } else{
            p=p->right_;
        }
    }
    //如果不存在关键字thekey
    if(p== nullptr){
        return ;
    }

    //如果p有两个非空子树
    if(p->left_!= nullptr && p->right_!= nullptr){
        //搜索p的走左子树最大节点
        BTreeNode<pair<const K,E>> *max_child=p->left_,
                *p_max= p;
        while(max_child->right_!= nullptr){
            p_max=max_child;
            max_child=max_child->right_;
        }

        //将最大元素移动到p(注意key为const，不能直接赋值)
        BTreeNode<pair<const K,E>> *q=new BTreeNode<pair<const K,E>>
                (max_child->element_,p->left_,p->right_);

        if(pp== nullptr){
            phead_=q;
        }else if(p==pp->left_){
            pp->left_=q;
        }else{
            pp->right_=q;
        }
        if(p_max==p) pp=q;
        else pp=p_max;

        delete p;
        p=max_child;
    }

    //如果p最多只有一个孩子
    BTreeNode<pair<const K,E>> *c;
    if(p->left_!= nullptr){
        c=p->left_;
    } else{
        c=p->right_;
    }

    //删除p
    if(p==phead_){
        phead_=c;
    } else{
        if(p==pp->left_){
            pp->left_=c;
        } else{
            pp->right_=c;
        }
    }

    --size_;
    delete p;
}

template<class K,class E>
void BinarySearchTree<K,E>::inorder_(BTreeNode<pair<const K, E>> *node)
{
    if(node== nullptr) {
        return;
    }

    inorder_(node->left_);
    cout<<node->element_.first<<"->"<<node->element_.second<<endl;
    inorder_(node->right_);
}

template<class K,class E>
void BinarySearchTree<K,E>::ascend()
{
    if(phead_== nullptr) {
        return;
    }

    inorder_(phead_);
}

总结

二叉搜索树的节点查询、构造和删除性能，与树的高度相关，如果二叉搜索树能够更“平衡”一些，避免了树结构向线性结构的倾斜，则能够显著降低时间复杂度。二叉搜索树的存储方面，相对于线性结构只需要保存元素值，树中节点需要额外的空间保存节点之间的父子关系，所以在存储消耗上要高于线性结构。

详细代码可以参考我的github代码:https://github.com/kingqiuol/algorithm_practice/blob/master/assignment5/search_tree.h

参考链接：

数据结构（二）：二叉搜索树（Binary Search Tree）

【二叉树（二）】：二叉搜索树

1、定义

2、基本操作

3、代码实现

总结

继续阅读

数据结构（c/c++）：3.线性表之静态链表代码实现

线性链表--链式链表实现（c语言）

C语言实现链表逆序

【二叉树（一）】：二叉树简单实现

数据结构：树与二叉树_二叉树_定义

前言--03---二叉树、二叉搜索树、平衡二叉树、红黑树、数据结构 Data Structure Visualizations二叉树（Binary Tree）二叉搜索树（Binary Search Tree）平衡二叉树（AVL Tree）红黑树（Red-Black Tree）

非二叉树转换成二叉树

对字符串 “ABC” 所有子集的列举

Uva(Digit Generator，1583) 生成元

十大常用算法

排序算法-插入排序(java实现)

排序算法之冒泡排序（一）

算法图解读书笔记第8章贪婪算法

算法图解读书笔记第3章递归