[数据结构]二叉搜索树详解

目录

一、二叉搜索树的概念

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

三、二叉搜索树的中序遍历用于排序+去重

四、二叉搜索树的查找

1、查找的非递归写法

2、查找的递归写法

五、二叉搜索树的插入

1、插入的非递归写法

2、插入的递归写法

六、二叉搜索树的删除

1、删除的非递归写法

2、删除的递归写法

七、二叉搜索树的使用场景

1、key搜索模型（节点存key）

key搜索模型整体代码

2、key/value搜索模型（节点既存key又存value）

key/value搜索模型整体代码

---

一、二叉搜索树的概念

        二叉搜索树又称二叉排序树。

        空树是二叉搜索树，如果一棵树不是空树，需要满足如下情况便可称其为二叉搜索树：

        1、左子树上每一个键值均小于根节点；

        2、右子树上每一个键值均大于根节点；

        3、左右子树均为二叉搜索树。

---

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

它可以用来排序 – 由于二叉搜索树的左子树都小于根，右子树都大于根，所以如果对二叉搜索树进行中序遍历得到的数据天然就是有序的。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

• 最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其平均比较次数为 O(logN)。
• 最差情况下，二叉搜索树退化为单支树( 或者类似单支)，其平均比较次数为 O(N)。
• 所以，二叉搜索树进行查找的时间复杂度为 O(N)。

可能有的同学会想，既然二叉搜索树查找的时间复杂度为 O(N)，那我们为什么不直接用二分查找呢？毕竟二分查找的时间复杂度可是 O(logN)，这是因为二分查找存在许多限制：

• 二分查找要求数据必须有序；
• 二分查找使用顺序表进行数据存储，插入、删除数据效率低，而在实际开发中，我们是要经常插入删除数据的；

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插 入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了。

---

三、二叉搜索树的中序遍历用于排序+去重

通过上面那张图不难发现，用二叉搜索树走个中序，就是升序+去重排序，这也是二叉搜索树又被称为二叉排序树的原因。

        使用InOrder调用_InOrder的原因是类外面传参传不了私有的_root，所以采用多套一层的方法。

//中序遍历
void _InOrder(Node* _root)
{if (_root == nullptr){return;}_InOrder(_root->_left);std::cout << _root->_key << " ";_InOrder(_root->_right);
}
void InOrder()//因为外部取不到_root,所以这里套了一层调用函数
{_InOrder(_root);std::cout << std::endl;
}

---

四、二叉搜索树的查找

1、查找的非递归写法

bool 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 true;}return false;
}

2、查找的递归写法

Node* _FindR(Node* root,const K& key)
{if (root == nullptr)return nullptr;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}elsereturn root;
}
bool FindR(const K& key)
{return _FindR(_root, key) == nullptr ? false : true;
}

---

五、二叉搜索树的插入

        二叉搜索树的插入需要考虑插入后，需要维持二叉搜索树的形态。

1、插入的非递归写法

bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);//BSTreeNode对象中存放key值，构造一个二叉搜索树节点 }else{Node* parent = nullptr;Node* cur = _root;//cur一直走，走到要插入的位置while (cur){parent = cur;if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else//说明数字重复，插入失败return false;}cur = new Node(key);//判断插入节点放在parent节点的左子树还是右子树if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}}return true;
}

        1、如果根是空，插入的节点就是新的根；

        2、如果根不为空，就先根据二叉搜索树的性质找到该节点要插入的位置，如果路上遇到相同的数，插入失败；

        3、再判断一下，是要插入父亲的左边还是右边即可。

2、插入的递归写法

bool _InsertR(Node*& root, const K& key)//形参是root的引用
{if (root == nullptr){root = new Node(key);//因为root是父节点左/右孩子的别名，直接修改别名，链接关系存在，不用考虑父子节点连接关系return true;}if (root->_key < key)return _InsertR(root->_right, key);//看到这个root->_right没，它是下一层root的别名else if (root->_key > key)return _InsertR(root->_left, key);//看到这个root->_left没，它是下一层root的别名else//说明相等，插入失败return false;
}
bool InsertR(const K& key)
{return _InsertR(_root, key);
}

因为函数参数是父节点的左孩子/右孩子的别名，所以被修后不需要考虑链接关系。

六、二叉搜索树的删除

        二叉搜索树的节点进行删除后，同样需要维持二叉搜索树的形态。

        二叉搜索树的删除无非是三种情况：

1、删除的非递归写法

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)//需要判断cur等于根节点的情况，否则else中parent空指针解引用了{_root = _root->_right;}else{if (parent->_left == cur)//确定cur是parent的左还是右，再进行“托孤”parent->_left = cur->_right;elseparent->_right = cur->_right;}	delete cur;}else if (cur->_right == nullptr)//被删除节点左孩子不为空,右孩子为空{if (cur == _root){_root = _root->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}	delete cur;}else//被删除节点左右孩子均不为空{//左右孩子均不为空，就需要左子树的最大值或右子树的最小值选出来当新根（对被删除节点进行替换）Node* rightMin = cur->_right;//这里选用右树的最小值进行更换Node* rightMinParent = cur;while (rightMin->_left!=nullptr)//因为找最小值，不停找左树即可{rightMinParent = rightMin;rightMin = rightMin->_left;}//std::swap(cur->_key, rightMin->key);//用std的交换对自定义类型可能比较慢cur->_key = rightMin->_key;//还是用赋值好一点，即使是自定义类型，肯定有写赋值重载//rightMin的左节点必为空，判断父节点的链接方式即可if (rightMinParent->_left == rightMin)//两种情况，第一种如上方图删除8，实际干掉9位置，需要将10的左连至9的右rightMinParent->_left = rightMin->_right;else if (rightMinParent->_right == rightMin)//第二种如上方图删除10，实际干掉14，需要将10的右连至14的右rightMinParent->_right = rightMin->_right;delete rightMin;}return true;}}return false;
}

         1、先通过二叉搜索树的性质找到要删除的节点；

        2、找到需要删除的节点后，分三种情况进行讨论：

        一、被删除节点的左孩子为空，除了cur等于根节点情况下，其他情况下，父节点的孩子指针由指向被删除节点转为指向被删除节点的右孩子。（如图删除9和14）

        二、被删除节点的左孩子存在但右孩子为空，除了cur等于根节点情况下，其他情况下，父节点的孩子指针由指向被删除节点转为指向被删除节点的左孩子。（如图删除9）

        三、被删除的节点均不为空，可以选用左树最大节点或者右树最小节点对被删除节点进行值替换，问题转化为第一种或第二种情况。（详见代码注释）

2、删除的递归写法

bool _EarseR(Node*& root, const K& key)//形参给了引用，意义同插入的递归写法
{if (root == nullptr){return false;}if (root->_key < key)return _EarseR(root->_right, key);else if (root->_key > key)return _EarseR(root->_left, key);else//说明找到了要删除的节点,无需考虑root的父亲为空{Node* del = root;if (root->_left == nullptr)//被删除节点的左为空root = root->_right;//让root连接root的右树，因为是引用，所以父节点和root是连接的else if (root->_right == nullptr)//被删除节点左不为空但右为空root = root->_left;else//root左右子树均不为空{Node* rightMin = root->_right;while (rightMin->_left!=nullptr)//找到被删除节点的右树最小节点 {rightMin = rightMin->_left;}root->_key = rightMin->_key;//找到了交换key//对子树进行递归删除return _EarseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归}delete del;return true;}
}
bool EraseR(const K& key)
{return _EarseR(_root, key);
}

 找到节点后，同样需要分三种情况讨论。

        1、被删除节点左树为空；

        2、被删除节点左树不为空但右树为空；

        3、被删除节点左右子树均不为空。

---

七、二叉搜索树的使用场景

1、key搜索模型（节点存key）

        key搜索模型只用key作关键码，结构中只需存key，key即为需要搜索到的值。

        例如对英语单词拼写的检查，可以将词库中的所有单词存入二叉搜索树，通过二叉搜索树中检索单词是否存在，达到拼写报错目的。

key搜索模型整体代码

template <class K>
struct BSTreeNode
{BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;
};
template <class K>
struct BSTree
{typedef BSTreeNode<K> Node;BSTree():_root(nullptr){}//插入节点bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);//BSTreeNode对象中存放key值 }else{Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else//说明数字重复return false;}cur = new Node(key);//判断插入节点放在parent节点的左子树还是右子树if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}}return true;}bool InsertR(const K& key){return _InsertR(_root, key);}//中序遍历void InOrder()//因为外部取不到_root,所以这里套了一层调用函数{_InOrder(_root);std::cout << std::endl;}//查找bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}elsereturn true;}return false;}bool FindR(const K& key){return _FindR(_root, key) == nullptr ? false : true;}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)//需要判断cur等于根节点的情况，否则else中parent空指针解引用了{_root = _root->_right;}else{if (parent->_left == cur)//确定cur是parent的左还是右，再进行“托孤”parent->_left = cur->_right;elseparent->_right = cur->_right;}	delete cur;}else if (cur->_right == nullptr)//被删除节点左孩子不为空,右孩子为空{if (cur == _root){_root = _root->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}	delete cur;}else//被删除节点左右孩子均不为空{//左右孩子均不为空，就需要左子树的最大值或右子树的最小值选出来当新根Node* rightMin = cur->_right;//这里选用右树的最小值进行更换Node* rightMinParent = cur;while (rightMin->_left!=nullptr){rightMinParent = rightMin;rightMin = rightMin->_left;}//std::swap(cur->_key, rightMin->key);//用std的交换对自定义类型可能比较慢cur->_key = rightMin->_key;//还是用赋值好一点，即使是自定义类型，肯定有写赋值重载if (rightMinParent->_left == rightMin)//两种情况，第一种如图删除8，实际干掉9位置，需要将10的左连至9的右rightMinParent->_left = rightMin->_right;else if (rightMinParent->_right == rightMin)//第二种如图删除10，实际干掉14，需要将10的右连至14的右rightMinParent->_right = rightMin->_right;delete rightMin;}return true;}}return false;}bool EraseR(const K& key){return _EarseR(_root, key);}
private:Node* _root;void _InOrder(Node* _root){if (_root == nullptr){return;}_InOrder(_root->_left);std::cout << _root->_key << " ";_InOrder(_root->_right);}Node* _FindR(Node* root,const K& key){if (root == nullptr)return nullptr;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}elsereturn root;}bool _InsertR(Node*& root, const K& key)//形参是root的引用{if (root == nullptr){root = new Node(key);//因为root是父节点左/右孩子的别名，直接修改别名，链接关系存在，不用考虑父子节点连接关系return true;}if (root->_key < key)return _InsertR(root->_right, key);else if (root->_key > key)return _InsertR(root->_left, key);elsereturn false;}bool _EarseR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key)return _EarseR(root->_right, key);else if (root->_key > key)return _EarseR(root->_left, key);else//说明找到了要删除的节点,无需考虑root的父亲为空{Node* del = root;if (root->_left == nullptr)root = root->_right;else if (root->_right == nullptr)root = root->_left;else//root左右子树均不为空{Node* rightMin = root->_right;while (rightMin->_left!=nullptr)//找到右树最小节点 {rightMin = rightMin->_left;}root->_key = rightMin->_key;return _EarseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归}delete del;return true;}}
};

2、key/value搜索模型（节点既存key又存value）

        key/value搜索模型指每一个key值，都有与之对应的value值，例如英汉互译，一个英文单词可以对应一个翻译字符串。该模型还可以用于统计相同内容出现次数。（举例代码见下方测试函数。）

key/value搜索模型整体代码

namespace KV
{template <class K,class V>struct BSTreeNode{BSTreeNode(const K& key,const V& value):_left(nullptr), _right(nullptr), _key(key),_value(value){}BSTreeNode<K,V>* _left;BSTreeNode<K,V>* _right;K _key;V _value;};template <class K,class V>struct BSTree{typedef BSTreeNode<K,V> Node;BSTree():_root(nullptr){}//插入节点bool Insert(const K& key,const V& value){if (_root == nullptr){_root = new Node(key,value);//BSTreeNode对象中存放key值 }else{Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else//说明数字重复return false;}cur = new Node(key, value);//判断插入节点放在parent节点的左子树还是右子树if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}}return true;}bool InsertR(const K& key,const V& value){return _InsertR(_root, key, value);}//中序遍历void InOrder()//因为外部取不到_root,所以这里套了一层调用函数{_InOrder(_root);std::cout << std::endl;}//查找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;}elsereturn cur;}return nullptr;}Node* 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)//需要判断cur等于根节点的情况，否则else中parent空指针解引用了{_root = _root->_right;}else{if (parent->_left == cur)//确定cur是parent的左还是右，再进行“托孤”parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr)//被删除节点左孩子不为空,右孩子为空{if (cur == _root){_root = _root->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;}else//被删除节点左右孩子均不为空{//左右孩子均不为空，就需要左子树的最大值或右子树的最小值选出来当新根Node* rightMin = cur->_right;//这里选用右树的最小值进行更换Node* rightMinParent = cur;while (rightMin->_left != nullptr){rightMinParent = rightMin;rightMin = rightMin->_left;}//std::swap(cur->_key, rightMin->key);//用std的交换对自定义类型可能比较慢cur->_key = rightMin->_key;//还是用赋值好一点，即使是自定义类型，肯定有写赋值重载cur->_value = rightMin->_value;if (rightMinParent->_left == rightMin)//两种情况，第一种如图删除8，实际干掉9位置，需要将10的左连至9的右rightMinParent->_left = rightMin->_right;else if (rightMinParent->_right == rightMin)//第二种如图删除10，实际干掉14，需要将10的右连至14的右rightMinParent->_right = rightMin->_right;delete rightMin;}return true;}}return false;}bool EraseR(const K& key){return _EarseR(_root, key);}private:Node* _root;void _InOrder(Node* _root){if (_root == nullptr){return;}_InOrder(_root->_left);std::cout << _root->_key << " "<<_root->_value;_InOrder(_root->_right);}Node* _FindR(Node* root, const K& key){if (root == nullptr)return nullptr;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}elsereturn root;}bool _InsertR(Node*& root, const K& key, const V& value)//形参是root的引用{if (root == nullptr){root = new Node(key,value);//因为root是父节点左/右孩子的别名，直接修改别名，链接关系存在，不用考虑父子节点连接关系return true;}if (root->_key < key)return _InsertR(root->_right, key，value);else if (root->_key > key)return _InsertR(root->_left, key，value);elsereturn false;}bool _EarseR(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key)return _EarseR(root->_right, key);else if (root->_key > key)return _EarseR(root->_left, key);else//说明找到了要删除的节点,无需考虑root的父亲为空{Node* del = root;if (root->_left == nullptr)root = root->_right;else if (root->_right == nullptr)root = root->_left;else//root左右子树均不为空{Node* rightMin = root->_right;while (rightMin->_left != nullptr)//找到右树最小节点 {rightMin = rightMin->_left;}root->_key = rightMin->_key;root->_value = rightMin->_value;return _EarseR(root->_right, rightMin->_key);//return表示子树进行删除，结束掉递归}delete del;return true;}}};
}
void testKV1()//中英互译
{KV::BSTree<std::string, std::string> dic;dic.Insert("data", "数据");dic.Insert("algorithm", "算法");dic.Insert("map", "地图、映射");dic.Insert("Linux", "一款开源免费的操作系统");std::string str;while (std::cin >> str){KV::BSTreeNode<std::string, std::string>* ret = dic.Find(str);if (ret != nullptr){std::cout << "中文翻译：" << ret->_value << std::endl;}elsestd::cout << "查找失败！" << std::endl;}
}
void testKV2()//用于统计次数
{std::string arr[] = { "数学", "语文", "数学", "语文", "数学", "数学", "英语","数学", "英语", "数学", "英语" };KV::BSTree<std::string, int> count;for (auto& e : arr){KV::BSTreeNode<std::string, int>* ret = count.Find(e);if (ret != nullptr){ret->_value++;}else{count.Insert(e,1);}}count.InOrder();
}