什么是二叉搜索树

二叉搜索树（Binary Search Tree），（又名：二叉查找树、二叉排序树）它或者是一棵空树。是一种特殊的二叉树，具有以下性质：

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

『数据结构』二叉搜索树-LMLPHP

二叉搜索树原理：
二叉搜索树的查找过程和二叉树类似，通常采取二叉链作为二叉搜索树的存储结构。中序遍历二叉搜索树可以可到一个关键字的有序序列；一个无需序列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无需序列进行排序的过程。每次插入的新节点都是二叉搜索树上新的叶子节点，在进行插入操作时，不必移动其他节点，只需要改动某个节点的指针，由空变为非空即可。二叉搜索树搜索、插入、删除的复杂度等于树高，O(log(n))。

二叉搜索树的操作

二叉搜索树的查找：

若根节点不为空：
如果根节点key==查找的key，返回true；
如果根节点key>查找的key，在其左子树查找；
如果根节点key<查找的key，在其右子树查找；
若根节点为空，返回false；

『数据结构』二叉搜索树-LMLPHP

二叉树的插入：
插入的过程如下：

如果树为空，则直接插入，然后返回true。
树不为空，按二叉搜索树的性质查找插入位置，插入新节点。

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

要删除的结点无孩子结点；
要删除的结点只有左孩子结点；
要删除的结点只有右孩子结点；
要删除的结点有左、右孩子结点；

看似有四种情况，第一种可以和第二种或第三种合并起来，总结如下：

只有左孩子，删除该节点且使被删除结点的双亲结点指向被删除结点的左孩子结点。
只有右孩子，删除该节点且使被删除结点的双亲结点指向被删除结点的右孩子结点。
有左右孩子，在它的右子树中寻找中序下的第一个结点（关键码最小），用它的值填补到被删除结点中，再来处理该节点的删除问题。

二叉搜索树性能分析

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

最优情况下，二叉搜索树为完全二叉树，平均比较次数为：log2(N)；
最差情况下，二叉搜索树退化为单支树，平均比较次数为：N/2；

如果退化成单支树，二叉搜索树的性能就失去了。这就是二叉搜索树的问题所在。有没有什么改进的方法呢？有，但是这里就不介绍了。可以提一下：AVL树。

模拟实现二叉搜索树

模拟实现中遇到的问题：
『数据结构』二叉搜索树-LMLPHP
二叉搜索树结点中pair<K, V> _kv;语句报错，缺少类型说明符。错误原因暂时不详。
解决方案如下：
将第3行和第4行交换一下，就可以了O(∩_∩)O哈哈~。

BinarySearchTree.h：

#pragma once

// 二叉搜索树结点
template<class K, class V>
struct BSTreeNode{

	pair<K, V> _kv;
	BSTreeNode<K, V>* _left;
	BSTreeNode<K, V>* _right;

	BSTreeNode(const pair<K, V>& kv)
		: _left(nullptr)
		, _right(nullptr)
		, _kv(kv)
	{}

};

// 二叉搜索树
template<class K, class V>
class BSTree{
	typedef BSTreeNode<K, V> Node;

public:
	BSTree()
		: _root(nullptr)
	{}

	~BSTree(){
		// 二叉搜索树的释放
		_release(_root);
	}

	// 二叉树的中序遍历
	void inorder(){
		_inorder(_root);

		cout << endl;
	}

	// 二叉搜索树的查找
	Node* find(const K& key){
		return _find(key);
	}

	// 二叉搜索树的插入
	bool insert(const pair<K, V>& kv){
		return _insert(kv);
	}

	// 二叉搜索树的删除
	bool remove(const K& key){
		return _remove(key);
	}

private:
	// 释放
	void _release(Node* root){
		// 该树非空
		if (root){
			// 保存左右孩子
			Node* left = root->_left;
			Node* right = root->_right;

			// 释放根
			delete root;

			// 左树非空，释放左树
			if (left){
				_release(left);
			}

			// 右树非空，释放右树
			if (right){
				_release(right);
			}
		}
	}

	// 中序遍历
	void _inorder(Node* root){
		// 递归出口
		if (root == nullptr){
			return;
		}

		_inorder(root->_left);
		cout << root->_kv.first << " ";
		_inorder(root->_right);
	}

	// 查找
	Node* _find(const K& key){
		Node* cur = _root;

		while (cur != nullptr){
			// 比根结点大，去右子树找
			if (key > cur->_kv.first){
				cur = cur->_right;
			}
			// 比根结点小，去左子树找
			else if (key < cur->_kv.first){
				cur = cur->_left;
			}
			// 相等
			else{
				break;
			}
		}

		return cur;
	}

	// 插入
	bool _insert(const pair<K, V>& kv){
		// 树为空
		if (_root == nullptr){
			_root = new Node(kv);

			return true;
		}
		// 树不为空
		else{
			Node* cur = _root;
			// 保存父节点
			Node* parent = nullptr;

			while (cur != nullptr){
				parent = cur;

				// 比根结点大，去右子树
				if (kv.first > cur->_kv.first){
					cur = cur->_right;
				}
				// 比根结点小，去左子树
				else if (kv.first < cur->_kv.first){
					cur = cur->_left;
				}
				// 和根结点一样，已存在，插入失败
				else{
					return false;
				}
			}

			// 新插入结点
			cur = new Node(kv);

			// 比双亲结点大，插入到右树
			if (kv.first > parent->_kv.first){
				parent->_right = cur;
			}
			// 比双亲结点小，插入到左树
			else{
				parent->_left = cur;
			}

			return true;
		}
	}

	// 删除
	bool _remove(const K& key){
		Node* cur = _root;
		// 保存父结点
		Node* parent = nullptr;

		while (cur != nullptr){
			// 比根结点大，右树找
			if (key > cur->_kv.first){
				parent = cur;
				cur = cur->_right;
			}
			// 比根结点小，左树找
			else if (key < cur->_kv.first){
				parent = cur;
				cur = cur->_left;
			}
			// 找到了
			else{
				// 该节点左树为空
				if (cur->_left == nullptr){
					// 该节点为根结点
					if (parent == nullptr){
						_root = cur->_right;
					}
					else{
						// 该节点在父结点的右树
						if (cur->_kv.first > parent->_kv.first){
							parent->_right = cur->_right;
						}
						// 该节点在父结点的左树
						else{
							parent->_left = cur->_right;
						}
					}
				}
				// 该节点右树为空
				else if (cur->_right == nullptr){
					// 该节点为根结点
					if (parent == nullptr){
						_root = cur->_left;
					}

					// 该节点在父结点的右树
					if (cur->_kv.first > parent->_kv.first){
						parent->_right = cur->_left;
					}
					// 该节点在父结点的右树
					else{
						parent->_left = cur->_right;
					}
				}
				// 该节点左右树都不为空
				else{
					// 右树中寻找替代结点
					Node* replace = cur->_right;
					// 保存替代结点的父结点
					Node* rparent = cur;

					// 寻找最左结点，即右树中的最小值
					while (replace->_left){
						rparent = replace;
						replace = replace->_left;
					}

					cur->_kv = replace->_kv;
					cur = replace;

					// 判断replace是否有左树
					// replace有左树
					if (rparent->_left == replace){
						// 将替代结点的右树连到替代结点的父结点的左树
						rparent->_left = replace->_right;
					}
					// replace没有左树
					else{
						// 将替代结点的右树连到替代结点的父结点的右树
						rparent->_right = replace->_right;
					}
				}

				// 删除替代结点
				delete cur;

				return true;
			}
		}
		return false;
	}

private:
	Node* _root;
};

sss_0916

『数据结构』二叉搜索树

什么是二叉搜索树

二叉搜索树的操作

二叉搜索树性能分析

模拟实现二叉搜索树