【数据结构】二叉搜索树的原理及其实现

认识二叉搜索树

二叉搜索树又称二叉排序树或者二叉查找树，本质上是一颗二叉树。对于二叉搜索树的任一节点，具有以下一些性质：

• 如果左子树非空，那么左子树上的值一定都小于根节点的值
• 如果右子树非空，那么右子树上的值一定都大于根节点的值
• 它的左右子树都是二叉搜索树

例如下图：

根据二叉搜索树的性质，左节点的值 < 根节点的值 < 右节点的值
我们很容易想到，对二叉搜索树进行中序遍历就可以得到一个节点值递增的序列。因此我们也将二叉搜索树称为二叉排序树。

二叉搜索树的应用其实非常广泛，像我们经常用的map，set等容器，底层其实就是一个二叉搜索树。

二叉搜索树的原理及实现

查找

1. 从根节点开始，类似于二分，比要是查找的节点值大于当前节点值，那就向当前节点的右孩子节点继续找。否则就往左孩子方向找。直到找到为止，或者走到空为止。
2. 查找的时间复杂度为树的高度，设二叉搜索树的节点数为N,那么平均查找时间就是O(logN)。当然，如果是极端情况下，即退化成一个单链表，查找的时间复杂度就是O(N)。
   

建树

• 如果当前树为空，那就把当前节点设置为树的根节点。
• 和查找过程类似，大于当前节点就往右走，小于就往左走，等于就退出（防止节点冗余）。直到直到一个空位置插上，往后的插入操作也是一样。
• 建树的时间复杂度与查找的时间复杂度有关，一般情况下建树的时间复杂度是NlogN。极端情况就是N^2,这种时候，二叉树就退化成了一个单链表。

二叉搜索树的性能分析

无论是插入操作还是查找操作的时间复杂度都取决于查找的时间效率，也就意味着，查找的效率极大程度上体现一颗二叉搜索树的性能。

等于有n个节点的二叉搜索树

• 最优情况：二叉搜索树是完全二叉树或者是接近完全二叉树（左右子树的节点数量相差不大），其平均比较时间是logN。
• 最坏情况：退化成类似一个单链表，平均比较次数为N^2。

根据以上分析得出结论，树的高度越低意味着整棵树越像完全二叉树，查找的效率也就越高。越高意味着越像单支树，查找的效率也就越低。为了保持二叉搜索树的性能，也就衍生出了AVL树和红黑树。

二叉搜索树的key模型实现

代码：

namespace k {

	template<class T>
	class BSTNode {
	public:
		BSTNode()
			:_val(0)
		{
			left = nullptr;
			right = nullptr;
		}

		BSTNode(T val)
			:_val(val)
		{
			left = nullptr;
			right = nullptr;
		}
		T _val;
		BSTNode<T>* left;
		BSTNode<T>* right;
	};


	template<class T>
	class BSTree {

		typedef BSTNode<T> Node;
		typedef Node* pNode;
	public:
		BSTree()
			:_root(nullptr)
		{

		}

		//删除
		bool Erase(const T& val) {
			if (_root == nullptr)return false;
			if (!Find(val))return false;
			pNode cur = _root;
			pNode pa = _root;
			while (cur) {
				if (cur->_val < val) {
					pa = cur;
					cur = cur->right;
				}
				else if (cur->_val > val) {
					pa = cur;
					cur = cur->left;
				}
				else break;
			}

			//被删除的节点孩子有空
			if (cur->left == nullptr) {
				if (cur == _root) {//如果被删除的节点是头节点
					pNode t = _root;
					_root = cur->right;
					delete t;
				}
				else if (pa->_val < cur->_val) {
					pa->right = cur->right;
					delete cur;
				}
				else {
					pa->left = cur->right;
					delete cur;
				}

			}
			else if (cur->right == nullptr) {
				if (cur == _root) {//如果被删除的节点是头节点
					pNode t = _root;
					_root = cur->left;
					delete t;
				}
				else if (pa->_val < cur->_val) {
					pa->right = cur->left;
					delete cur;
				}
				else {
					pa->left = cur->left;
					delete cur;
				}

			}//cur的两个孩子节点都不为空
			else {
				pNode ffa = cur;
				pNode minright = cur->right;
				while (minright->left) {
					ffa = minright;
					minright = minright->left;
				}

				ffa->left = minright->right;
				std::swap(minright->_val, cur->_val);
				delete minright;
			}


		}


		//查找
		bool Find(const T& val) {
			assert(_root != nullptr);
			pNode cur = _root;
			while (cur) {
				if (cur->_val < val) {
					cur = cur->right;
				}
				else if (cur->_val > val) {
					cur = cur->left;
				}
				else return true;

			}
			return false;
		}

		//插入
		bool Insert(const T& val) {
			if (_root == nullptr) {
				_root = new Node(val);
				return true;
			}

			pNode cur = _root;
			pNode pa = nullptr;
			while (cur) {
				if (cur->_val < val) {
					pa = cur;
					cur = cur->right;
				}
				else if (cur->_val > val) {
					pa = cur;
					cur = cur->left;
				}
				else return false;//已经存在无需插入

			}
			if (pa->_val > val) {
				pa->left = new Node(val);
			}
			else {
				pa->right = new Node(val);
			}
			return true;
		}
		//遍历
		void InOrder() {
			_InOrder(_root);
			std::cout << std::endl;
		}
	private:
		void _InOrder(pNode root) {
			if (root == nullptr)return;
			_InOrder(root->left);
			std::cout << root->_val << " ";
			_InOrder(root->right);
		}
		pNode _root;
	};
}

二叉搜索树的key-value模型实现

代码：

namespace k_val {

	template<class K,class V>
	class BSTNode {
	public:
		BSTNode()
			:_key(0)
			,_val(0)
		{
			left = nullptr;
			right = nullptr;
		}

		BSTNode(const K& key,const V& val)
			:_key(key)
			,_val(val)
		{
			left = nullptr;
			right = nullptr;
		}
		K _key;
		V _val;
		BSTNode<K,V>* left;
		BSTNode<K,V>* right;
	};


	template<class K,class V>
	class BSTree {

		typedef BSTNode<K,V> Node;
		typedef Node* pNode;
	public:
		BSTree()
			:_root(nullptr)
		{

		}

		//删除
		bool Erase(const K& key) {
			if (_root == nullptr)return false;
			if (!Find(key))return false;
			pNode cur = _root;
			pNode pa = _root;
			while (cur) {
				if (cur->_key < key) {
					pa = cur;
					cur = cur->right;
				}
				else if (cur->_key > key) {
					pa = cur;
					cur = cur->left;
				}
				else break;
			}

			//被删除的节点孩子有空
			if (cur->left == nullptr) {
				if (cur == _root) {//如果被删除的节点是头节点
					pNode t = _root;
					_root = cur->right;
					delete t;
				}
				else if (pa->_key < cur->_key) {
					pa->right = cur->right;
					delete cur;
				}
				else {
					pa->left = cur->right;
					delete cur;
				}

			}
			else if (cur->right == nullptr) {
				if (cur == _root) {//如果被删除的节点是头节点
					pNode t = _root;
					_root = cur->left;
					delete t;
				}
				else if (pa->_key < cur->_key) {
					pa->right = cur->left;
					delete cur;
				}
				else {
					pa->left = cur->left;
					delete cur;
				}

			}//cur的两个孩子节点都不为空
			else {
				pNode ffa = cur;
				pNode minright = cur->right;
				while (minright->left) {
					ffa = minright;
					minright = minright->left;
				}

				ffa->left = minright->right;
				std::swap(minright->_key, cur->_key);
				delete minright;
			}


		}


		//查找
		pNode Find(const K& key) {
			assert(_root != nullptr);
			pNode 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& val) {
			if (_root == nullptr) {
				_root = new Node(key,val);
				return true;
			}

			pNode cur = _root;
			pNode pa = nullptr;
			while (cur) {
				if (cur->_key < key) {
					pa = cur;
					cur = cur->right;
				}
				else if (cur->_key > key) {
					pa = cur;
					cur = cur->left;
				}
				else return false;//已经存在无需插入

			}
			if (pa->_key > key) {
				pa->left = new Node(key,val);
			}
			else {
				pa->right = new Node(key,val);
			}
			return true;
		}
		//遍历
		void InOrder() {
			_InOrder(_root);
			std::cout << std::endl;
		}
	private:
		void _InOrder(pNode root) {
			if (root == nullptr)return;
			_InOrder(root->left);
			std::cout << root->_val << " ";
			_InOrder(root->right);
		}
		pNode _root;
	};
}