二叉树进阶（二叉搜索树）

• 二叉搜索树
• • 二叉搜索树的概念及其图解
  • 搜索树操作
  • • 查找
    • 插入
    • 删除
  • 性能分析
• 二叉搜索树的应用
• • 和二叉搜索树的小区别

二叉搜索树

二叉搜索树的概念及其图解

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

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

其所有的节点通过中序遍历打印出来就是有序的序列。

搜索树操作

首先搜索树是一个特殊的树我们得先定义它的结构
并对其进行构造初始化

template<class K>
struct BSTreeNode
{
	K _key;
	BSTreeNode* _left;
	BSTreeNode* _right;

	BSTreeNode(K& key)
		:key(_key), _left(nullptr), right(nullptr)
	{}
};

查找

其中的查找较为简单因为搜索树有序的直接进行key值的判断就行。

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

插入

这里我们先传入插入的key值通过模板去推到类型。
如果进来树就为空树，我们就需要将当前插入的节点
当我们不是就需要通过不断地判断大小直到找到当前所对应的位置对其进行插入

bool Insert(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->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return false;
		}
		Node* newnode = new Node(key);
		if (parent->_key>key)
		{
			parent->_left = newnode;
		}
		else if (parent->_key < key)
		{
			parent->_right = newnode;
		}
		return true;
	}

删除

这里删除是最重要的，也是最常考的。
情况A：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
情况B：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
情况C：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中， 再来处理该结点的删除问题

先找到对应删除的节点并保存上一结点的位置，然后通过删除节点或者替代节点让上一结点指向删除节点的叶子，或者删除掉替代后的节点。

bool Erase(K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		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 (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else if (cur == parent->_right)
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else if (cur == parent->left)
					{
						parent->_left = cur->_left;
					}
					else if (cur == parent->_right)
					{
						parent->_right = cur->_left;
					}
				}
				else
				{
					Node* newparent = cur;
					Node* submin = cur->_right;
					while (submin->_left)
					{
						newparent = submin;
						submin = submin->_left;
					}
					cur->_key = submin->_left;
					if (submin == newparent->_left)
					{
						newparent->_left = submin->_right;
					}
					else if (submin == newparent->_right)
					{
						newparent - _right = submin->_right;
					}
					delete submin；
				}
				return true;
			}
		}
		return false;
	}

性能分析

二叉搜索树的应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生 活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定 单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

和二叉搜索树的小区别

这里和之前不一样的就是对每一个KEY值进行了value的绑定。
当我们去查找key的时候也就相当于查找到了与值对应的value

template<class K, class V> 
struct BSTNode 
 { 
BSTNode(const K& key = K(), const V& value = V()) 
        : _pLeft(nullptr) , _pRight(nullptr), _key(key), _Value(value)     {} 
BSTNode<T>* _pLeft; 
BSTNode<T>* _pRight; 
K _key; 
V _value 
 };

这里就需要对构造函数进行一些修改，添加入value值。

在插入的时候也需要传入key和value，当然搜索树中也是通过key来排而不是value，只是通过绑定，可以进行查找或删除