二叉搜索树的实现

本文旨在讲解如何编写一颗二叉搜索树，包括基本的增删查改的操作。

一、二叉搜索树的概念

编辑二、二叉搜索树的编写

2.1节点的编写

2.2节点的插入

2.3节点的查找

2.4节点的删除

三、二叉搜索树的应用

四、二叉搜索树的性能分析

五、完整代码

一、二叉搜索树的概念

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

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

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

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

二、二叉搜索树的编写

2.1节点的编写

作为一颗树他的节点应该包括储存的内容和找到其他节点的方式，而因为它是一棵二叉树，所以这里我采用左右孩子法去定义它的孩子。

template <class K, class V>
struct BSTreeNode
{BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _val;BSTreeNode(const K& key,const V& val)//可能存自定义类型，所以用引用节省空间提升效率:_left(nullptr),_right(nullptr),_key(key),_val(val){}
};

这里我预计储存一个k_val两个类型的数据，但是其实写多少个类型的数据都可以（>=1）。但是要明确的是，只有一个数据参与了对应节点在二叉树中位置相关的代码。

2.2节点的插入

当节点的插入实现后，我们就可以将这颗树建立起来。根据二叉树的特性，比当前节点小的在左边，大的在右边。

插入的具体过程如下：

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

代码如下

bool Insert(const K& key, const V& val){if (_root == nullptr){_root = new Node(key,val);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}} cur = new Node(key,val);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}

2.3节点的查找

这里我希望当节点找到后返回它对应的地址，根据二叉搜索树代码如下：

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

当然我们也可以使用递归的方式来判断一棵树中是否有某个节点

    bool FindR(const K& key){return _FindR(_root, key);}bool _FindR(Node* root,const K& key)//带R表示是递归实现{if (root == nullptr){return false;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key>key){return _FindR(root->_left, key);}else{return true;}}

2.4节点的删除

节点的删除是二叉搜索树最困难的部分。首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

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

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

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

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

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下

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

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

情况 d ：在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ，用它的值填补到被删除节点

中，再来处理该结点的删除问题 -- 替换法删除

其中替换法删除就是用要删除节点的左边最大的节点或着右边最小的节点的值来替换当前节点，然后情况d就转换成了情况b或c。

此外，我们还应该考虑的时如果要删除的节点时根节点的情况。

    bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){//先找到这个要删除的元素的位置if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else // 找到了{if (cur->_left == nullptr){if (cur == _root)_root = _root->_right;else{if (parent->_right == cur)parent->_right = cur->_right;else parent->_left = cur->_right;}}if (cur->_right == nullptr){if (cur == _root)_root = _root->_left;else{if (parent->_right == cur)parent->_right = cur->_left;else parent->_left = cur->_left;}}else{//找替换节点，左面最大或者右面最小parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}std::swap(cur->_key, leftMax->_key);std::swap(cur->_val, leftMax->_val);if (parent->_left == leftMax)parent->_left = leftMax->_left;else parent->_right= leftMax->_left;}delete cur;return true;}}return false;}

最终我们就将整颗二叉搜索树的基本功能实现了

三、二叉搜索树的应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

1>以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树

2>在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英

文单词与其对应的中文<word, chinese>就构成一种键值对；

再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出

现次数就是<word, count>就构成一种键值对

四、二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树： 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$log_2 N 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N/2问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了。

五、完整代码

#pragma once
#include<iostream>
using namespace std;template <class K, class V>
struct BSTreeNode
{BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _val;BSTreeNode(const K& key,const V& val)//可能存自定义类型，所以用引用节省空间提升效率:_left(nullptr),_right(nullptr),_key(key),_val(val){}
};
template<class K,class V>
class BSTree
{typedef BSTreeNode<K,V> Node;
public:BSTree():_root(nullptr){}bool Insert(const K& key, const V& val){if (_root == nullptr){_root = new Node(key,val);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}} cur = new Node(key,val);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if(key>cur->_key){cur = cur->_right;}else{return cur;}}return nullptr;}bool FindR(const K& key){return _FindR(_root, key);}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){//先找到这个要删除的元素的位置if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else // 找到了{if (cur->_left == nullptr){if (cur == _root)_root = _root->_right;else{if (parent->_right == cur)parent->_right = cur->_right;else parent->_left = cur->_right;}}if (cur->_right == nullptr){if (cur == _root)_root = _root->_left;else{if (parent->_right == cur)parent->_right = cur->_left;else parent->_left = cur->_left;}}else{//找替换节点，左面最大或者右面最小parent = cur;Node* leftMax = cur->_left;while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}std::swap(cur->_key, leftMax->_key);std::swap(cur->_val, leftMax->_val);if (parent->_left == leftMax)parent->_left = leftMax->_left;else parent->_right= leftMax->_left;}delete cur;return true;}}return false;}void InOrder()//中序遍历{_InOrder(_root);cout << endl;}
private:bool _FindR(Node* root,const K& key)//带R表示是递归实现{if (root == nullptr){return false;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key>key){return _FindR(root->_left, key);}else{return true;}}void _InOrder(Node* root){if (root == NULL){return;}_InOrder(root->_left);cout << root->_key << " :"<<root->_val;_InOrder(root->_right);}
private:Node* _root;
};