《算法导论》第12章：二叉搜索树

基本性质

左子树 < 根 < 右子树

基本操作 O(logn)

1.查找最大、最小关键字元素
2.查找前驱和后继
查找后继分为两种情况：
①右结点存在，即只需要找到右子树中最小的元素就好了
②右结点不存在，此时就要向亲代查找，直到找到右上方的亲代
3.插入和删除
插入：类似于一根小棒在树中移动，最终把待插入元素放置在一个空结点上
删除：较复杂，有很多情况

利用二叉树进行排序 Ω(n*logn)

不断地插入节点，最后中序遍历即可——元素之间的比较和快速排序相同，故它们的运行效率相似。若采用随机化策略，则平均运行时间为θ(n*logn)，树高为θ(logn)

二叉搜索树类的实现

#include <iostream>
using namespace std;

#pragma once
//设想是：当树为空时，root一定为nullptr 
struct node
{
    int element = 0;
    node* parent = nullptr;
    node* left = nullptr;
    node* right = nullptr;
};

class BinarySearchTree
{
public:
    BinarySearchTree() {}
    ~BinarySearchTree();
    int size();
    int maximum();
    int minimum();
    void print();
    void clear();
    void insert(const int&);
    void remove(const int&);
private:
    int cnt = 0;
    node* root = nullptr;

    node* minimum(node* x);
    void transplant(node* u, node* v);
    void clear(node*);
    void print(node*);
};

void BinarySearchTree::clear(node* x)
{
    if(x == nullptr) return;

    if(x->left != nullptr) clear(x->left);
    if(x->right != nullptr) clear(x->right);
    delete x;
    x = nullptr;
}

void BinarySearchTree::clear()
{
    cnt = 0;    
    clear(root);
}

BinarySearchTree::~BinarySearchTree()
{
    clear(root);
}

int BinarySearchTree::maximum()
{
    node* x = root;
    if(x == nullptr) return 0;
    while(x->right != nullptr)
        x = x->right;
    return x->element;
}

node* BinarySearchTree::minimum(node* x)
{
    if(x == nullptr) return 0;
    while(x->left != nullptr)
        x = x->left;
    return x;
}

int BinarySearchTree::minimum()
{
    return minimum(root)->element;
}

int BinarySearchTree::size()
{
    return cnt;
}

void BinarySearchTree::print(node* x)
{
    if(x == nullptr) return;
    if(x->left != nullptr) print(x->left);
    cout << x->element << ' ';
    if(x->right != nullptr) print(x->right);
}

void BinarySearchTree::print()
{
    print(root);
    cout<<'\n';
}

void BinarySearchTree::insert(const int& a)
{
    if(cnt == 0)
    {
        root = new node;
        root->element = a;
    }
    else
    {
        node* x = root;
        node* y = nullptr;
        while(x != nullptr)
        {
            y = x;
            if(a > x->element) x = x->right;
            else x = x->left;
        }

        node* t = new node;
        t->parent = y;
        t->element = a;
        if(a > y->element) y->right = t;
        else y->left = t;
    }
    ++cnt;
}

void BinarySearchTree::transplant(node* u, node* v)
{
    if(u->parent == nullptr) root = v;
    else if(u == u->parent->left) u->parent->left = v;
    else u->parent->right = v;

    if(v != nullptr) v->parent = u->parent;
}

void BinarySearchTree::remove(const int& a)
{
    node* x = root;
    while(x != nullptr && x->element != a)
    {
        if(a > x->element) x = x->right;
        else x = x->left;
    }
    if(x == nullptr) return;

    --cnt;
    if(x->left == nullptr)
        transplant(x, x->right);
    else if(x->right == nullptr)
        transplant(x, x->left);
    else
    {
        node* y = minimum(x->right);
        if(y->parent != x)
        {
            transplant(y, y->right);
            y->right = x->right;
            y->right->parent = y;
        }
        transplant(x, y);
        y->left = x->left;
        y->left->parent = y;
    }
}