二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3. 它的左右子树也分别为二叉搜索树

二叉搜索树操作

结点类的实现

为了方便二叉搜索树的实现，我们需要先实现一个节点类，它包含一个左指针，一个右指针，一个结点值。

template<class K>
struct BSTreeNode
{BSTreeNode* _left;BSTreeNode* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};

中序遍历实现

为了方便我们随时可以检测我们我们实现的二叉搜索树是否有问题，我们需要实现一个中序遍历来将各结点值打印出来，以便保证二叉搜索树的正确性。

template<class K>
class BSTree
{typedef BSTreeNode Node;
public:void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
private:Node* _root;
};

二叉搜索树的插入

插入的具体过程如下：

1. 树为空，则直接新增节点，赋值给root指针
2. 树不空，按二叉搜索树性质查找插入位置，插入新结点

树不为空，插入结点分为以下操作：

• 待插入结点的值小于根节点的值，向左子树中插入
• 待插入结点的值大于根节点的值，向右子树中插入
• 待插入结点的值等于根节点的值，返回false

依次进行插入，直到找到空位置进行插入后者返回false。

非递归实现

我们需要记录根节点的位置，便于最后插入时将待插入节点与它的父节点连接起来，所以我们定义一个parent结点记录位置，在定义一个cur来遍历二叉搜索树：

代码实现：

bool Insert(const K& key)
{//如果此时插入的为根结点，直接创建新结点if (_root == nullptr){_root = new Node(key);return true;}//定义一个父结点记录位置Node* parent = nullptr;Node* cur = _root;while (cur){//插入值小于结点值，去左子树中找if (cur->_key > key){parent = cur;cur = cur->_left;}//插入值大于结点值，去右子树中找else if(cur->_key < key){parent = cur;cur = cur->_right;}//插入值等于结点值，返回falseelse{return false;}}//创建key所在结点cur = new Node(key);//此时如果key < parent->_key,就在左边插入if (parent->_key > key){parent->_left = cur;}//反之，右边插入else{parent->_right = cur;}return true;
}

递归实现

插入的递归实现其实很简单，依然是小于根节点就去左边插入，大于根节点就去右边插入，但是需要注意的是结点的传递我们需要以引用的方式，因为最后我们是需要将插入结点与前面结点链接起来的：

bool _InSertR(Node*& root, const K& key)
{//为空树，创建一个根结点if (root == nullptr){root = new Node(key);return true;}//key小于根结点的值，左子树中寻找if (root->_key > key){return _InSertR(root->_left, key);}//key大于根结点的值，右子树中寻找else if(root->_key < key){return _InSertR(root->_right, key);}//相等，返回falseelse{return false;}
}
//便于调用子函数进行插入
void InSertR(const K& key)
{_InSertR(_root, key);
}

二叉搜索树的查找

非递归实现

二叉搜索树非递归实现跟插入差不多，就是分别在左右子树中找，找到了就返回true，找不到就返回false：

//查找
bool Find(const K& key)
{Node* cur = _root;while (cur){//查找值小于结点值，去左子树中找if (cur->_key > key){cur = cur->_left;}//查找值大于结点值，去右子树中找else if (cur->_key < key){cur = cur->_right;}//查找值等于结点值，返回trueelse{return true;}}return false;//没有找到，返回false
}

递归实现

bool _FindR(Node*& root, const K& key)
{//为空，就找不到，返回falseif (root == nullptr){return false;}//key小于根结点的值，左子树中寻找if (root->_key > key){return _FindR(root->_left, key);}//key大于根结点的值，右子树中寻找else if (root->_key < key){return _FindR(root->_right, key);}//相等，返回trueelse{return true;}

二叉搜索树的删除

删除的具体过程如下：

1. 树为空，则不需要删除
2. 树不空，按二叉搜索树性质查找删除位置

树不为空，存在以下三种情况：

• 被删除结点左右都为空，此时只需要delete cur，然后让parent结点指向nullptr即可；
  

• 被删除的结点一边为空，此时就需要就需要判断被删除结点是parent结点的左孩子还是右孩子，
  然后在改变parent结点的指向；
  
  上面两种情况如果我们此时删除的是根结点，我们只需要改变根节点的位置就可以了：
  

• 被删除的结点两边都不为空，此时就需要我们考虑用替换法来删除，我们可以考虑用被删除结点左子树的最大值或者是右子树的最小值来替换掉被删除结点，因为这样删除以后并不会破坏二叉搜索树的性质，我们以右子树的最小值来替换掉被删除结点为例，我们需要定义一个min结点来记录右子树的最小值，定义一个minParent记录min结点父节点位置。
  
  

非递归实现

//删除
bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){//key小于根结点的值，左子树中寻找if (cur->_key > key){parent = cur;cur = cur->_left;}//key大于根结点的值，右子树中寻找else if (cur->_key < key){parent = cur;cur = cur->_right;}//相等，进行删除else{//被删除结点左孩子为空if (cur->_left == nullptr){//被删除结点为根节点if (cur == _root){//改变根节点指向位置_root = cur->_left;}//被删除结点不为根节点else{//被删除结点为左孩子if (cur == parent->_left){//父结点左指针指向被删除孩子右子树parent->_left = cur->_right;}//被删除结点为右孩子else{//父结点右指针指向被删除孩子右子树parent->_right = cur->_right;}}//删除该结点delete cur;cur = nullptr;}//被删除结点右孩子为空else if (cur->_right == nullptr){//被删除结点为根节点if (cur == _root){//改变根节点指向位置_root = cur->_left;}//被删除结点不为根节点else{//被删除结点为左孩子if (cur == parent->_left){//父结点左指针指向被删除孩子左子树parent->_left = cur->_left;}//被删除结点为右孩子else{//父结点右指针指向被删除孩子左子树parent->_right = cur->_left;}}//删除该结点delete cur;cur = nullptr;}else{//记录待删除结点右子树当中值最小结点的父结点Node* minParent = cur;//记录待删除结点右子树当中值最小的结点Node* min = cur->_right;//寻找待删除结点右子树当中值最小的结点while (min->_left){minParent = min;min = min->_left;}//交换待删除结点与min结点的值swap(cur->_key, min->_key);//此时minParent的左指针指向minif (minParent->_left == min){//让minParent的左指针指向min的右子树minParent->_left = min->_right;}//此时minParent的右指针指向minelse{//让minParent的右指针指向min的右子树minParent->_right = min->_right;}//删除掉min结点delete min;min = nullptr;}return true;}}return false;
}

递归实现

• 若树为空树，则结点删除失败，返回false。

• 若所给key值小于树根结点的值，则问题变为删除左子树当中值为key的结点。

• 若所给key值大于树根结点的值，则问题变为删除右子树当中值为key的结点。

• 若所给key值等于树根结点的值，则根据根结点左右子树的存在情况不同，进行不同的处理。

bool _EraseR(Node*& root, const K& key)
{//空树，找不到，返回falseif (root == nullptr){return false;}//key小于根结点的值，在左子树中去找if (root->_key > key){return _EraseR(root->_left, key);}//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* min = root->_right;//寻找待删除结点右子树当中值最小的结点while (min->_left){min = min->_left;}//交换待删除结点与min结点的值swap(root->_key, min->_key);//递归进行删除return _EraseR(root->_right, key);}//释放掉待删除结点delete del;return true;}
}

构造函数

构造一个空树即可：

//构造函数
BSTree():_root(nullptr)
{}

拷贝构造函数

我们需要注意点是二叉搜索树的拷贝属于深拷贝，我们需要创建一颗和被拷贝二叉搜索树相同的树：

//拷贝函数
Node* _Copy(Node* root)
{//为空树，直接返回空if (root == nullptr){return nullptr;}//拷贝根结点Node* CopyRoot = new Node(root->_key);//向左递归拷贝左子树CopyRoot->_left = _Copy(root->_left);//向右递归拷贝右子树CopyRoot->_right = _Copy(root->_right);//返回拷贝的树return CopyRoot;
}
//拷贝构造函数
BSTree(const BSTree<K>& t)
{_root = _Copy(t._root);
}

析构函数

二叉搜索树析构函数就是将每个结点都释放掉，但需要注意的是我们这儿要后序遍历进行释放：

void _Destory(Node*& root)
{//为空树，返回上一级if (root == nullptr){return;}//向左递归释放左子树_Destory(root->_left);//向右递归释放右子树_Destory(root->_right);//释放根节点delete root;//root置为nullptrroot = nullptr;
}
//析构函数
~BSTree()
{_Destory(_root);
}

赋值运算符重载

我们使用现代写法来进行赋值运算符重载：

	//赋值运算符重载BSTree<K>& operator=(const BSTree<K> t){swap(_root, t._root);return *this;}

二叉搜索树的应用

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

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

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

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。

• 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
• 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

对于有n个结点的二叉搜索树：

最优的情况下，二叉搜索树为完全二叉树，其平均比较次数为：log N；
最差的情况下，二叉搜索树退化为单支树，其平均比较次数为：N / 2；