@TOC

零、前言

我们都知道二叉树只有附加上一些特性才具有实用的价值，而本章主要讲解二叉树进阶的内容-二叉搜索树

一、二叉搜索树概念

• 概念：

二叉搜索树（Binary Search Tree）又称二叉排序树，也称作二叉查找树它或者是一棵空树，或者是具有以下性质的二叉树

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

3. 它的左右子树也分别为二叉搜索树

• 示图：

• 性能：

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为O(log n)（理想状态下和完全二叉树形似）

注：对于极端状态下，查找、插入为O(n)（形似单链表）

• 示图：

二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如map，set等

二、二叉搜索树的详解及模拟

1、二叉搜索树的结构

• 二叉搜索树结点结构：

template<class K>
struct BSTreeNode
{
    //记录左右子树
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	//存值
	K _key;
	//构造函数
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
    {}
};

• 二叉搜索树基本框架：

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	bool Insert(const K& key);
	Node* Find(const K& key);
	bool Erase(const K& key);
	void InOrder();
private:
    void _InOrder(Node* root);
	Node* _root = nullptr;
};

注：由于二叉搜索树的特性，所以二叉搜索树不能修改key

2、二叉树搜索树的构造和析构

• 实现代码：

BSTree()
    :_root(nullptr)
    {}

BSTree(const BSTree<K>& t)
{
    _root = _Copy(t._root);
}

BSTree<K>& operator=(BSTree<K> t)
{
    std::swap(_root, t._root);
    return *this;
}

~BSTree()
{
    _Destory(_root);
}

Node* _Copy(Node* root)
{
    //空结点构建
    if (root == nullptr)
        return nullptr;

    //构建当前结点
    Node* newnode = new Node(root->_key);

    //递归构建左右子树
    newnode->_left = _Copy(root->_left);
    newnode->_right = _Copy(root->_right);

    return newnode;
}

void _Destory(Node*& root)
{
    if (root == nullptr)
        return;

    //后序遍历释放结点
    _Destory(root->_left);
    _Destory(root->_right);

    //释放置空结点
    delete root;
    root = nullptr;
}

3、二叉搜索树的查找

• 具体操作过程：

1. 若走到空节点，则搜索失败，返回空指针
2. 若key大于当前结点的数据域之值，则搜索右子树
3. 若key小于当前结点的数据域之值，则搜索左子树
4. 若key等于当前结点的数据域之值，则查找成功，返回当前结点地址

• 示图：查找32

• 迭代实现：

Node* Find(const K& key)
{
    Node* cur = _root;
    while (cur)
    {
        if (cur->_key > key)
        {
            cur = cur->_left;
        }
        else if (cur->_key < key)
        {
            cur = cur->_right;
        }
        else
        {
            return cur;
        }
    }
    return nullptr;
}

• 递归实现：

Node* FindR(const K& key)
{
    return _FindR(_root,key);
}
Node* _FindR(Node* root, const K& key)
{
    if (root == nullptr)
        return nullptr;

    if (root->_key == key)
        return root;
    else if (root->_key > key)
        return _FindR(root->_left, key);
    else
        return _FindR(root->_right, key);
}

• 注意：

1. 实现子函数便于递归，并且保护私有成员
2. 子函数一般建议设置为私有，避免接口暴露

4、二叉搜索树的插入

• 具体操作过程：

1. 若key大于当前结点的数据域之值，则插入右子树
2. 若key小于当前结点的数据域之值，则插入左子树
3. 若key等于当前结点的数据域之值，则插入失败，返回false
4. 若走到空结点直接插入，插入成功，返回true

• 示图：插入56

• 迭代实现：

bool Insert(const K& key)
{
    if (_root == nullptr)
    {
        _root = new Node(key);
        return true;
    }

    Node* cur = _root;
    Node* prev = nullptr;
    while (cur)
    {
        if (cur->_key > key)
        {
            prev = cur;
            cur = cur->_left;
        }
        else if (cur->_key < key)
        {
            prev = cur;
            cur = cur->_right;
        }
        else
        {
            return false;
        }
    }

    cur = new Node(key);
    //依靠键值比较来决定连接位置（依靠节点地址来判断会误判）
    if (prev->_key > key)
    {
        prev->_left = cur;
    }
    else
    {
        prev->_right = cur;
    }
    return true;
}

• 递归实现：

bool InsertR(const K& key)
{
    return _InsertR(_root, key);
}
bool _InsertR(Node*& root, const K& key)
{
    if (root == nullptr)
    {
        root = new Node(key);
        return true;
    }

    if (root->_key > key)
    {
        return _InsertR(root->_left, key);
    }
    else if (root->_key < key)
    {
        return _InsertR(root->_right, key);
    }
    else
    {
        return false;
    }
}

5、二叉搜索树的删除

• 具体操作过程：

1. 若查找元素不存在在二叉搜索树中，则返回false

2. 若查找元素存在，则可能分为下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

注：实际情况a可以与情况b或者c合并起来

• 最终的删除过程如下：

1. 情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点

• 示图：删除91

2. 情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点

• 示图：删除29

3. 情况d：替换删除，在左子树中找到key最大的（或则在右子树中找到key最小的），与当前结点交换key，然后删除左子树中key最大结点（或则在右子树key最小的结点）

• 示图：删除20

• 迭代实现：

bool Erase(const K& key)
{
    Node* cur = _root;
    Node* prev = nullptr;//记录父结点
    while (cur)
    {
        if (cur->_key > key)
        {
            prev = cur;
            cur = cur->_left;
        }
        else if (cur->_key < key)
        {
            prev = cur;
            cur = cur->_right;
        }
        else//找到了
        {
            //分情况讨论
            if (cur->_left == nullptr)
            {
                //根节点特殊处理
                if (cur == _root)
                {
                    _root = cur->_right;
                }
                else
                {
                    //判断是左还是右
                    if (prev->_left == cur)
                    {
                        prev->_left = cur->_right;
                    }
                    else
                    {
                        prev->_right = cur->_right;
                    }
                }
                delete cur;
            }
            else if (cur->_right == nullptr)
            {
                if (cur == _root)
                {
                    _root = cur->_left;
                }
                else
                {
                    if (prev->_left == cur)
                    {
                        prev->_left = cur->_left;
                    }
                    else
                    {
                        prev->_right = cur->_left;
                    }
                }
                delete cur;
            }
            else
            {
                //找到左子树中最大的结点
                Node* maxLeft = cur->_left;
                while (maxLeft->_right)
                {
                    maxLeft = maxLeft->_right;
                }

                K max = maxLeft->_key;
                //先删再替换
                Erase(max);
                cur->_key = max;
            }
            return true;
        }
    }
    return false;
}

• 递归实现：

bool EraseR(const K& key)
{
    return _EraseR(_root, key);
}
bool _EraseR(Node*& root, const K& key)
{
    if (root == nullptr)
        return false;

    if (root->_key > key)
        return _EraseR(root->_left, key);
    else if (root->_key < key)
        return _EraseR(root->_right, key);
    else
    {
        //记录当前结点
        Node* del = root;
        if (root->_left == nullptr)
        {
            root = root->_right;
        }
        else if (root->_right == nullptr)
        {
            root = root->_left;
        }
        else
        {
            //找到右边最小结点
            Node* minR = root->_right;
            while (minR->_left)
            {
                minR = minR->_left;
            }
            //替换值
            root->_key = minR->_key;

            _EraseR(root->_right, root->_key);
            return true;
        }
        delete del;
        return true;
    }
}

三、二叉搜索树的应用

1. K模型：

• 概念：

K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值

• 示例：给一个单词word，判断该单词是否拼写正确

以单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中,检索该单词是否存在，存在则拼写正确，不存在则拼写错误

2. KV模型：

• 概念：

每一个关键码key，都有与之对应的值Value，即**<Key, Value>**的键值

• 示例：

1. 英汉词典：通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对

2. 统计单词次数：统计后，给定单词就可快速找到其出现的次数，单词与其出现次数就是**<word, count>**就构成一种键值对

• 实现一个简单的英汉词典dict：

<单词，中文含义>为键值对构造二叉搜索树,二叉搜索树需要比较，键值对比较时只比较Key查询英文单词时，只需给出英文单词，就可快速找到与其对应的key

• KV模型：

template<class K, class V>
struct BSTNode
{
	BSTNode(const K& key = K(), const V& value = V())
		: _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value)
	{}
	BSTNode<T>* _pLeft;
	BSTNode<T>* _pRight;
	K _key;
	V _value
};
template<class K, class V>
class BSTree
{
	typedef BSTNode<K, V> Node;
	typedef Node* PNode;
public:
	BSTree() : _pRoot(nullptr)
	{}
	~BSTree();
	PNode Find(const K& key);
	bool Insert(const K& key, const V& value)
	{
		// ...
		PNode pCur = _pRoot;
		PNode pParent = nullptr;
		while (pCur)
		{
			pParent = pCur;
			if (key < pCur->_key)
				pCur = pCur->_pLeft;
			else if (key > pCur->_key)
				pCur = pCur->_pRight; // 元素已经在树中存在
			else
				return false;
		}
		// ...
		return true;
	}
	bool Erase(const K& key)
	{
		// ...
		return true;
	}
private:
	PNode _pRoot;
};