目录

一、二叉搜索树概念

二、二叉搜索树的性能

三、二叉搜索树的代码实现（实现key和key/value）

插入

key版本

key/value版本

查询

key版本

key/value版本

删除

key版本

key/value版本

完整代码

key版本

key/value版本

四、二叉搜索树的应用

一、二叉搜索树概念

⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树: 1.若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值。2.若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值它的左右⼦树也分别为⼆叉搜索树。

二、二叉搜索树的性能

如果是最优情况下接近完全二叉树下，高度接近为，使得复杂度为O()。而当情况为最差情况下就是单支树，高度为n，复杂度就是O(n)。所以综合二叉树的增删查改的时间复杂度为O(n)。

它和二分查找查询差不多，二分查找也可以实现O()的查找效率，但是二分查找有一个缺陷就是内部支持下标随机访问的且有序，删除和插入需要挪动数据效率很低，所以二叉搜索树就是在插入和删除要优与二分查找。

三、二叉搜索树的代码实现（实现key和key/value）

插入

key版本

//插入(默认左边小于根，右边大于根) bool insert(const K& key) { //判断是否有根节点 if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = nullptr; while(cur) { //比根小 if (cur->_key > key) { parent = cur; cur = cur->_left; } //比根大 else if (cur->_key < key) { parent = cur; cur = cur->_right; } //相同 else { return false; } } //寻找到空位置 Node* node = new Node(key); //比父大 if (parent->_key < key) { parent->_right = node; } //比父小 else { parent->_left = node; } //插入成功 return true; }

key/value版本

//插入(默认左边小于根，右边大于根) bool insert(const pair<K,V>& kv) { //判断是否有根节点 if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { //比根小 if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } //比根大 else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } //相同 else { return false; } }

查询

key版本

//查询 Node* find(const K& key) { if (_root == nullptr) { return nullptr; } 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; }

key/value版本

//查询 Node* find(const K& key) { if (_root = nullptr) { return nullptr; } Node* cur = _root; while (cur) { if (cur->_kv.first > key) { cur = cur->_left; } else if (cur->_kv.first < key) { cur = cur->_right; } //找到了 else { return cur; } } //没找到 return nullptr; }

删除

key版本

总结代码实现删除可以看成3种类型

1.左孩子不存在（将右结点存在和不存在结合在一起）

//左孩子为空(结合右孩子为空和不为空的情况) if (cur->_left == nullptr) { //先判断是否为根节点 if (cur == _root) { _root = _root->_right; } else { //判断是parent左右孩子 if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; cur = nullptr; }

2.右孩子不存在（将左孩子存在和左孩子不存在结合在一起）

//右孩子为空 else if (cur->_right == nullptr) { //先判断该删除结点是否为根结点 if (cur == _root) { _root = _root->_left; } else { //判断是parent的左右孩子 if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; cur = nullptr; }

3.都存在

第三种：情况较为复杂，就是左右孩子都存在，这就需要寻找一个代替结点去继承该删除结点，我们可以选择左子树中的最右结点（也就是左子树中最大结点），或者我们选择右子树中的最左结点（也就是右子树中最小结点），这两个操作都可以实现，目的是为了满足根结点一定要小于右子树/大于左子树即可。

//左右孩子不为空 else { //这里我以左子树中最大结点作为删除结点的替换 Node* midrootparent = cur; Node* midroot = cur->_left; //寻找最右结点 while (midroot->_right) { midrootparent = midroot; midroot = midroot->_right; } //找到 //交换key swap(cur->_key, midroot->_key); if (midrootparent->_left == midroot) { midrootparent->_left = midroot->_left;//因为我们找的是cur左子树中的最右结点，可能最大值的左孩子存在 } else { midrootparent->_right = midroot->_left; } //删除midroot delete midroot; midroot = nullptr; } return true;

key/value版本

key/value版本和key的思路都一样

bool erase(const K& key) { Node* parent = nullptr; Node* cur = _root; if (cur == nullptr) { return false; } while (cur) { if (cur->_kv.first > key) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < key) { parent = cur; cur = cur->_right; } //找到了 else { //左孩子为空(结合右孩子为空和不为空的情况) if (cur->_left == nullptr) { //先判断是否为根节点 if (cur == _root) { _root = _root->_right; } else { //判断是parent左右孩子 if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; cur = nullptr; } //右孩子为空 else if (cur->_right == nullptr) { //先判断该删除结点是否为根结点 if (cur == _root) { _root = _root->_left; } else { //判断是parent的左右孩子 if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; cur = nullptr; } //左右孩子不为空 else { //这里我以左子树中最大结点作为删除结点的替换 Node* midrootparent = cur; Node* midroot = cur->_left; //寻找最右结点 while (midroot->_right) { midrootparent = midroot; midroot = midroot->_right; } //找到 //交换key swap(cur->_kv, midroot->_kv); if (midrootparent->_left == midroot) { midrootparent->_left = midroot->_left;//因为我们找的是cur左子树中的最右结点，可能最大值的左孩子存在 } else { midrootparent->_right = midroot->_left; } //删除midroot delete midroot; midroot = nullptr; } return true; } } return false; }

完整代码

key版本

namespace bear1 { template<class K> struct BSTNode { K _key; BSTNode<K>* _left; BSTNode<K>* _right; //初始化构造 BSTNode(K key) :_key(key) ,_left(nullptr) ,_right(nullptr) {} }; template<class K> class BSTree { typedef BSTNode<K> Node; public: //构造 BSTree(Node* root = nullptr) :_root(root) {} //插入(默认左边小于根，右边大于根) bool insert(const K& key) { //判断是否有根节点 if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = nullptr; while(cur) { //比根小 if (cur->_key > key) { parent = cur; cur = cur->_left; } //比根大 else if (cur->_key < key) { parent = cur; cur = cur->_right; } //相同 else { return false; } } //寻找到空位置 Node* node = new Node(key); //比父大 if (parent->_key < key) { parent->_right = node; } //比父小 else { parent->_left = node; } //插入成功 return true; } //查询 Node* find(const K& key) { if (_root == nullptr) { return nullptr; } 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; } //删除 bool erase(const K& key) { Node* parent = nullptr; Node* cur = _root; if (cur == nullptr) { return false; } while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } //找到了 else { //左孩子为空(结合右孩子为空和不为空的情况) if (cur->_left == nullptr) { //先判断是否为根节点 if (cur == _root) { _root = _root->_right; } else { //判断是parent左右孩子 if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; cur = nullptr; } //右孩子为空 else if (cur->_right == nullptr) { //先判断该删除结点是否为根结点 if (cur == _root) { _root = _root->_left; } else { //判断是parent的左右孩子 if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; cur = nullptr; } //左右孩子不为空 else { //这里我以左子树中最大结点作为删除结点的替换 Node* midrootparent = cur; Node* midroot = cur->_left; //寻找最右结点 while (midroot->_right) { midrootparent = midroot; midroot = midroot->_right; } //找到 //交换key swap(cur->_key, midroot->_key); if (midrootparent->_left == midroot) { midrootparent->_left = midroot->_left;//因为我们找的是cur左子树中的最右结点，可能最大值的左孩子存在 } else { midrootparent->_right = midroot->_left; } //删除midroot delete midroot; midroot = nullptr; } return true; } } return false; } //中序遍历 void _Order() { Order(_root); cout << endl; } private: void Order(Node* root) { //利用递归进行中序遍历 if (root == nullptr) { return; } //左根右 Order(root->_left); cout << root->_key << ' '; Order(root->_right); } Node* _root; }; }

key/value版本

namespace bear2 { template<class K,class V> struct BSTNode { pair<K, V> _kv; BSTNode<K,V>* _left; BSTNode<K,V>* _right; //初始化构造 BSTNode(pair<K,V> kv) :_kv(kv) , _left(nullptr) , _right(nullptr) { } }; template<class K,class V> class BSTree { typedef BSTNode<K,V> Node; public: //构造 BSTree(Node* root = nullptr) :_root(root) { } //插入(默认左边小于根，右边大于根) bool insert(const pair<K,V>& kv) { //判断是否有根节点 if (_root == nullptr) { _root = new Node(kv); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { //比根小 if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } //比根大 else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } //相同 else { return false; } } //寻找到空位置 Node* node = new Node(kv); //比父大 if (parent->_kv.first < kv.first) { parent->_right = node; } //比父小 else { parent->_left = node; } //插入成功 return true; } //查询 Node* find(const K& key) { if (_root = nullptr) { return nullptr; } Node* cur = _root; while (cur) { if (cur->_kv.first > key) { cur = cur->_left; } else if (cur->_kv.first < key) { cur = cur->_right; } //找到了 else { return cur; } } //没找到 return nullptr; } bool erase(const K& key) { Node* parent = nullptr; Node* cur = _root; if (cur == nullptr) { return false; } while (cur) { if (cur->_kv.first > key) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < key) { parent = cur; cur = cur->_right; } //找到了 else { //左孩子为空(结合右孩子为空和不为空的情况) if (cur->_left == nullptr) { //先判断是否为根节点 if (cur == _root) { _root = _root->_right; } else { //判断是parent左右孩子 if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; cur = nullptr; } //右孩子为空 else if (cur->_right == nullptr) { //先判断该删除结点是否为根结点 if (cur == _root) { _root = _root->_left; } else { //判断是parent的左右孩子 if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; cur = nullptr; } //左右孩子不为空 else { //这里我以左子树中最大结点作为删除结点的替换 Node* midrootparent = cur; Node* midroot = cur->_left; //寻找最右结点 while (midroot->_right) { midrootparent = midroot; midroot = midroot->_right; } //找到 //交换key swap(cur->_kv, midroot->_kv); if (midrootparent->_left == midroot) { midrootparent->_left = midroot->_left;//因为我们找的是cur左子树中的最右结点，可能最大值的左孩子存在 } else { midrootparent->_right = midroot->_left; } //删除midroot delete midroot; midroot = nullptr; } return true; } } return false; } //中序遍历 void _Order() { Order(_root); cout << endl; } private: void Order(Node* root) { //利用递归进行中序遍历 if (root == nullptr) { return; } //左根右 Order(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; Order(root->_right); } Node* _root; }; }

四、二叉搜索树的应用

二叉搜索树的应用场景在生活中很场景，例如：在搜索单词是否正确时候，我们会用到二叉搜索树来查询是否有这个单词从而来判断单词的正确性；还有就是小区门口用于防外来车俩占用业主车库的识别杠，这个时候用二叉搜索树来查询就会很方便，查询到是业主车牌就会开杠入进。而还有一个针对于key/value的应用场景，可以是中英互译，知道key（中文/英文）就能得到value(英文/中文)；还有就是统计一篇文章中单词出现次数，用二叉搜索树就很方便，类似哈希表，后面我们会将和哈希表的联系。