二叉搜索树

1.二叉搜索树

1.1.二叉搜索树概念

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

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

1.2.二叉搜索树操作

1. 二叉搜索树的查找

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

2. 二叉搜索树的插入

树为空，则直接增加节点，赋值给root指针，树不为空，按二叉搜索树性质查找插入位置，插入新节点。

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

• 要删除的节点无孩子节点
• 要删除的节点只有左孩子节点
• 要删除的节点只有右孩子节点
• 要删除的节点有左右孩子节点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正删除过程如下:

• 情况b:删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点-直接删除。
• 情况c:删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点-直接删除。
• 情况d:在它的右子树中寻找中序下第一个节点(关键码最小),用它的值填补到被删除节点中，再来处理该节点的删除问题–替换法删除。
  

1.3.二叉搜索树的模拟实现

template <class K>
struct BSTreeNode
{struct BSTreeNode* left;struct BSTreeNode* right;K key;BSTreeNode(const K& key):key(key),left(nullptr),right(nullptr){}
};template <class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& t){_root = Copyt(t._root);}BSTree<K>& operator=(BSTree 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* parent = _root;Node* cur = _root;while (cur != nullptr){if (cur->key < key){parent = cur;cur = cur->right;}else if (cur->key > key){parent = cur;cur = cur->left;}elsereturn false;}if (parent->key < key){parent->right =  new Node(key);}else{parent->left = new Node(key);}return true;}void InOrder(){_InOrder(_root);cout << endl;}bool Find(const K& key){if (_root == nullptr)return false;Node* cur = _root;while (cur != nullptr){if (cur->key < key){cur = cur->right;}else if (cur->key < key){cur = cur->left;}elsereturn true;}return false;}bool Erase(const K& key){Node* parent = _root;Node* cur = _root;while (cur != nullptr){if (cur->key > key){parent = cur;cur = cur->left;}else if (cur->key < key){parent = cur;cur = cur->right;}else{Node* del = cur;//到这里，成功的找到这个元素,删除的情况分三种//1.左为空if (cur->left == nullptr){if (cur == _root){_root = cur->right;}else{if (parent->right == cur){parent->right = cur->right;}else{parent->left = cur->right;}}}//2.右为空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;}}}//3.左右都不为空，用的是替换法，左边最大，右边最小(这里用右最小)else{Node* minRight = cur->right;//minRight就是右最大while (minRight->left != nullptr){parent = minRight;minRight = minRight->left;}swap(cur->key, minRight->key);if (parent->left == minRight){parent->left = minRight->right;}else{parent->right = minRight->right;}cur = minRight;}delete cur;return true;}}return false;}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;}Node* Copyt(const Node* root){if (root == nullptr){return nullptr;}Node* parent = new Node(root->key);parent->left = Copyt(root->left);parent->right = Copyt(root->right);return parent;}void _InOrder(Node* _root){if (_root == nullptr)return;_InOrder(_root->left);cout << _root->key << " ";_InOrder(_root->right);}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{//三种情况//1.左为空Node* del = root;if (root->left == nullptr){root = root->right;}//2.右为空else if (root->right == nullptr){root = root->left;}//3.左右都不为空else{Node* minRight = root->right;while (minRight->left != nullptr){minRight = minRight->left;}swap(root->key, minRight->key);return _EraseR(root->right, key);}delete del;return true;}}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 _InsertR(Node* &root,const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->key < key){_InsertR(root->right, key);}else if (root->key > key){_InsertR(root->left, key);}else{return false;}return false;}//bool _InsertR(Node* root, const K& key)//{//	if (_root == nullptr)//	{//		_root = new Node(key);//		return true;//	}//	if (root->key < key) {//		if (root->right == nullptr)//		{//			root->right = new Node(key);//			return true;//		}//		_InsertR(root->right, key);//	}//	else if (root->key > key) {//		if (root->left == nullptr)//		{//			root->left = new Node(key);//			return true;//		}//		_InsertR(root->left, key);//	}//	else//		return false;//	return true;//}protected:Node* _root = nullptr;
};

2.二叉搜索树的应用

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

比如：给一个单词Word，判断该单词是否拼写正确。
在二叉搜索树中检查该单词是否存在，存在则拼写正确，不存在则拼写错误。

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

• 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<Word，Chinese>就构成一种键值对；
• 再比如统计单调次数，统计成功后，给定单词就可快速找到出现的次数，单词与其出现次数就是<word,count>就构成一种键值对。

namespace KV
{template <class K,class V>struct BSTreeNode{struct BSTreeNode* left;struct BSTreeNode* right;K key;V value;BSTreeNode(const K& key,const V& value):key(key),value(value), left(nullptr), right(nullptr){}};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 = _root;Node* cur = _root;while (cur != nullptr){if (cur->key < key){parent = cur;cur = cur->right;}else if (cur->key > key){parent = cur;cur = cur->left;}elsereturn false;}if (parent->key < key){parent->right = new Node(key,value);}else{parent->left = new Node(key,value);}return true;}Node* Find(const K& key){Node* cur = _root;while (cur != nullptr){if (cur->key < key){cur = cur->right;}else if (cur->key > key){cur = cur->left;}elsereturn cur;}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* _root){if (_root == nullptr)return;_InOrder(_root->left);cout << _root->key << ":"<<_root->value;_InOrder(_root->right);}protected:Node* _root = nullptr;};
}void Test4()
{KV::BSTree<string, int> b;string arr[] = { "苹果","苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };for (auto& e : arr){auto ret = b.Find(e);if (ret){ret->value++;}else{b.Insert(e, 1);}}b.InOrder();
}int main()
{Test4();
}

3.二叉搜索树的性能分析

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

最优情况下:二叉搜索树为完全二叉树（或者接近完全二叉树），其平均比较次数$lo{g}_{2}N$
最差情况下，二叉搜索树退化为单支树，其平均比较次数为:$\frac{N}{2}$