【C++】二叉搜索树

🌠 作者：@阿亮joy.
🎆专栏：《吃透西嘎嘎》
🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根

- 👉二叉搜索树的概念👈
- 👉模拟实现二叉搜索树👈
- - 节点的定义
  - 插入操作（非递归）
  - 查找操作（非递归）
  - 删除操作（非递归）
  - 查找操作（递归）
  - 插入操作（递归）
  - 删除操作（递归）
  - 析构函数
  - 拷贝构造
  - 赋值运算符重载
  - 完整代码
- 👉二叉搜索树的性能分析👈
- 👉二叉搜索树的应用👈
- 👉总结👈

👉二叉搜索树的概念👈

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

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

因为二叉搜索树的左子树所有节点的键值比根节点的小，右子树所有节点的键值比根节点的大，所以查找的效率就会比较高，查找效率为O(h)，h为树的高度。
二叉搜索树也被称为二叉排序树的原因是：二叉搜索树中序遍历的结果是升序的。
二叉搜索树中的键值是不允许修改的，如果可以修改的话，就有可能不再是二叉搜索树了。

👉模拟实现二叉搜索树👈

节点的定义

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

因为键值可以是多种类型的，所以我们树的节点定义成模板类。同时还提供了节点的构造函数，new节点时可以调用节点的构造函数初始化。

插入操作（非递归）

插入的具体过程如下：

树为空，则直接新增节点，赋值给 root 指针。
树不空，按二叉搜索树性质查找插入位置，插入新节点。即当前节点的值小于插入节点的值，往右走；当前节点的值大于插入节点的值，往左走；直至当前节点为空，找到插入位置。走过过程中，还需要记录前一个节点才能完成插入。
插入可能从左边插入，也有可能从右边插入。我们可以通过比较前一个节点的值与插入节点的值的大小，就可以知道从哪一边插入节点。
当二叉搜索树中已经存在插入的值时，插入失败，返回false。因为二叉搜索树中不允许重复的值存在。

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->_right;}else if(cur->_key > key)	// 当前节点的值大于插入节点的值，往左走{parent = cur;cur = cur->_left;}else{return false;	// 插入失败}}// 插入节点cur = new Node(key);// 判断从哪边插入节点if (parent->_key < key)	// 从右边插入节点parent->_right = cur;elseparent->_left = cur;return true;	// 插入成功
}

现在插入节点的接口已经写完了，那么我们再写一个中序遍历接口Inorder来验证一下我们写得对不对。因为中序遍历首先要有根节点才能进行遍历，而根节点_root是私有的，在类外无法拿到它。但是遍历是需要根节点的，那怎么解决呢？我们可以在类里定义一个公有的辅助函数帮我们拿到根节点_root，然后就可以遍历了。但是个人比较推荐第二种方法：在类里定义一个私有的中序遍历的子函数_Inorder，Inorder函数调用子函数_Inorder来完成中序遍历。

public:void Inorder(){_Inorder(_root);cout << endl;}
private:// 中序遍历的子函数void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << endl;_Inorder(root->_right);}

在这里插入图片描述

注：二叉搜索树的中序遍历结果是没有重复元素的升序序列。

查找操作（非递归）

查找操作的逻辑和插入操作的逻辑是一样的，具体步骤如下：

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
最多查找高度次，走到到空，还没找到，这个值不存在。

bool Find(const K& key)
{if (_root == nullptr)return false;Node* cur = _root;while (cur){if (cur->_key < key)	// 当前节点的值比要查找的值小，往右走cur = cur->_right;else if (cur->_key > key)	// 当前节点的值比要查找的值大，往左走cur = cur->_left;elsereturn true;	// 找到了}return false;	// 没找到
}

删除操作（非递归）

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

要删除的结点无孩子结点
要删除的结点只有左孩子结点
要删除的结点只有右孩子结点
要删除的结点有左、右孩子结点

看起来待删除节点有四种情况，实际情况 1 可以与情况 2或者 3 合并起来，因此真正的删除过程如下：

情况 2：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点（直接删除）
情况 3：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点（直接删除）
情况 4：找出删除节点左子树最大值的节点或者是右子树最小值的节点，并与删除节点进行值交换。交换后，上述两个节点就成了要删除的替换节点。替换节点要么没有孩子，要么只有一个孩子，可以转化为前面的三种情况（替换法删除）

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 = cur->_right;}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;}else    // 待删除节点有左右孩子(替换法删除){// 找到右子树的最小节点进行替换Node* minParent = cur;	// minParent不能设置为nullptrNode* min = cur->_right;while (min->_left){minParent = min;min = min->_left;}swap(cur->_key, min->_key);// 因为替换节点是右子树的最小节点,没有左孩子if (minParent->_left == min)	// 替换节点在父节点的左边minParent->_left = min->_right;elseminParent->_right = min->_right;delete min;}return true;}}return false;	// 删除失败
}

测试删除接口

void BSTreeTest2()
{BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 , 5 };for (auto e : a){t.Insert(e);}for (auto e : a){t.Erase(e);t.Inorder();}cout << endl;
}

在这里插入图片描述

如果想要啊检验自己是否掌握删除操作的老铁，可以做做力扣上的这道题：删除二叉搜索树中的节点。

查找操作（递归）

因为查找操作也是需要用到根节点的，所以递归的查找操作也是采用子函数的方式来实现。

在这里插入图片描述

public:bool FindR(const K& key){return _FindR(_root, key);}
private: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);elsereturn true;}

插入操作（递归）

public:bool InsertR(const K& key){return _InsertR(_root, key);}
private: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);elsereturn false;}

注：_InsertR 函数的Node*&在插入节点时起作用，root是其父亲的左指针或者右指针的别名，所以root = new Node(key)就可以实现将新插入节点和父节点链接起来。当树为空时，上面的代码也能实现插入节点。

删除操作（递归）

public:bool EraseR(const K& key){return _EraseR(_root, key);}
private: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;	// 记录要删除的节点// 此时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;}swap(min->_key, root->_key);//return Erase(key);	// 错的,因为树的结构已经该变了return _EraseR(root->_right, key);	//调用自己进行删除}delete del;return true;}}

注：引用在删除时才会起作用，因为此时root是其父节点左指针或者右指针的别名，root = root->_left或者root = root->_right就可以改变父节点左指针或右指针的指向。当要删除的节点有左右孩子时，需要找到右子树的最左节点（注：也可以找左子树的最右节点）。找到后，进行值交换将替换节点的值改为key，最后调用_EraseR(root->_right, key)删除替换节点即可完成删除。以上代码对于删除节点为根节点且没有左子树或者右子树的特殊情况，也能完成删除。

在这里插入图片描述

递归插入删除操作演示

在这里插入图片描述

析构函数

树的销毁是通过后序遍历的顺序来销毁的，因为不能先销毁根节点。

public:~BSTree(){_Destory(_root);}
private:void _Destory(Node*& root){if (root == nullptr)return;_Destory(root->_left);_Destory(root->_right);delete root;root = nullptr;}

拷贝构造

public:// 构造函数会走初始化列表,将根节点初始化为nullptrBSTree(){}// C++11的用法:强制编译器生成默认的构造// BSTree() = default;BSTree(const BSTree<K>& t){_root = _Copy(t._root);}
private: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;}Node* _Copy(Node* root){if (root == nullptr)return nullptr;// 后序遍历拷贝二叉搜索树Node* left = _Copy(root->_left);	// 先构造左子树Node* right = _Copy(root->_right);	// 再构造右子树Node* copyRoot = new Node(root->_key);	// 最后构造根copyRoot->_left = left;copyRoot->_right = right;return copyRoot;}
private:Node* _root = nullptr;

赋值运算符重载

BSTree<K>& operator=(BSTree<K> t)
{swap(_root, t._root);return *this;
}

因为传值传参会存在拷贝构造，所以只需要交换两个二叉搜索树的根节点即可。

拷贝构造和赋值运算符重载测试

在这里插入图片描述

完整代码

#pragma oncetemplate <class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key): _left(nullptr), _right(nullptr), _key(key){}
};//class BinarySearchTree
template <class K>
class BSTree
{
public:typedef BSTreeNode<K> Node;BSTree(){}BSTree(const BSTree<K>& t){_root = _Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){_Destory(_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->_right;}else if(cur->_key > key)	// 当前节点的值大于插入节点的值，往左走{parent = cur;cur = cur->_left;}else{return false;	// 插入失败}}// 插入节点cur = new Node(key);// 判断从哪边插入节点if (parent->_key < key)	// 从右边插入节点parent->_right = cur;elseparent->_left = cur;return true;	// 插入成功}bool InsertR(const K& key){return _InsertR(_root, key);}bool Find(const K& key){if (_root == nullptr)return false;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);}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 = cur->_right;}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;}else    // 待删除节点有左右孩子(替换法删除){// 找到右子树的最小节点进行替换Node* minParent = cur;	// minParent不能设置为nullptrNode* min = cur->_right;while (min->_left){minParent = min;min = min->_left;}swap(cur->_key, min->_key);// 因为替换节点是右子树的最小节点,没有左孩子if (minParent->_left == min)	// 替换节点在父节点的左边minParent->_left = min->_right;elseminParent->_right = min->_right;delete min;}return true;}}return false;	// 删除失败}bool EraseR(const K& key){return _EraseR(_root, key);}void Inorder(){_Inorder(_root);cout << endl;}private:Node* _root = nullptr;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);elsereturn 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);elsereturn 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;	// 记录要删除的节点// 此时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;}swap(min->_key, root->_key);//return Erase(key);	// 错的,因为树的结构已经该变了return _EraseR(root->_right, key);}delete del;return true;}}void _Destory(Node*& root){if (root == nullptr)return;_Destory(root->_left);_Destory(root->_right);delete root;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;}//Node* _Copy(Node* root)//{//	if (root == nullptr)//		return nullptr;//	// 后序遍历拷贝二叉搜索树//	Node* left = _Copy(root->_left);//	Node* right = _Copy(root->_right);//	Node* copyRoot = new Node(root->_key);//	copyRoot->_left = left;//	copyRoot->_right = right;//	return copyRoot;//}
};

👉二叉搜索树的性能分析👈

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

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

二叉搜索树的增删查的时间复杂度为O(h)，h为树的高低。最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为 $log⁡N\log N$ 。最差情况下，二叉搜索树退化为单支树(或者类似单支)，此时h == N，N为节点的个数。

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

👉二叉搜索树的应用👈

Key 模型：Key 模型即只有 Key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为 Key，构建一棵二叉搜索树。
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型：每一个关键码 Key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文 <word, chinese> 就构成一种键值对；
再比如统计水果次数，统计成功后，给定水果名就可快速找到其出现的次数，水果与其出现次数就是 <fruit, count> 就构成一种键值对。

KeyValue 模型

namespace KeyValue
{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):_left(nullptr), _right(nullptr), _key(key), _value(value){}};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);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};
}