二叉搜索树

概念

什么是二叉搜索树，二叉搜索树就是指左孩子永远比根小右孩子永远比根大。这个规则适用于所有的子树。

上面的就是一棵二叉搜索树，我们还可以发现这棵树走一个中序遍历序列是有序的，所以它又被称为二叉排序树。

二叉搜索树的操作

二叉搜索树的操作主要分为以下几点，查找， 插入，删除。

查找

算法思想：二叉搜索树的查找算法是这样的，从根的地方开始找，如果要找的key比根大就到右子树去找，如果比根小就到左子树找。时间复杂度最差为O(N)最优为O(logn)，如果一棵树走完了还没有找到说明这个数字不在这棵树内。
O(N)时间复杂度是下面这棵树的查找产生的。

我们要使树的高度保持为logN就必须引入平衡二叉搜索树的概念，这个部分我们在后面的AVL和红黑树部分讲解。
非递归算法：

	bool Find(const K& key){Node* cur = _root;while (cur != nullptr){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;}

递归算法：
key小于就递归找左树，大于就递归找右树

	bool _FindR(Node* root, const K& key){if (root == nullptr){return false;}if (root->_key < key){_FindR(root->_right, key);}else if (root->_key > key){_FindR(root->_left, key);}else{return true;}}

插入

插入分为两种情况：
1、如果树为空，则直接新增节点，赋值给_root指针。
2、树不为空，按二叉搜索树性质查找插入位置，插入新节点。

非递归算法

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

递归算法

		bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){return _InsertR(root->_left, key);}else if (root->_key < key){return _InsertR(root->_right, key);}else{return false;}}

删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点可能分下面四种情况：
a.要删除的节点无孩子节点
b.要删除的节点只有左孩子节点
c.要删除的节点只有右孩子节点
d.要删除的节点有左右孩子节点
情况b，c可以合成一个情况，那就是只有一个孩子节点。
情况b：删除该节点且是被删除节点的双亲节点指向被删除节点的左孩子节点—直接删除

情况c：删除该节点且是被删除节点的双亲节点指向被删除节点的右孩子节点—直接删除

情况d：在它的左子树中寻找最大节点，用它的值填补到被删除节点中，再来处理该节点的删除问题—替换法删除。

非递归算法：

bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//左边为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}else{//左右都不为空//找到左树中的最大值为替代节点Node* parent = cur;Node* leftmax = _root->_left;while (leftmax->_right != nullptr){parent = leftmax;leftmax = leftmax->_right;}swap(cur->_key, leftmax->_key);if (parent->_left == leftmax){parent->_left = leftmax->_left;}else{parent->_right = leftmax->_left;}cur = leftmax;}delete cur;return true;}}return false;}

非递归算法：

//Node*& 引用是关键，没有引用就不会链接起来，不用引用也可以用二级指针。
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;//1、左为空//2、右为空//3、左右都不为空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_left){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}}

完整代码

namespace name
{template<class K>struct BSTreeNode{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template <class K>class BSTree{typedef BSTreeNode<K> Node;public://构造函数BSTree():_root(nullptr){}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;}else{parent->_left = cur;}return true;}bool Find(const K& key){Node* cur = _root;while (cur != nullptr){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return true;}}return false;}bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//左边为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right == cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}else{//左右都不为空//找到左树中的最大值为替代节点Node* parent = cur;Node* leftmax = _root->_left;while (leftmax->_right != nullptr){parent = leftmax;leftmax = leftmax->_right;}swap(cur->_key, leftmax->_key);if (parent->_left == leftmax){parent->_left = leftmax->_left;}else{parent->_right = leftmax->_left;}cur = leftmax;}delete cur;return true;}}return false;}void Inorder(){_Inorder(_root);cout << endl;}bool FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}private: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;}bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){return _InsertR(root->_left, key);}else if (root->_key < key){return _InsertR(root->_right, key);}else{return false;}}bool _FindR(Node* root, const K& key){if (root == nullptr){return false;}if (root->_key < key){_FindR(root->_right, key);}else if (root->_key > key){_FindR(root->_left, key);}else{return 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;//1、左为空//2、右为空//3、左右都不为空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_left){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}}void _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}Node* _root;};
}

二叉搜索树的应用

应用主要是分为了K模型和KV模型，后面的set为K模型，map为KV模型，具体是这样的：

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到 的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
   在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见： 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文<word,chinese>就构成一种键值对； 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word,count>就构成一种键值对。
   上面的代码时K模型的，下面的代码时KV模型的。

namespace name1
{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://构造函数BSTree():_root(nullptr){}BSTree(const BSTree<K,V>& t){_root = Copy(t._root);}BSTree<K,V>& operator=(BSTree<K,V> t){swap(_root, t._root);return *this;}~BSTree(){Destory(_root);}void Inorder(){_Inorder(_root);cout << endl;}Node* FindR(const K& key){return _FindR(_root,key);}bool InsertR(const K& key,const V& value){return _InsertR(_root, key,value);}bool EraseR(const K& key){return _EraseR(_root, key);}private: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;}bool _InsertR(Node*& root,const K& key,const V& value){if (root == nullptr){root = new Node(key,value);return true;}if (root->_key > key){return _InsertR(root->_left, key, value);}else if (root->_key < key){return _InsertR(root->_right, key, value);}else{return false;}}Node* _FindR(Node* root, const K& key){if (root == nullptr){return nullptr;}if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}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;//1、左为空//2、右为空//3、左右都不为空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* leftMax = root->_left;while (leftMax->_left){leftMax = leftMax->_right;}swap(root->_key, leftMax->_key);return _EraseR(root->_left, key);}delete del;return true;}}void _Inorder(Node* root){if (root==nullptr){return;}_Inorder(root->_left);cout << root->_key << ":" << root->_value << endl;_Inorder(root->_right);}Node* _root;};
}

KV模型的测试：

void Test_BSTree7()
{string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };name1::BSTree<string, int> countTree;for (auto& str : arr){//没有找到证明是第一次出现auto ret = countTree.FindR(str);if (ret == nullptr){countTree.InsertR(str, 1);}else{ret->_value++;}}countTree.Inorder();
}
int main()
{//Test_BSTree();//Test_BSTree1();//Test_BSTree2();//Test_BSTree3();//Test_BSTree4();//Test_BSTree5();//Test_BSTree6();Test_BSTree7();return 0;
}

好的我们下一篇再见！