二叉搜索树（BST,Binary Search Tree）

前言

一、二叉搜索树概念

二、二叉搜索树的实现与操作

1.查找

2.插入

3.删除

4.中序遍历

5.完整代码

三、二叉搜索树的应用（K模型、KV模型）

1.K模型

2.KV模型

3.完整代码

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

前言

为何学？

1.二叉搜索树是一种树形结构，是一种查找效率非常高的结构，值得我们去学习

2.map和set的底层也是二叉搜素树，学习二叉搜索树可以让我们更好的了解set和map的特性

一、二叉搜索树概念

二叉搜索树（BST,Binary Search Tree）又称二叉排序树、二叉查找树

它可以是一颗空树

如果不是，它（或者说它的任何一颗子树）必须满足下列条件：

1.如果它的左子树不为空，则左子树上的所有节点值都小于根节点的值

2.如果它的右子树不为空，则右子树上的所有节点值都大于根节点的值

3.左、右子树都是二叉搜索树

二、二叉搜索树的实现与操作

节点结构

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

树类

template<class K, class V>
class BSTree
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key){}bool Find(const K& key){}bool Erase(const K& key){}void _InOrder(Node* root){}void InOrder(){_InOrder(root);}
private:Node* root = nullptr;
};

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.插入

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;
}

3.删除

在二叉搜索树中删除是一个稍显麻烦的事，其中包含了许多细节

我们可以知道，待删除的节点有四种情景：

1.要删除的结点无孩子结点

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

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

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

在后面的处理中1情景和23情景可以融合，因此去掉1情景，我们有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->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}else{// 替换法Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMin == rightMinParent->_left)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;return true;}}}return false;
}

4.中序遍历

既然二叉搜索树能叫做二叉排序树，自然是有原因的，在二叉搜索树中，对二叉搜索树来一次中序遍历，即可得到一组有序元素

在C++的类中，不能直接调用递归函数，需要嵌套一层递归

void InOrder()
{_InOrder(_root);cout << endl;
}
void _InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);
}

5.完整代码

template<class K>
struct BSTreeNode
{typedef BSTreeNode<K> Node;Node* _left;Node* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}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 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;}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->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}else{// 替换法Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMin == rightMinParent->_left)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;
};

三、二叉搜索树的应用（K模型、KV模型）

1.K模型

K模型中只有一个key值作为关键码，只存储key值

如我们要在一个词库中搜索一个单词 “key”，我们只需要以这个词库的每一个单词作为key值构建二叉搜索树，再在这个树中查找key值为“key”的节点

2.KV模型

KV模型中的每一个key值都有一个对应的value值（也叫映射），即<Key,Value>键值对

如我们平时学习上经常用到的英汉词典，每个英文都对应着中文，英文单词与其对应的<Word,Chinese>就构成了一种键值对

下面就是上述K模型代码改造的KV模型代码

3.完整代码

template<class K, class V>
struct BSTreeNode
{typedef BSTreeNode<K, V> Node;Node* _left;Node* _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;}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->_right){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}else{// 替换法Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMin == rightMinParent->_left)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;
};