C++进阶 二叉搜索树

 目录

二叉搜索树概念

二叉搜索树的模拟实现

二叉搜索树的查找

二叉搜索树的插入

二叉搜索树的删除

二叉搜索树的性能分析

二叉搜索树的应用

K模型

 KV模型

---

二叉搜索树概念

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

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

可以看到二叉搜索树通过中序遍历后得出的数组是有序的。 

---

二叉搜索树的模拟实现

首先我们要创建一个节点结构体，结构体内容要包括指向左右节点的指针和自身的键值，为了能适配int的内置类型和string的自定义类型，我们使用模板构建节点结构体。

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

以下操作我们用以下数组进行操作：

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

  我们先搭一个二叉搜索树的基本框架，以节点为类型构建一个根节点root：

template<class K>
class BSTree
{typedef BSTNode<K> Node;private:Node* _root = nullptr;
};

---

二叉搜索树的查找

要实现查找功能要满足以下两个条件：

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

二叉搜索树查找的模拟实现代码如下： 

	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;  //没找到}

---

二叉搜索树的插入

插入的具体过程如下：

1. 树为空，则直接新增节点，赋值给root指针
2. 树不空，按二叉搜索树性质（比根大插右边，比根小插左边）查找插入位置，插入新节点

 二叉搜索树插入的模拟实现代码如下： 

	bool Insert(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->_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;}else{parent->_left = cur;}return true;}

这里为什么用bool类型作为返回值？原因：要插入的值可能和根节点相等，如果相等就不能插入，因为违反了二叉搜索树的性质（比根大插右边，比根小插左边）。

---

二叉搜索树的删除

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

1. 要删除的结点无孩子结点
2. 要删除的结点只有左孩子结点
3. 要删除的结点只有右孩子结点
4. 要删除的结点有左、右孩子结点

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

1. 情况1：没有孩子——直接删除
2. 情况2：一个孩子——按照二叉搜索树性质，将其子节点连接到父节点上
3. 情况3：两个孩子——在它的右子树中寻找中序下的第一个结点(key最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除  

此为删除的是根节点且根节点左子树为空的情况，直接将右子树的地址赋值给root，让他作为根节点即可，当然根节点右子树为空也是同样操作，直接赋值。 

 注意这里不会出现大小混乱，原因：

如果删除的节点是父节点的右子树，比父亲大，他的右子树比他本身还要大，所以接上后成立

如果删除的节点是父节点的左子树，比父亲小，根据性质，左子树所有值都比根小，所以删除节点的右子树也比父节点小，所以成立。

 这里的替代法找右子树的最小节点（最左节点）或者左子树的最大节点（最右节点都可以）

删除的模拟实现代码如下：

	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{// 删除// 0-1个孩子的情况if (cur->_left == nullptr)  //左孩子为空{if (parent == nullptr)   // 删除根节点且左子树为空{_root = cur->_right;}else  //删除的不是根节点{if (parent->_left == cur)   //看删除的节点是父节点的左还是右parent->_left = cur->_right;  //是左就把右子树接左边elseparent->_right = cur->_right;  //右就把右子树接右边}delete cur;  //避免野指针return true;}else if (cur->_right == nullptr)  //右孩子为空{if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;  return true;}else{// 2个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left) //右子树的最左节点{rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key; //替代if (rightMinP->_left == rightMin) //链接rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}

另外我们再增加上一个中序遍历的代码，将中序遍历的代码写在private区域，再在public区域调用这个中序函数，传参直接使用私有成员变量_root会方便许多，代码如下：

template<class K>
class BSTree
{typedef BSTNode<K> Node;void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}Node* _root = nullptr;
};

通过这些就能完成二叉搜索树的模拟实现了。

---

二叉搜索树的性能分析

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

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

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

左图为最优情况，二叉搜索树接近完全二叉树，其平均比较次数为：

右图为最差情况，二叉搜索树退化为类似单支树，其平均比较次数为：

---

二叉搜索树的应用

K模型

K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

1. 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
2. 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

 KV模型

每一个关键码Key，都有与之对应的值Value，即<Key,Value>的键值对。该种方式在现实生活中非常常见,英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对。STL库中的map和set就是利用了这种模型。