MENU

二叉查找树

一:背景

二叉查找树(Binary Search Tree,简称BST),也称二叉搜索树、有序二叉树、排序二叉树,是指一棵空树或者具有下列性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,为$O(logn)$。

二:具体实现与代码分析

首先大体看下结点和类的结构:

struct Node
{
    int key;
    Node * left;
    Node * right;
    Node(int key)
    {
        this->key = key;
        this->left = this->right = nullptr;
    }
};

class BST
{
private:
    Node * header;
private:
    void destroy(Node * node);
    Node * insert_real(int key, Node *& node);
    Node *& find_real(int key, Node *& node);
    void in_order(Node * node);
public:
    BST();
    ~BST();
    Node * insert(int key);
    Node * find(int key);
    void erase(int key);
    void print();
};

其中,header结点并非根结点,而是我在实现上的一个技巧,header->left指向的才是根结点。

2.1 插入操作

思路很简单,但有一点需要注意,在插入结点以后,需要把它父亲结点的孩子指针指向它,因此这里我们使用了指针引用。

Node * BST::insert_real(int key, Node *& node)
{
    if (node == nullptr)
        return node = new Node(key);

    if (key < node->key)
        return insert_real(key, node->left);
    else if (key > node->key)
        return insert_real(key, node->right);
    else
        return nullptr;
}

Node * BST::insert(int key)
{
    return insert_real(key, header->left);
}

2.2 查找

思路依旧很简单,只需注意的是find_real()返回的是指针引用,之所以这么做,是因为在接下来的删除操作中有妙用。

Node *& BST::find_real(int key, Node *& node)
{
    if (node == nullptr)
        return node;

    if (key < node->key)
        return find_real(key, node->left);
    else if (key > node->key)
        return find_real(key, node->right);
    else
        return node;
}

Node * BST::find(int key)
{
    return find_real(key, header->left);
}

2.3 删除

一个结点的删除有四种情况,如下图,其中红色结点为要被删除的结点:

  • 图一,要删除的结点存在左孩子,也存在右孩子;
  • 图二,要删除的结点仅存在左孩子;
  • 图三,要删除的结点仅存在右孩子;
  • 图四,要删除的结点没有孩子。

对于图二,图三,图四这三种情况,实现很容易。我们重点说下图一的情况。

首先我们要明确一条定理:二叉查找树的中序遍历序列是升序序列。因此对于图一的情况,我们采取的策略就是,找到要删除结点(在中序遍历中)的后继,用后继替换要删除的结点(当然用前驱去替换也是可以的)。详情见下图:

其中,t为要删除的结点,xt的后继结点,yx的父亲结点。

void BST::erase(int key)
{
    Node *& p = find_real(key, header->left);
    if (p)
    {
        Node * t = p;
        if (t->left && t->right)
        {
            // 找到 t 的后继结点
            Node * y = t;
            Node * x = t->right;
            while (x->left)
            {
                y = x;
                x = x->left;
            }

            // 将后继结点的右子树接上它的父亲
            if (y == t)
                y->right = x->right;
            else
                y->left = x->right;

            // 用后继结点替换要删除的结点 t
            p = x;
            x->left = t->left;
            x->right = t->right;
        }
        else
            p = t->left ? t->left : t->right;

        delete t;
    }
}

三:完整代码

/**
*
* author 刘毅(Limer)
* date   2017-08-15
* mode   C++
*/
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

struct Node
{
    int key;
    Node * left;
    Node * right;
    Node(int key)
    {
        this->key = key;
        this->left = this->right = nullptr;
    }
};

class BST
{
private:
    Node * header;
private:
    void destroy(Node * node);
    Node * insert_real(int key, Node *& node);
    Node *& find_real(int key, Node *& node);
    void in_order(Node * node);
public:
    BST();
    ~BST();
    Node * insert(int key);
    Node * find(int key);
    void erase(int key);
    void print();
};

BST::BST()
{
    header = new Node(0);
}

BST::~BST()
{
    destroy(header->left);
    delete header;
    header = nullptr;
}

void BST::destroy(Node * node)
{
    if (node == nullptr)
        return;
    destroy(node->left);
    destroy(node->right);
    delete node;
}

Node * BST::insert_real(int key, Node *& node)
{
    if (node == nullptr)
        return node = new Node(key);

    if (key < node->key)
        return insert_real(key, node->left);
    else if (key > node->key)
        return insert_real(key, node->right);
    else
        return nullptr;
}

Node *& BST::find_real(int key, Node *& node)
{
    if (node == nullptr)
        return node;

    if (key < node->key)
        return find_real(key, node->left);
    else if (key > node->key)
        return find_real(key, node->right);
    else
        return node;
}

void BST::in_order(Node * node)
{
    if (node == nullptr)
        return;

    in_order(node->left);
    cout << node->key << " ";
    in_order(node->right);
}

Node * BST::insert(int key)
{
    return insert_real(key, header->left);
}

Node * BST::find(int key)
{
    return find_real(key, header->left);
}

void BST::erase(int key)
{
    Node *& p = find_real(key, header->left);
    if (p)
    {
        Node * t = p;
        if (t->left && t->right)
        {
            // 找到 t 的后继结点
            Node * y = t;
            Node * x = t->right;
            while (x->left)
            {
                y = x;
                x = x->left;
            }

            // 将后继结点的右子树接上它的父亲
            if (y == t)
                y->right = x->right;
            else
                y->left = x->right;

            // 用后继结点替换要删除的结点 t
            p = x;
            x->left = t->left;
            x->right = t->right;
        }
        else
            p = t->left ? t->left : t->right;

        delete t;
    }
}

void BST::print()
{
    in_order(header->left);
    cout << endl;
}

int main()
{
    BST bst;

    // test "insert"
    bst.insert(7);
    bst.insert(2);
    bst.insert(1); bst.insert(1);
    bst.insert(5);
    bst.insert(3);
    bst.insert(6);
    bst.insert(4);
    bst.insert(9);
    bst.insert(8);
    bst.insert(11); bst.insert(11);
    bst.insert(10);
    bst.insert(12);
    bst.print(); // 1 2 3 4 5 6 7 8 9 10 11 12

    // test "find"
    Node * p = nullptr;
    cout << ((p = bst.find(2)) ? p->key : -1) << endl;   //  2
    cout << ((p = bst.find(100)) ? p->key : -1) << endl; // -1

    // test "erase"
    bst.erase(2);
    bst.print(); // 1 3 4 5 6 7 8 9 10 11 12
    bst.erase(10);
    bst.erase(9);
    bst.print(); // 1 3 4 5 6 7 8 11 12

    return 0;
}

四:时间复杂度

最好情况,二叉查找树同时也是一棵完全二叉树,此时时间复杂度为$O_{best}(logn)$;

最差情况,输入的数据正好是升序或降序序列,此时二叉查找树退化成单链表,时间复杂度变为$O_{worst}(n)$;

平均情况,时间复杂度为$O_{avg}(1.39logn)$,关于它的证明,读者可以参考这里

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码
添加新评论

1 条评论
  1. 看不懂啊!