数据结构--二叉查找树 Binary Search Tree

Michael阿明

发布于 2021-02-20 10:41:04

4920

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1.二叉查找树概念

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

2.二叉查找树操作

2.1 查找

2.2 插入

2.3 删除

2.4 其他

支持快速地查找最大节点和最小节点、前驱节点和后继节点。
中序遍历二又查找树，可以输出有序的数据序列，时间复杂度是 O(n) ，非常高效。因此，二叉查找树也叫作二叉排序树。

3. 支持重复数据的二叉查找树

通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

在二叉查找树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。两个极端情况的时间复杂度分别是 O(n) 和 O(logn) ，分别对应二叉树退化成链表的情况和完全二叉树。
为了避免时间复杂度的退化，针对二又查找树，我们又设计了一种更加复杂的树，平衡二叉查找树，时间复杂度可以做到稳定的 O(logn)

4 有散列表了，还需要二叉查找树？

散列表时间复杂度可以做到常量级的O(1), 而二叉查找树在比较平衡的情况下, 时间复杂度才是 O(logn), 相对散列表,好像并没有什么优势,那我们为什么还要用二叉查找树呢? 几个原因:
第一, 散列表中的数据是无序存储的, 如果要输出有序的数据,需要先进行排序.而对于二叉查找树来说,我们只需要中序遍历,就可以在O(n)的时间复杂度内,输出有序的数据序列.
第二, 散列表扩容耗时很多,而且当遇到散列冲突时,性能不稳定,尽管二叉查找树的性能不稳定,但是在工程中,我们最常用的平衡二叉查找树的性能非常稳定,时间复杂度稳定在O(logn).
第三, 尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 快. 加上哈希函数的耗时,也不一定就比平衡二又查找树的效率高.
第四, 散列表的构造比二又查找树要复杂,需要考虑的东西很多. 比如散列函数的设计、冲突解决办法、扩容、缩容等.平衡二又查找树只需要考虑平衡性这一个问题,而且这个问题的解决方案比较成熟、固定.
最后,为了避免过多的散列冲突,散列表装载因子不能太大,特别是基于开放寻址法解决冲突的散列表,不然会浪费一定的存储空间.
综合这几点, 平衡二又查找树在某些方面还是优于散列表的, 所以,这两者的存在并不冲突. 我们在实际的开发过程中,需要结合具体的需求来选择使用哪一个.

5 代码实现

/**
 * @description: 二叉查找树
 * @author: michael ming
 * @date: 2019/5/16 23:48
 * @modified by: 
 */
#include <iostream>
#include <random>
#include <time.h>
using namespace std;
template <class T>
class BSTNode
{
public:
    T data;
    BSTNode<T> *left, *right;
    BSTNode():left(NULL), right(NULL){}
    BSTNode(const T& d, BSTNode<T> *l = NULL, BSTNode<T> *r = NULL)
    {
        data = d;   left = l;   right = r;
    }
};
template <class T>
class BST
{
private:
    BSTNode<T>* root;
    int nodeLen;
public:
    BST():root(NULL){}
    ~BST()
    {
        clear(root);
        root = NULL;
    }
    void clear(BSTNode<T>* nodeP)
    {
        if(nodeP == NULL)
            return;
        if (nodeP == NULL)
            return;
        clear(nodeP->left);
        clear(nodeP->right);
        delete nodeP;
    }
    BSTNode<T>* get_root() const {  return root;    }
    bool isEmpty() const {  return root == NULL;    }
    T* search(const T& d) const
    {
        return search(d, root);
    }
    T* search(const T& d, BSTNode<T>* p) const
    {
        while(p != NULL)
        {
            if(d == p->data)
                return &(p->data);
            else if(d < p->data)
                p = p->left;
            else
                p = p->right;
        }
        return 0;
    }
    T* get_max_data()
    {
        if(root == NULL)
            return NULL;
        BSTNode<T>* temp = root;
        while(temp->right != NULL)
            temp = temp->right;
        return &temp->data;
    }
    T* get_min_data()
    {
        if(root == NULL)
            return NULL;
        BSTNode<T>* temp = root;
        while(temp->left != NULL)
            temp = temp->left;
        return &temp->data;
    }
    void insert(const T& d)
    {
        BSTNode<T> *p = root, *prev = NULL;
        while(p != NULL)
        {
            prev = p;
            if(d < p->data)
                p = p->left;
            else
                p = p->right;
        }
        if(root == NULL)
            root = new BSTNode<T>(d);
        else if(d < prev->data)
            prev->left = new BSTNode<T>(d);
        else
            prev->right = new BSTNode<T>(d);
    }
    void del(T d)
    {
        if(root == NULL)
            return;
        BSTNode<T> *p = root, *pfather = NULL;
        while(p != NULL && p->data != d)
        {
            pfather = p;
            if(d > p->data)
                p = p->right;
            else
                p = p->left;
        }
        if(p == NULL)   //没找到d
            return;
        if(p->left != NULL && p->right != NULL)//要删除的节点有2个子节点
        {
            BSTNode<T> *minP = p->right, *minPFather = p;//找到右子树最小的跟要删的交换
            while(minP->left != NULL)   //右子树最小的肯定在左节点
            {
                minPFather = minP;
                minP = minP->left;
            }
            p->data = minP->data;   //把右子树最小的数付给要删除的节点data
            p = minP;   //minP付给p，删除p
            pfather = minPFather;
        }
        //要删除的是叶节点或者只有1个节点
        BSTNode<T>* child;
        if(p->left != NULL)
            child = p->left;
        else if(p->right != NULL)
            child = p->right;
        else
            child = NULL;
        if(pfather == NULL)//p是根节点
            root = child;
        else if(p == pfather->left)
            pfather->left = child;
        else
            pfather->right = child;
        delete p;
        p = NULL;
    }
    int get_height(BSTNode<T>* nodep)  //递归法, 求左右子树高度，较大的+1
    {
        if(nodep == NULL)
            return 0;
        int leftheight = get_height(nodep->left);
        int rightheight = get_height(nodep->right);
        return max(leftheight, rightheight) + 1;
    }
    void inOrderPrint(BSTNode<T>* nodep)    //二叉查找树用中序打印，是有序的
    {
        if (nodep == NULL)
            return;
        inOrderPrint(nodep->left);
        cout << nodep->data << " ";
        inOrderPrint(nodep->right);
    }
};

int main()
{
    BST<int> intBST;
    srand(time(0));
    for(int i = 0; i < 6; ++i)
    {
        intBST.insert(rand());
    }
    intBST.insert(7);
    if(intBST.search(7))
        cout << *(intBST.search(7)) << endl;
    cout << "BST height: " << intBST.get_height(intBST.get_root()) << endl;
    intBST.inOrderPrint(intBST.get_root());
    cout << "max : " << *(intBST.get_max_data()) << ", min : " << *(intBST.get_min_data()) << endl;
    intBST.del(7);
    intBST.inOrderPrint(intBST.get_root());
    return 0;
}