🌈感谢阅读East-sunrise学习分享——[进阶数据结构]二叉搜索树
博主水平有限，如有差错，欢迎斧正🙏感谢有你 码字不易，若有收获，期待你的点赞关注💙我们一起进步

---

🌈我们在之前已经学习过了二叉树，而如今已经掌握C++语法的我们比起当初只能通过C语言学习已经稍有精进了
C++拥有一些C语言所不具有的优势，所以更适合我们对高阶数据结构的学习，今天要分享的二叉搜索树是二叉树的进阶类型，在做题或实际应用都有着重要地位🚀🚀🚀

一、概念

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

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

---

二、基本操作

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

2.1 查找

搜索二叉树的特性结构，使得它的查找效率十分快

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

✏️代码实现

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

2.2 插入

插入的具体过程如下：

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

由于要严格遵循二叉搜索树的结构，所以在每次遍历或最后的插入时都需要比较新增节点与其父节点的值的大小♨️所以我们可以用一个parent指针，随时记录下父节点，便于插入时的大小判断💭

✏️代码实现

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

	//插入,小于就插左，大于就插右
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		parent = cur;
		if (key < cur->_key)
			cur = cur->_left;
		else if (key > cur->_key)
			cur = cur->_right;
		else
			return false;
	}
	
	//到合适的空了，开始插入
	//要插在左还是右，还是需要比较
	cur = new Node(key);
	if (key < parent->_key)
		parent->_left = cur;
	if (key > parent->_key)
		parent->_right = cur;
	return true;
}

2.3 删除

二叉搜索树的删除较为复杂

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

1. 要删除的节点无孩子节点
2. 要删除的节点只有右孩子节点
3. 要删除的节点只有左孩子节点
4. 要删除的节点有左、右孩子节点

---

删除的情况有些许复杂，我们可以将其归成两类

1. 直接删除法
2. 替换法删除

⭕直接删除法

直接删除法适用于以上的情况1、2、3；其具体情况是删除的节点只有一个孩子或没有孩子节点
而当你删除节点后，其被删节点的孩子节点不能就任其飘荡呀，所以我们就需要对其进行“寄养”；而若删除节点没有孩子节点（左右孩子节点都为空）则删除后，被删节点的父节点所对应的孩子节点也需要指向空🔅

综上所述，根据搜索二叉树的结构可得：
在代码实现时，我们可以把情况1和情况2合为一种情况 —— 被删节点的左孩子节点为空 ——> 判断被删节点为其父节点的左or右孩子 ——> 将被删节点的右孩子与父节点链接起来（寄养）✅
情况3 —— 被删节点的右孩子节点为空 ——> 判断被删节点为其父节点的左or右孩子 ——> 将被删节点的左孩子与父节点链接起来（寄养）✅

🚩🚩直接删除法有一个bug需要留意 —— 当被删节点为根节点时，会出现空指针的问题；因此在代码实现时注意判断

⭕替换法删除

✏️代码实现

//删除
bool Erase(const K& key)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)
		{
			parent = cur;
			cur = cur->_left;
		}
		else//值相等 - 找到了
		{
			//1.左为空
			//2.右为空
			//3.左右都不为空 - 替换删除
			if (cur->_left == nullptr)
			{
				if (cur == _root) //parent == nullptr
					_root = cur->_right;
				else
				{
					if (cur == parent->_left)
						parent->_left = cur->_right;
					else
						parent->_right = cur->_right;
				}
				delete cur;
			}
			else if (cur->_right == nullptr)
			{
				if (cur == _root) //parent == nullptr
					_root = cur->_left;
				else
				{
					if (cur == parent->_left)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
				}
				delete cur;
			}
			else
			{
				//替换删除
				Node* parent = cur;
				Node* minRight = cur->_right;
				while (minRight->_left)
				{
					parent = minRight;
					minRight = minRight->_left;
				}
                
				cur->_key = minRight->_key;
                
				if (minRight == parent->_left)
					parent->_left = minRight->_right;
				else
					parent->_right = minRight->_right;
                
				delete minRight;
			}
			return true;
		}
	}
	return false;
}

---

三、递归实现

3.1 递归查找 - Find

bool _FindR(Node* root, const K& key)
{
	if (root == nullptr)
		return false;

	if (key > root->_key)
		root = root->_right;
	else if (key < root->_key)
		root = root->_left;
	else
		return true;
}

3.2 递归插入 - Insert

在实现递归插入的过程中，最后会发现插入时需要调用到父指针，但是一步一步传父指针很麻烦💭于是这里用到了一个很巧妙的方法🚩🚩

✏️代码实现

bool _InsertR(Node*& root, const K& key)
{
	if (root == nullptr)
	{
		root = new Node(key);
		return true;
	}

	if (key < root->_key)
		return _InsertR(root->_right, key);
	else if (key > root->_key)
		return _InsertR(root->_left, key);
	else
		return false;
}

3.3 递归删除 - Erase

✏️代码实现

bool _EraseR(Node*& root, const K& key)
{
	if (root == nullptr)
		return false;

	if (key < root->_key)
		return _EraseR(root->_left, key);
	else if (key > root->_key)
		return _EraseR(root->_right, key);
	else
	{
		//1.左右都为空
		//2.右为空
		//3.左右都不为空
		Node* del = root;
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		else
		{
			//替换删除
			Node* minRight = root->_right;
			while (minRight->_left)
				minRight = minRight->_left;

			swap(root->_key, minRight->_key);

			// 转换成在子树中去删除节点
			return _EraseR(root->_right, key);
		}

		delete del;
		return true;
	}
}

此递归实现有两处点睛之笔✨✨

🔅假如如图，我们要删除的是节点14，当递归走到节点10这一层时，调用函数时传的是（节点10）-> 右
也就意味着下一层函数的root是10->right的别名；那我们要删除的就是节点正是10 -> right（此时是节点14），我们再创建一个指针del将其存起来；然后直接改变其值 —— root = root -> _left 如此一来，10 -> right 就变为13了✔️最后再将del给delete掉就搞定了

---

当我们需要替换法删除时，替换了节点后，此树子树不符合搜索二叉树的结构了，但是我们能够发现，其删除节点的子树是符合的，因此要删掉节点只需要转换到子树中删除即可✔️

四、二叉搜索树的应用

4.1 K模型

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

• 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

4.2 KV模型

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

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

✏️改造二叉搜索树为KV结构

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
};

template<class K, class V>
class BSTree
{
     typedef BSTNode<K, V> Node;
     typedef Node* PNode;
public:
     BSTree(): _pRoot(nullptr){}
     PNode Find(const K& key);
     bool Insert(const K& key, const V& value)
     bool Erase(const K& key)
private:
 PNode _pRoot;
};

void TestBSTree3()
{
	// 输入单词，查找单词对应的中文翻译
	BSTree<string, string> dict;
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("left", "左边、剩余");
	dict.Insert("right", "右边");
	dict.Insert("sort", "排序");
	// 插入词库中所有单词
	string str;
	while (cin>>str)
	{
    	 BSTreeNode<string, string>* ret = dict.Find(str);
         if (ret == nullptr)
         	 cout << "单词拼写错误，词库中没有这个单词:" <<str <<endl;
     	else
             cout << str << "中文翻译:" << ret->_value << endl;
	}
}

void TestBSTree4()
{
     // 统计水果出现的次数
     string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", 
	"苹果", "香蕉", "苹果", "香蕉" };
     BSTree<string, int> countTree;
     for (const auto& str : arr)
     {
     	// 先查找水果在不在搜索树中
     	// 1、不在，说明水果第一次出现，则插入<水果, 1>
     	// 2、在，则查找到的节点中水果对应的次数++
     	//BSTreeNode<string, int>* ret = countTree.Find(str);
     	auto ret = countTree.Find(str);
     	if (ret == NULL)
         	countTree.Insert(str, 1);
        else
       		ret->_value++;
     }
countTree.InOrder();
}

五、二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：logN

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N/2

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？这就需要我们的AVL树和红黑树派上用场了（后续分享）

✏️附上二叉搜索树源码BST.h

namespace K
{
	template <class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _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 = Copy(t._root);
		}

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}

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

			//插入,小于就插左，大于就插右
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				parent = cur;
				if (key < cur->_key)
					cur = cur->_left;
				else if (key > cur->_key)
					cur = cur->_right;
				else
					return false;
			}
			//到合适的空了，开始插入
			//要插在左还是右，还是需要比较
			cur = new Node(key);
			if (key < parent->_key)
				parent->_left = cur;
			if (key > parent->_key)
				parent->_right = cur;
			return true;
		}

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

		//删除
		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else//值相等 - 找到了
				{
					//1.左为空
					//2.右为空
					//3.左右都不为空 - 替换删除
					if (cur->_left == nullptr)
					{
						if (cur == _root) //parent == nullptr
							_root = cur->_right;
						else
						{
							if (cur == parent->_left)
								parent->_left = cur->_right;
							else
								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
								parent->_right = cur->_left;
						}
						delete cur;
					}
					else
					{
						//替换删除
						Node* parent = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							parent = minRight;
							minRight = minRight->_left;
						}
						cur->_key = minRight->_key;
						if (minRight == parent->_left)
							parent->_left = minRight->_right;
						else
							parent->_right = minRight->_right;
						delete minRight;
					}
					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);
		}

		//中序遍历
		void Inorder()
		{
			_Inorder(_root);
			cout << endl;
		}
	private:
		Node* _root = nullptr;

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;

			Node* newnode = new Node(root->_key);
			newnode->_left = Copy(root->_left);
			newnode->_right = Copy(root->_right);

			return newnode;
		}

		void Destroy(Node* root)
		{
			if (root == nullptr)
				return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		void _Inorder(Node* root)
		{
			if (root == nullptr)
				return;

			_Inorder(root->_left);
			cout << root->_key << " ";
			_Inorder(root->_right);
		}

		bool _FindR(Node* root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (key > root->_key)
				root = root->_right;
			else if (key < root->_key)
				root = root->_left;
			else
				return true;
		}

		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				root = new Node(key);
				return true;
			}

			if (key < root->_key)
				return _InsertR(root->_right, key);
			else if (key > root->_key)
				return _InsertR(root->_left, key);
			else
				return false;
		}

		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
				return false;

			if (key < root->_key)
				return _EraseR(root->_left, key);
			else if (key > root->_key)
				return _EraseR(root->_right, key);
			else
			{
				Node* del = root;
				if (root->_left == nullptr)
				{
					root = root->_right;
				}
				else if (root->_right == nullptr)
				{
					root = root->_left;
				}
				else
				{
					//替换删除
					Node* minRight = root->_right;
					while (minRight->_left)
						minRight = minRight->_left;

					swap(root->_key, minRight->_key);

					// 转换成在子树中去删除节点
					return _EraseR(root->_right, key);
				}

				delete del;
				return true;
			}
		}
	};
}

六、二叉树进阶试题

1️⃣根据二叉树创建字符串

传送门

💭解题思路：此题的难点在于括号的省略，我们可以先按照不用省略括号的思路写出前序遍历，再去归纳什么时候就需要省略括号🔅

class Solution {
public:
    string tree2str(TreeNode* root) {
        //可能是空树
        if(root == nullptr)
            return string();
        //不是空树，开始前序遍历
        //首先构造一个string
        string str;
        //不是空树则先插入根
        str += to_string(root->val);

        //前序遍历 - 递归 -- 中-左-右
        //根完毕后就转换为子问题，去遍历左树，左树完毕就遍历右树

        //关于括号省略
        //1.左为空 右为空 - 省略
        //2.左为空，右不为空 - 不能省略
        //3.左不为空，右为空 - 省略

        if(root->left || root->right)
        {
            str += '(';
            str += tree2str(root->left);
            str += ')';
        }
        
        if(root->right)
        {
            str += '(';
            str += tree2str(root->right);
            str += ')';
        }        

        return str;
    }
};

2️⃣二叉树的层序遍历

传送门

💭解题思路：对于大部分层序遍历，我们都可以利用队列来辅助完成；由于先进先出，每次元素出队列时就带入其子节点，这样我们便能按层顺序入队列以及出队列了。♨️而此题的难点在于不仅要层序遍历，而且还需要将每层的元素分开；那么我们可以在队列加入一个标记变量livesize，来标识每层元素所剩元素个数和是否已经全部出完

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> sum;
        queue<TreeNode*> q;

        //有可能是空树
        if(root == nullptr)
            return sum;
        
        //非空
        q.push(root);
        int levesize = 1;
        while(!q.empty())
        {
            vector<int> ret;
            while(levesize--)
            {
                TreeNode* front = q.front();
                q.pop();

                ret.push_back(front->val);
                if(front->left)
                    q.push(front->left);e
                if(front->right)
                    q.push(front->right);
            }
            //一层遍历结束
            levesize = q.size();
            sum.push_back(ret);
        }
        return sum;
    }
};

3️⃣二叉树的最近公共祖先

传送门

✏️思路1：递归检查

💭解题思路：我们经过分析可以归纳总结以下的情况

1.若有一个根节点，并且一个在其左子树，一个在其右子树，那么此根节点即是最近公共祖先

2.若走到一个节点正是题目中的要求节点之一，而另外一个节点在其子树，则先走到的那个节点为最近公共祖先

• 此思路主要需要判断节点是否在根的左右子树中，因此变量的命名尤为重要，不然就容易乱💤

class Solution {
public:
    bool Find(TreeNode* sub, TreeNode* x)
    {
        if(sub == nullptr)
            return false;
        
        if(sub == x)
            return true;

        return Find(sub->left, x)
            || Find(sub->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr)
            return nullptr;

        //根就是
        if(root == q || root == p)
            return root;

        bool qInLeft, qInRight, pInLeft, pInRight;
        pInLeft = Find(root->left, p);
        pInRight = !pInLeft;

        qInLeft = Find(root->left, q);
        qInRight = !qInLeft;

        //1、一个在左一个在右，root就是最近公共祖先
        //2、如果都在左，就递归去左边
        //3、如果都在右，就递归去右边
        if((pInLeft && qInRight) || (qInLeft && pInRight))
        {
            return root;
        }
        else if (qInLeft && pInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }
        else if (qInRight && pInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }
        else
        {
            return nullptr;
        }
    }
};

✏️思路2：路径比较

💭解题思路：从根开始走到每个节点都有其路径，而我们可以把2个节点的路径都记录下来，然后找出那个最后一样的节点便是公共祖先

• 而对于路径的记录我们可以通过递归来记录
• 对于最后公共祖先的查找，我们可以让大的栈先pop，直到两个路径栈的元素个数相同，再相比较，如果不同则pop

class Solution {
public:
    bool Fpath(TreeNode* root,TreeNode* cur,stack<TreeNode*>& st)
    {
        if(root == nullptr)
            return false;
        
        st.push(root);
        if(root == cur)
            return true;
        
        if(Fpath(root->left,cur,st))
            return true;
        if(Fpath(root->right,cur,st))
            return true;
        
        //走到光标处说明此节点的左右子树都false
        st.pop();
        return false;
    }
    
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> ppath;
        stack<TreeNode*> qpath;
        Fpath(root,p,ppath);
        Fpath(root,q,qpath);

        //两个栈的数量不一则要统一
        //找路径相遇点
        while(ppath.size()!=qpath.size())
        {
            if(ppath.size() > qpath.size())
                ppath.pop();
            else
                qpath.pop();
        }

        while(ppath.top() != qpath.top())
        {
            ppath.pop();
            qpath.pop();
        }
        return ppath.top();
        
    }
};

🌈🌈写在最后 我们今天的学习分享之旅就到此结束了
🎈感谢能耐心地阅读到此
🎈码字不易，感谢三连
🎈关注博主，我们一起学习、一起进步