一、二叉搜索树的基本知识
1、什么是二叉搜索树
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
二叉搜索树的这种特性使得在其中进行搜索、插入和删除操作具有高效性能。通过对节点值的比较，我们可以迅速定位目标节点或确定应插入的位置。
上图中就是二叉搜索树的构成，他满足所有左叶子节点比跟小，所以的右叶子节点比根要大。
为了更好的理解二叉搜索树，下面将带来大家底层实现二叉搜索树的查找，插入，删除。
2、二叉搜索树的性能分析
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
- 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：O(log n)
- 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为O(n)
二、底层模拟实现
1、构建二叉搜索树
template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) :_key(key) , _left(nullptr) , _right(nullptr) {} }; template<class K> class BSTree { typedef BSTreeNode<K> Node; public://函数 private: Node* _root = nullptr; }
这里我们定义好节点，和树的主体就好了，下面我的二叉搜索树的功能函数多在类中实现。
2、二叉搜索树的查找
现在给我们一颗搜索二叉树，那我们是如何让他查找到我们想要的元素
查找原则：
- 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
- 最多查找高度次，走到到空，还没找到，这个值不存在。
顺着这个思路我们很容易思路就可以写出查找：
普通写法：
//查找 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; } else { return true; } } return false; }
递归写法：
bool _FindR(Node* root, const K& key) { 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; } }
这二种写法，在这里好像看不出来特别大的差别。
3、二叉搜索树的插入
这里我们思考一下，如果我们要在1处插入 0
我们要找到插入的位置。然后在new一个节点进连接就可以
插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
普通写法：
bool Inert(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; } else { return false; } } //创建节点 cur = new Node(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; } if (root->_key < key) { return _InsertR(root->_right, key); } else if (root->_key > key) { return _InsertR(root->_left, key); } else { return false; } }
递归写法最让我们感到绝妙的是我们在这里传root用的是引用，因为用递归时(如果没有用root的引用)并没有传父亲节点，这也就在连接的时候会遇到到问题，但是我们这里传了root的引用就可以解决这个问题
这里当我们要插入9，到我们递归到root == 10时候,在进行递归时，会往root->left递归，指向空,就可以插入，而&root是root->left指针的别名，就可以完美的连接起来。 
4、二叉搜索树的删除节点
这里是本次模拟的难点所在，大家可以细细品味：
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情 况：
- a. 要删除的结点无孩子结点
- b. 要删除的结点只有左孩子结点
- c. 要删除的结点只有右孩子结点
- d. 要删除的结点有左、右孩子结点
其实我们可以总结为3种删除情况：
- 情况1：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
- 情况2：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
- 情况3：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点 中，再来处理该结点的删除问题--替换法删除
普通写法：
这里我们重点注意第三种情况，这里我们是找左树的最大或者说是右树的最小和我们要删除的数，进行替换在删除就可以了。
//删除 bool Erase(const K& key) { 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; } else { //1、左为空 //2、右为空 // 1.2都可以直接删除 //在直接删除前，我们还要做好cur的左右节点的链接工作，并处理特殊情况(cur==_root) if (cur->_left == nullptr) { //处理特殊情况 if (cur == _root) { _root = cur->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } else if (cur->_right == nullptr) { //处理特殊情况 if (cur == _root) { _root = cur->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; }
递归写法：
bool _EraseR(Node*& root, const K& key) { if (root == nullptr) { return false; } //先找到要删除的位置 if (root->_key < key) { return _EraseR(root->_right, key); } else if (root->_key > key) { return _EraseR(root->_left, key); } else { Node* del = root; if (root->_right == nullptr) { root = root->_left; } else if (root->_left == nullptr) { root = root->_right; } else { Node* minRight = root->_right; while (minRight->_left) { minRight = minRight->_left; } swap(root->_key, minRight->_key); //转换为在子树中删除节点 return _EraseR(root->_right, key); } delete del; return true; } }
5、完整代码实现
namespace K { template<class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) :_key(key) , _left(nullptr) , _right(nullptr) {} }; template<class K> class BSTree { typedef BSTreeNode<K> Node; public: //默认构造 BSTree() :_root(nullptr) {} //构造函数 BSTree(const BSTree<K>& t) { _root = Copy(t._root); } //赋值重载 BSTree<K>& operator=(BSTree<K> t) { swap(_root, t._root); return *this; } //析构函数 ~BSTree() { Destroy(_root); _root = nullptr; } //搜索二插树插入 bool Inert(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; } else { return false; } } //创建节点 cur = new Node(key); //连接树 if (parent->_key > key) { parent->_left = cur; } else { parent->_right = cur; } return true; } //查找 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; } else { return true; } } return false; } //删除 bool Erase(const K& key) { 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; } else { //1、左为空 //2、右为空 // 1.2都可以直接删除 //在直接删除前，我们还要做好cur的左右节点的链接工作，并处理特殊情况(cur==_root) if (cur->_left == nullptr) { //处理特殊情况 if (cur == _root) { _root = cur->_right; } else { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } else if (cur->_right == nullptr) { //处理特殊情况 if (cur == _root) { _root = cur->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } //3、左右都不为空 //找cur右子数的最小节点 else { Node* parent = cur; Node* minRight = cur->_right; while (minRight->_left) { parent = minRight; minRight = minRight->_left; } cur->_key = minRight->_key; //连接 if (parent->_left == minRight) { parent->_left = minRight->_right; } else { parent->_right = minRight->_right; } //删除节点 delete minRight; } return true; } } return false; } void InOrder() { _InOrder(_root); cout << endl; } bool InsertR(const K& key) { return _InsertR(_root, key); } bool FindR(const K& key) { return _FindR(_root, key); } bool EraseR(const K& key) { return _EraseR(_root, key); } //递归写法完成增删查改 private: void Destroy(Node* root) { if (root == nullptr) { return; } Destroy(root->_left); Destroy(root->_right); delete root; } //拷贝节点 Node* Copy(Node* root) { if (root == nullptr) { return nullptr; } Node* newRoot = new Node(root->_key); newRoot->_left = Copy(root->_left); newRoot->_right = Copy(root->_right); return newRoot; } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } bool _InsertR(Node*& root, const K& key) { if (root == nullptr) { root = new Node(key); return true; } if (root->_key < key) { return _InsertR(root->_right, key); } else if (root->_key > key) { return _InsertR(root->_left, key); } else { return false; } } bool _FindR(Node* root, const K& key) { 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; } } bool _EraseR(Node*& root, const K& key) { if (root == nullptr) { return false; } //先找到要删除的位置 if (root->_key < key) { return _EraseR(root->_right, key); } else if (root->_key > key) { return _EraseR(root->_left, key); } else { Node* del = root; if (root->_right == nullptr) { root = root->_left; } else if (root->_left == nullptr) { root = root->_right; } else { Node* minRight = root->_right; while (minRight->_left) { minRight = minRight->_left; } swap(root->_key, minRight->_key); //转换为在子树中删除节点 return _EraseR(root->_right, key); } delete del; return true; } } private: Node* _root = nullptr; }; }
三、二叉搜索树的应用
1、K模型
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到 的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
这里就是我们完整实现的二叉树，这里我们用二叉搜索树的查找功能，如果该单词存在树中就会返回true，否则返回false。
2、KV模型
KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方 式在现实生活中非常常见：
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文就构成一种键值对；
- 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出 现次数就是就构成一种键值对。
这里我们上面代码进行简单改造就可以得到我们的KV模型：
namespace KV { template<class K, class V> struct BSTreeNode { BSTreeNode<K, V>* _left; BSTreeNode<K, V>* _right; K _key; V _value; BSTreeNode(const K& key, const V& value) :_key(key) , _value(value) , _left(nullptr) , _right(nullptr) {} }; //BSTree<string, vector<string>> bookInfo; template<class K, class V> class BSTree { typedef BSTreeNode<K, V> Node; public: bool Insert(const K& key, const V& value) { if (_root == nullptr) { _root = new Node(key, value); 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, value); if (parent->_key < key) { parent->_right = cur; } else { parent->_left = cur; } return true; } Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return cur; } } return nullptr; } void Inorder() { _Inorder(_root); } void _Inorder(Node* root) { if (root == nullptr) return; _Inorder(root->_left); cout << root->_key << ":" << root->_value << endl; _Inorder(root->_right); } private: Node* _root = nullptr; }; } void TestBSTree2() { // Key/Value的搜索模型,通过Key查找或修改Valu KV::BSTree<string, string> dict; dict.Insert("sort", "排序"); dict.Insert("string", "字符串"); dict.Insert("left", "左边"); dict.Insert("right", "右边"); string str; while (cin >> str) { KV::BSTreeNode<string, string>* ret = dict.Find(str); if (ret) { cout << ret->_value << endl; } else { cout << "无此单词" << endl; } } }
这里我们对改造的二叉搜索树，就可以进行通过英文快速找到英文。
