【C++从练气到飞升】16---二叉搜索树

• 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

• 最多查找高度次，走到空还没找到，说明这个值不存在。

小Tips：这里最多查找高度次的时间复杂度并不是O(logN)，是建立在比较理想的情况下，即这颗二叉树是一颗满二叉树或者完全二叉树。在极端情况下，这棵二叉树只有一条路径，此时最多查找高度次的时间复杂度就是O(logN)。

2.2 二叉搜索树的插入

插入的具体过程如下：

• 树为空：则直接新增节点，赋值给 root 指针。

• 树不为空：先按二叉搜索树的性质寻找插入位置，插入新节点。

2.3 二叉搜索树的删除

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

1. 要删除的结点没有孩子结点。

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

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

4. 要删除的结点有左、右孩子节点。

• 情况一（要删除的结点只有左孩子）：删除该节点且使被删除节点的双亲结点指向被删除结点的左孩子结点----直接删除。

• 情况二（要删除的结点只有右孩子）：删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点-----直接删除。

• 情况三（要删除的结点有左、右孩子）：在它的左子树中寻找出关键码最大的结点，用它的值填补到被删除结点中，再来处理该结点的删除问题----替换法删除。

三、二叉搜索树的实现

二插搜索树只是一种结构，它本质上是由一个个结点链接而成，因此我们首先需要定义一个结点类，这个结点用来存储数据。有了结点类之后就需要定义一个二叉搜索树的类，这个类主要是用来维护结构的，实现增删查改等功能，因为它是维护结构的，因此这个类里面的成员变量只需要一个根节点即可，有了这个根节点就能对整个数的结构进行维护管理。

template <class K>
struct BinarySearchTreeNode
{typedef BinarySearchTreeNode<K> TNode;BinarySearchTreeNode(const K& val = K()):_val(val),_left(nullptr),_right(nullptr){}K _val;TNode* _left;TNode* _right;
};

3.2 BinarySearchTree（二叉搜索树类）

template <class K>
class BinarySearchTree
{typedef BinarySearchTreeNode<K> BSTNode;typedef BinarySearchTree<K> Self;
public:BinarySearckTree():_root(nullptr){}
private:BSTNode* _root;
};

3.2.2 insert（插入）

非递归版：

bool insert(const K& val)
{if (_root == nullptr){_root = new BSTNode(val);return true;}BSTNode* newnode = new BSTNode(val);BSTNode* cur = _root;BSTNode* parent = nullptr;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{return false;//相等就说明树中已经有了，就应该插入失败}}//if (parent->_left == cur)//左右都是空，每次就走上面这个了if(val < parent->_val){parent->_left = newnode;}else{parent->_right = newnode;}return true;
}

小Tips：需要单独考虑根节点为空的情况。用 cur 找到该结点应该要插入的位置，用 parent 指向该位置的双亲结点，以实现链接关系。最后还需要判断插入到双亲结点的左侧还是右侧。我们实现的这个二叉搜索树要求存储相同值的结点在一个二叉搜索树中只能出现一次，因此当插入一个值 val 的时候，如果检测到树中已经有一个结点存的是 val，那么就应该返回 false，表明插入失败。

递归版：

//插入(递归---版本一)
private:bool _InsertR(BSTNode*& root, BSTNode* parent, const K& key){if (root == nullptr)//为空说明就是在该位置插入{BSTNode* newnode = new BSTNode(key);if (parent != nullptr){if (key < parent->_val){parent->_left = newnode;}else{parent->_right = newnode;}}else{root = newnode;}return true;}//root不为空说明还没有找到待插入的位置，还得继续找if (key < root->_val){return _InsertR(root->_left, root, key);}else if (key > root->_val){return _InsertR(root->_right, root, key);}else{return false;}}
public://插入(递归)bool InsertR(const K& key){return _InsertR(_root, _root, key);}

//插入(递归---版本二)
private:bool _InsertR(BSTNode*& root, const K& key){if (root == nullptr)//为空说明就是在该位置插入{root = new BSTNode(key);return true;}//root不为空说明还没有找到待插入的位置，还得继续找if (key < root->_val){return _InsertR(root->_left, key);}else if (key > root->_val){return _InsertR(root->_right, key);}else{return false;}}
public://插入(递归)bool InsertR(const K& key){return _InsertR(_root, key);}

小Tips：在空树的时候执行插入，是需要改变根节点 _root 的，即需要对指针进行修改，因此这里需要使用引用或者二级指针。

private:void _InOrder(BSTNode* root) const{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_val << " ";_InOrder(root->_right);}
public:void InOrder(){_InOrder(_root);cout << endl;}

小Tips：这里的中序遍历用的是递归的方式来实现的，但是递归函数一定是需要一个参数的，要中序遍历整个二叉树，用户一定是要把根节点 _root 传给这个函数，但是根节点 _root 是私有的成员变量，用户是访问不到的，因此我们不能直接提供中序遍历函数给用户。正确的做法是，虽然用户访问不到根结点，但是类里面可以访问呀，所以我们可以在类里面实现一个中序遍历的子函数 _InOrder，在这个子函数中实现中序遍历的逻辑，然后我们再去给用户提供一个中序遍历的函数接口 InOrder，由它去调用 _InOrder。这样以来用户就可以正常去使用中序遍历啦。

非递归版：

bool find(const K& key)
{BSTNode* cur = _root;while (cur){if (key < cur->_val){cur = cur->_left;}else if (key > cur->_val){cur = cur->_right;}else{return true;}}return false;
}

递归版：

private:bool _FindR(BSTNode* root, const K& key){if (root == nullptr){return false;}if (key < root->_val){return _FindR(root->_left, key);}else if (key > root->_val){return _FindR(root->_right, key);}else{return true;}}
public:bool FindR(const K& key){return _FindR(_root, key);}

3.2.5 erase（删除）

非递归版：

bool erase(const K& key)
{BSTNode* cur = _root;BSTNode* parent = nullptr;//先找需要删除的结点while (cur){if (key < cur->_val){parent = cur;cur = cur->_left;}else if (key > cur->_val){parent = cur;cur = cur->_right;}else{//到这里说明cur就是待删除的节点if (cur->_left == nullptr)//如果cur只有一个孩子(只有右孩子)，直接托孤{if (parent == nullptr)//说明删除的是根结点{_root = _root->_right;}else if (cur == parent->_left)//判断cur是左孩子还是右孩子{parent->_left = cur->_right;}else if(cur == parent->_right){parent->_right = cur->_right;}}else if(cur->_right == nullptr)//如果cur只有一个孩子(只有左孩子){if (parent == nullptr)//说明删除的是根结点{_root = _root->_left;}else if (cur == parent->_left)//判断cur是左孩子还是右孩子{parent->_left = cur->_left;}else if (cur == parent->_right){parent->_right = cur->_left;}}else//到这里说明cur有两个孩子{BSTNode* parent = cur;BSTNode* leftmax = cur->_left;//找到左孩子中最大的那个while (leftmax->_right){parent = leftmax;leftmax = leftmax->_right;}swap(cur->_val, leftmax->_val);cur = leftmax;//有一种极端情况就是左边只有一条路径if (leftmax == parent->_left){parent->_left = leftmax->_left;}else{parent->_right = leftmax->_left;}}delete cur;return true;}}return false;
}

小Tips：在上面的代码中我们始终让 cur 指向待删除节点，parent 指向待删除结点的双亲，也就是 cur 的双亲。删除大体上就分为2. 3小节中提到的三种情况。但是里面任然有一些细节需要我们注意，比如删除根结点的情况，即 parent == nullptr 的时候。在情况一和情况二中，我们还需要判断待删除结点 cur 是其双亲结点 parent 的左孩子还是右孩子，以保证让 cur 的孩子和 parent 建立正确的链接关系。情况三，待删除的结点有两个孩子，我们这里的做法是，找出 cur 左子树中最大的那个节点 leftmax，让它来替换 cur，帮助 cur 带“孩子”。找到左子树中值最大的结点很容易，从 cur 的左孩子开始，一路往右即可。找到后交换 cur 和 leftmax 中存储的值。交换后 leftmax 就变成了要删除的结点，所以所以此时需要让 cur 重新指向 leftmax 这个结点。由于要删除 leftmax 结点，为了方便后面修改链接关系，这里我们还需要找到 leftmax 的双亲结点，因此在这个局部域中我们重新定义了一个 parent，它和外面那个 parent 并不冲突，优先使用局部的，但是注意里面这个 parent 表示的意义和外面 parent 的意义是有所不同的，前者表示 cur 左树中最大节点的双亲结点，后者表示 cur 的双亲结点。最后我们需要通过修改链接关系来实现 cur 结点的删除，这里的链接关系有以下两种情形：

情形一：

小Tips：Step2 中的交换是交换节点中的值，并不是交换两个结点。最终 leftmax 和 cur 指向同一个结点。

情形二：

小Tips：情形二与情形一最大的不同点体现在两个地方，第一情形二中的 parent 就是 cur，只说明我们在定义 parent 赋初值的时候不能让 parent = nullptr，应该让 parent = cur，否则后面修改链接关系会出现访问空指针的问题。第二点不同在于修改链接关系，情形二是让 parent 的左孩子指向 leftmax 的左孩子；情形一是让 parent 的右孩子指向 leftmax 的左孩子。因此在修改链接关系的时候要进行判断，看是哪种情形。在第二点不同里面又有一个相同点，即无论是 parent 的左孩子，还是 parent 的右孩子，最终都指向了 leftmax 的左孩子，这是为什么呢？原因其实很简单，leftmax 的右孩子一定为空，而左孩子则不一定为空。为什么可以肯定右孩子一等为空，因为 leftmax 是左子树中最大的那个结点，如果它的右孩子不为空，说明当前这个 leftmax 一定不是最大的那个结点。因此在修改链接关系的时候，要让 parent 与 leftmax 的左孩子建立连接。最后需要注意，交换完之后，只能通过修改链接关系去删除 cur 结点，不能通过递归调用去删除，因为这个函数每次都是从根节点开始查找的，交换后这棵树暂时不满足二叉搜索树的结构，以情形一为例，它就找不到存储8的结点。

递归版：

private:
//删除递归版bool _eraseR(BSTNode*& root, const K& key){if (root == nullptr){return false;}if (key < root->_val){return _eraseR(root->_left, key);}else if (key > root->_val){return _eraseR(root->_right, key);}else{//相等了，需要进行删除了BSTNode* del = root;if (root->_left == nullptr)//左为空{root = root->_right;}else if (root->_right == nullptr)//右为空{root = root->_left;}else//左右都不为空{BSTNode* parent = root;BSTNode* leftmax = root->_left;//找到左孩子中最大的那个while (leftmax->_right){parent = leftmax;leftmax = leftmax->_right;}swap(root->_val, leftmax->_val);return _eraseR(root->_left, key);}delete del;del = nullptr;return true;}}
public://删除递归版bool eraseR(const K& key){return _eraseR(_root, key);}

小Tips：在交换后，虽然整棵树可能不满足二叉搜索树的结构，但是 root 结点的左子树一定是满足二叉搜索树的，因为我们交换的是 root 结点的 _val 和左子树中最大的那个 _val，而 root 结点的 _val 一定是比左子树中最大的那个 _val 还要大的，所以交换完之后 root 的左子树任然满足二叉搜索树的结构，此时我们就可以通过递归调用去 root 的左子树中找要删除的结点，并且交换后待删除的结点一定变成了情况一或者情况二中的一种。递归版中对情况一和情况二的处理变简单了许多，因为 root 是一个引用，如果发现 root 的一个孩子为空，直接把 root 的另一个孩子赋值给它即可，在赋值之前记得保存一下 root 的值，这个值指向的结点就是要删除的结点，把这个值保存下来后面才能去 delete，否则赋值后就没有指针指向该结点，那就没办法释放这个结点的空间资源，就会造成内存泄漏。非递归中即使用了引用也不能这样搞，因为非递归中，一个引用始终是在一个函数栈帧里面，而引用是不能改变指向的。但是递归就不一样了，每一次递归调用都会开辟新的函数栈帧，每一个函数栈帧中 root 都是不同结点的别名。

private://析构子函数void Destruction(BSTNode*& root){if (root == nullptr){return;}//先去释放左孩子和右孩子的空间资源Destruction(root->_left);Destruction(root->_right);//再去释放root自己的空间资源delete root;root = nullptr;//形参root如果不加引用，这里置空是没有任何意义的，因为不加引用这里仅仅是一份拷贝return;}
public://析构函数~BinarySearckTree(){Destruction(_root);}

3.2.7 BinarySearchTree(const Self& tree)（拷贝构造）

注意拷贝构造不能直接去调用 insert，因为数据插入的顺序不同，这棵树最终的结构也是不同的，虽然最终也符合二叉树的结构，但是还是和被拷贝的树有所不同。正确做法是，走一个前序遍历，遍历到 tree 的一个结点时，去 new 一个结点，存储同样的值。

写法一：

//拷贝构造函数的子函数
private:void Construct(BSTNode*& root, BSTNode* copy){if (copy == nullptr){root = nullptr;return;}root = new BSTNode(copy->_val);//通过引用直接来实现链接关系Construct(root->_left, copy->_left);Construct(root->_right, copy->_right);}
public://拷贝构造BinarySearchTree(const Self& tree):_root(nullptr){Construct(_root, tree._root);}

写法二：

private:
//拷贝构造子函数(写法二)BSTNode* Construct(BSTNode* root){if (root == nullptr){return nullptr;}BSTNode* newnode = new BSTNode(root->_val);newnode->_left = Construct(root->_left);//通过返回值来实现链接关系newnode->_right = Construct(root->_right);return newnode;}
public://拷贝构造(写法二)BinarySearchTree(const Self& tree){_root = Construct(tree._root);}

小Tips：上面两种写法的不同点在于，方法一是通过引用去实现链接关系，方法二则是通过返回值的方式来实现链接关系。

public:
//赋值运算符重载(现代写法)Self& operator=(Self tree){swap(_root, tree._root);//交换两颗搜索二叉树就是交换它们里面维护的根节点return *this;}

小Tips：上面两种写法的不同点在于，方法一是通过引用去实现链接关系，方法二则是通过返回值的方式来实现链接关系。

3.2.8 operator=（赋值运算符重载）

public:
//赋值运算符重载(现代写法)Self& operator=(Self tree){swap(_root, tree._root);//交换两颗搜索二叉树就是交换它们里面维护的根节点return *this;}

四、二叉搜索树的应用

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

• 以词库中所有单词集合中的每个单词作为 Key，构建一颗二叉搜索树。

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

我们上面手搓的这可二叉搜索树就是 Key 模型，因为这颗树的结点里面只能存储一个值，这个值就是 Key。

4.2 KV模型

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

• 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文 <word，Chinese> 就构成一种键值对。

• 再比如统计单词次数，统计成功后，给定单词就可以快速找到其出现的次数，单词与其出现次数就是 <word，count> 就构成一种键值对。

4.2.1 KV 模型手撕

#pragma oncenamespace K_V
{template <class K, class V>struct BinarySearchTreeNode{typedef BinarySearchTreeNode<K, V> TNode;BinarySearchTreeNode(const K& key = K(), const V& val = V()):_key(key), _val(val), _left(nullptr), _right(nullptr){}K _key;V _val;TNode* _left;TNode* _right;};template <class K, class V>class BinarySearchTree{typedef BinarySearchTreeNode<K, V> BSTNode;typedef BinarySearchTree<K, V> Self;private:void _InOrder(BSTNode* root) const{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << "--" << root->_val << endl;_InOrder(root->_right);}BSTNode* _FindR(BSTNode* root, const K& key)//KV模型中的Key不能被修改，但是Val可以被修改{if (root == nullptr){return nullptr;}if (key < root->_key){return _FindR(root->_left, key);}else if (key > root->_key){return _FindR(root->_right, key);}else{return root;}}//插入(递归---版本一)//bool _InsertR(BSTNode*& root, BSTNode* parent, const K& key)//{//	if (root == nullptr)//为空说明就是在该位置插入//	{//		BSTNode* newnode = new BSTNode(key);//		if (parent != nullptr)//		{//			if (key < parent->_key)//			{//				parent->_left = newnode;//			}//			else//			{//				parent->_right = newnode;//			}//		}//		else//		{//			root = newnode;//		}//		return true;//	}//	//root不为空说明还没有找到待插入的位置，还得继续找//	if (key < root->_key)//	{//		return _InsertR(root->_left, root, key);//	}//	else if (key > root->_key)//	{//		return _InsertR(root->_right, root, key);//	}//	else//	{//		return false;//	}//}//插入(递归---版本二)bool _InsertR(BSTNode*& root, const K& key, const V& val){if (root == nullptr)//为空说明就是在该位置插入{root = new BSTNode(key, val);return true;}//root不为空说明还没有找到待插入的位置，还得继续找if (key < root->_key){return _InsertR(root->_left, key, val);}else if (key > root->_key){return _InsertR(root->_right, key, val);}else{return false;}}//删除递归版bool _eraseR(BSTNode*& root, const K& key){if (root == nullptr){return false;}if (key < root->_key){return _eraseR(root->_left, key);}else if (key > root->_key){return _eraseR(root->_right, key);}else{//相等了，需要进行删除了BSTNode* del = root;if (root->_left == nullptr)//左为空{root = root->_right;}else if (root->_right == nullptr)//右为空{root = root->_left;}else//左右都不为空{BSTNode* parent = root;BSTNode* leftmax = root->_left;//找到左孩子中最大的那个while (leftmax->_right){parent = leftmax;leftmax = leftmax->_right;}std::swap(root->_key, leftmax->_key);return _eraseR(root->_left, key);}delete del;del = nullptr;return true;}}//析构子函数void Destruction(BSTNode*& root){if (root == nullptr){return;}//先去释放左孩子和右孩子的空间资源Destruction(root->_left);Destruction(root->_right);//再去释放root自己的空间资源delete root;root = nullptr;//形参root如果不加引用，这里置空是没有任何意义的，因为不加引用这里仅仅是一份拷贝return;}//拷贝构造函数的子函数(写法一)void Construct(BSTNode*& root, BSTNode* copy){if (copy == nullptr){root = nullptr;return;}root = new BSTNode(copy->_key);Construct(root->_left, copy->_left);Construct(root->_right, copy->_right);}//拷贝构造子函数(写法二)BSTNode* Construct(BSTNode* root){if (root == nullptr){return nullptr;}BSTNode* newnode = new BSTNode(root->_key);newnode->_left = Construct(root->_left);newnode->_right = Construct(root->_right);return newnode;}public:BinarySearchTree():_root(nullptr){}//拷贝构造(写法一)/*BinarySearchTree(const Self& tree):_root(nullptr){Construct(_root, tree._root);}*///拷贝构造(写法二)BinarySearchTree(const Self& tree){_root = Construct(tree._root);}//赋值运算符重载(现代写法)Self& operator=(Self tree){swap(_root, tree._root);//交换两颗搜索二叉树就是交换它们里面维护的根节点return *this;}//插入(非递归)bool insert(const K& key, const V& val){if (_root == nullptr){_root = new BSTNode(key, val);return true;}BSTNode* newnode = new BSTNode(key, val);BSTNode* cur = _root;BSTNode* parent = nullptr;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{return false;//相等就说明树中已经有了，就应该插入失败}}//if (parent->_left == cur)//左右都是空，每次就走上面这个了if (key < parent->_key){parent->_left = newnode;}else{parent->_right = newnode;}return true;}//插入(递归)bool InsertR(const K& key, const V& val){return _InsertR(_root, key, val);}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}//查找(非递归)BSTNode* find(const K& key){BSTNode* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return cur;}}return nullptr;}//查找(递归)BSTNode* FindR(const K& key){return _FindR(_root, key);}//删除(非递归)bool erase(const K& key){BSTNode* cur = _root;BSTNode* parent = nullptr;//先找需要删除的结点while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{//到这里说明cur就是待删除的节点if (cur->_left == nullptr)//如果cur只有一个孩子(只有右孩子)，直接托孤{if (parent == nullptr){_root = _root->_right;}else if (cur == parent->_left)//判断cur是左孩子还是右孩子{parent->_left = cur->_right;}else if (cur == parent->_right){parent->_right = cur->_right;}}else if (cur->_right == nullptr)//如果cur只有一个孩子(只有左孩子){if (parent == nullptr){_root = _root->_left;}else if (cur == parent->_left)//判断cur是左孩子还是右孩子{parent->_left = cur->_left;}else if (cur == parent->_right){parent->_right = cur->_left;}}else//到这里说明cur有两个孩子{BSTNode* parent = cur;BSTNode* leftmax = cur->_left;//找到左孩子中最大的那个while (leftmax->_right){parent = leftmax;leftmax = leftmax->_right;}std::swap(cur->_key, leftmax->_key);cur = leftmax;//有一种极端情况就是左边只有一条路径if (leftmax == parent->_left){parent->_left = leftmax->_left;}else{parent->_right = leftmax->_left;}}delete cur;return true;}}return false;}//删除递归版bool eraseR(const K& key){return _eraseR(_root, key);}//析构函数~BinarySearchTree(){Destruction(_root);}private:BSTNode* _root = nullptr;};
}void TestBSTree4()
{// 统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };K_V::BinarySearchTree<string, int> countTree;for (const auto& str : arr){// 先查找水果在不在搜索树中// 1、不在，说明水果第一次出现，则插入<水果, 1>// 2、在，则查找到的节点中水果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.FindR(str);if (ret == NULL){countTree.insert(str, 1);}else{ret->_val++;}}countTree.InOrder();
}

小Tips：虽然变成了 KV 模型，但它仍然是一颗二叉搜索树，因此整棵树的结构没有发生任何变化。唯一的变化在于树的结点，对与 KV 模型来说，树中的结点不仅要存 Key，还要存 Value，这就进一步导致在插入时不仅要插入 Key，还要插入一个与该 Key 对应的 Value。其次对 KV 模型来说，Key 不允许被修改，Value 可以被修改，因此对 KV 模型来说，在 Find 的时候应该返回结点的指针，这样方便后续进行一些操作。

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二插搜索树的深度的函数，即结点越深，则比较次数越多。但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树。

• 最优情况下：二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数为：log2^n。
• 最差情况下：二叉搜索树退化为单支树（或者类似单支），其平均比较次数为：N/2。如果退化成了单支树，那么二叉搜索树的性能就失去了。此时就需要用到即将登场的 AVL 树和红黑树了。