【数据结构】二叉搜索树

目录

1、二叉搜索树的概念

2、二叉搜索树的实现

2.1 二叉搜索树的查找

2.2 二叉搜索树的插入

2.3 二叉搜索树的中序遍历

2.4 二叉搜索树的删除

3、二叉搜索树的应用

3.1 K模型

3.2 KV模型

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

---

1、二叉搜索树的概念

2、二叉搜索树的实现

2.1 二叉搜索树的查找

查找规则是：1. 从根开始比较，比根大则取根的右子树查找，比根小则去根的左子树查找

                      2.做多查找高度次，走到空，还没找到，则这个值不存在

首先，创建一个结点

template<class K>
struct BSTNode // 二叉搜索树的结点
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};

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; // 找到了返回true}return false; // 没找到返回false
}

2.2 二叉搜索树的插入

首先，需要先判断一下这颗二叉搜索树是否为空，若是空，则直接创建一个结点，结点的值赋值为要插入的值，并将_root指向这个结点

若不为空，则按二叉搜索树的性质往下查找，从根节点开始往下查找，当前遍历到的结点的值小于插入的值，则到当前节点的右子树查找，当前遍历到的结点的值大于插入的值，则到当前节点的左子树查找，直到遍历到的结点为空，那么这个位置就是插入的位置

注意，一定要记录当前遍历到的结点的父节点，因为当遍历到的结点为空，要插入时，需要知道遍历到的结点的父节点才能插入

然后，遍历到的结点为空时，这时候只知道其父节点，但并不知道遍历到的位置是其父节点的左孩子还是右孩子，所以还需要用插入的那个值与父节点的值比较一下，以判断是父节点的左孩子还是右孩子

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;}Node* newNode = new Node(key);if (parent->_key < key) parent->_right = newNode;else parent->_left = newNode;return true;
}

注意，二叉搜索树是不允许有重复的元素的，所以会设计一个bool返回值，当遍历二叉树时，若是找到了与要插入的值相同的值，则不进行插入，并返回false 

2.3 二叉搜索树的中序遍历

二叉搜索树也叫二叉排序树，正是因为二叉搜索树按照中序遍历打印出来后吗，是有序的

中序遍历是使用递归实现的，但是根节点是private的成员变量，外部没办法直接获取。此时有两种解决方法，第一种是在类中写一个函数GetRoot，第二种是写一个子函数，这里采用写子函数的方法

template<class K>
class BSTree
{typedef BSTNode<K> Node;
public: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; // 找到了返回true}return false; // 没找到返回false}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;}Node* newNode = new Node(key);if (parent->_key < key) parent->_right = newNode;else parent->_left = newNode;return true;}void InOrder(){_InOrder(_root);}
private:void _InOrder(Node* _root){if (_root == nullptr) return;_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}Node* _root = nullptr;
};

2.4 二叉搜索树的删除

首先，需要先找到需要删除的这个结点，所以函数需要有一个bool返回值，当找到了就进行删除操作，若没找到，则返回false。并且需要记录遍历到的位置的父亲结点

找到需要删除的结点后，会有3种情况：1. 要删除的结点没有孩子

                                                               2. 要删除的结点有1个孩子

                                                               3. 要删除的结点有2个孩子 

此时我们会发现，这两种是可以合成为一种的。因为当我们找到要删除的结点后，如果这个结点有一个孩子是空，那么我们就是用另一个孩子去替换掉这个结点

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){// 判断cur是父亲的左孩子还是右孩子if (parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){if (parent->_left == cur) parent->_left = cur->_left;else parent->_right = cur->_left;delete cur;return true;}// 要删除的结点有两个孩子else{// 先去右子树中寻找值最小的结点，也就是右子树最左边的那个结点Node* rightMin = cur->_right;Node* rightMinP = nullptr;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;rightMinP->_left = rightMin->_right;delete rightMin;return true;}}}return false;
}

此时容易写出这样的代码，但是这是有问题的，问题在于处理要删除的结点有两个孩子时

问题1：我们将rightMinP初始化为空，如果我们要删除的结点是6，那么rightMin初始化就是7，不会进入循环，rightMinP仍然是空，后面还有解引用就会出错，也很容易发现，实际上要删除的结点激素rightMin的父节点，也就是rightMinP直接初始化为cur即可

问题2：我们将rightMin的值与cur替换后，此时需要将rightMin的孩子给其父节点，前面分析过了rightMin的孩子最多只有一个(因为左孩子一定为空)，上面的代码是直接将rightMin的右孩子给其父节点的左孩子，因为是找的cur的右子树最左边的结点，所以很容易就写成上面那样，这样是符合删除3的，但是对于删除6是不满足的，因为删除6并没有进去cur的右子树中一直往左边找，所以应该修改成判断一下rightMin在rightMinP的左边还是右边，然后将rightMin的右孩子替换到rightMin的位置

template<class K>
struct BSTNode // 二叉搜索树的结点
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}
};
template<class K>
class BSTree
{typedef BSTNode<K> Node;
public: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; // 找到了返回true}return false; // 没找到返回false}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;}Node* newNode = new Node(key);if (parent->_key < key) parent->_right = newNode;else parent->_left = newNode;return true;}void InOrder(){_InOrder(_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 // 此时已经找到了要删除的结点{// 要删除的结点只有一个孩子或者没有孩子,此时只需要把它的孩子给他的父亲结点if (cur->_left == nullptr){// 判断cur是父亲的左孩子还是右孩子if (parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){if (parent->_left == cur) parent->_left = cur->_left;else parent->_right = cur->_left;delete cur;return true;}// 要删除的结点有两个孩子else{// 先去右子树中寻找值最小的结点，也就是右子树最左边的那个结点Node* rightMin = cur->_right;Node* rightMinP = cur;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:void _InOrder(Node* _root){if (_root == nullptr) return;_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}Node* _root = nullptr;
};

3、二叉搜索树的应用

3.1 K模型

K模型就是二叉搜索树的结点中只存放一个有效值

上面实现的就是K模型的二叉搜索树

K模型主要用来处理在不在的问题。如门禁系统，只需要判断一个人在不在门禁系统中。又如检查英文小说中是否有错误单词，只需要判断一个英文单词是否在词库中

3.2 KV模型

KV模型就是二叉搜索树的结点中存放两个有效值。每一个关键码key，都有与之对应的值value，即<key,value>的键值对

KV模型主要用来处理通过一个值(key)找另一个值(value)的问题。如简单词典、车库收费系统、统计单词出现的次数

对我们上面的二叉搜索树稍作修改，就能得到KV模型的二叉搜索树

1. 结点模板和类模板都增加一个模板参数

2. 插入结点时参数多一个value，不过比较时仍然用key比较

3. 查找时也只给key即可，不过现在需要返回的是结点的指针，因为找到了需要获取里面的值

4. 其余没有变化

KV模型的二叉搜索树仍然是不能有重复的key值的

template<class K,class V>
struct BSTNode_V // 二叉搜索树的结点
{K _key;V _value;BSTNode_V<K,V>* _left;BSTNode_V<K,V>* _right;BSTNode_V(const K& key,const V& value):_key(key),_value(value), _left(nullptr), _right(nullptr){}
};
template<class K,class V>
class BSTree_V
{typedef BSTNode_V<K,V> Node;
public: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; // 没找到返回空}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;}Node* newNode = new Node(key, value);if (parent->_key < key) parent->_right = newNode;else parent->_left = newNode;return true;}void InOrder(){_InOrder(_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 // 此时已经找到了要删除的结点{// 要删除的结点只有一个孩子或者没有孩子,此时只需要把它的孩子给他的父亲结点if (cur->_left == nullptr){// 判断cur是父亲的左孩子还是右孩子if (parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;delete cur;return true;}else if (cur->_right == nullptr){if (parent->_left == cur) parent->_left = cur->_left;else parent->_right = cur->_left;delete cur;return true;}// 要删除的结点有两个孩子else{// 先去右子树中寻找值最小的结点，也就是右子树最左边的那个结点Node* rightMin = cur->_right;Node* rightMinP = cur;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:void _InOrder(Node* _root){if (_root == nullptr) return;_InOrder(_root->_left);cout << _root->_key << "--" << _root->_value << " ";_InOrder(_root->_right);}Node* _root = nullptr;
};

利用KV模型实现一个简易的词典

void dictionary()
{BSTree_V<string, string> dict;dict.Insert("left", "左边");dict.Insert("right", "右边");dict.Insert("insert", "插入");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret) cout << "->" << ret->_value << endl;else cout << "无此单词，请重新输入" << endl;}
}

利用KV模型来记录每种水果的个数

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

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

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

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：O(logN)

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：O(N)

所以二叉搜索树并不是完美的，当其变成接近与单支树的情况时，时间复杂度是比较高的，所以引入的平衡二叉搜索树(AVL树和红黑树)。在内存中AVL树和红黑树已经够用了，但是在磁盘上仍然是不够的，所以又引入了B树家族