【C++】二叉搜索树

这是一篇万子以上的博客，本文更准确的说可以算上二叉树的进阶，详细讲解的二叉搜索树的插入，删除，查找，以及递归查找，递归删除，递归查找和构造，析构，拷贝构造，以及赋值重载，详细讲解什么是K模型，什么是KV模型，以及二叉搜索树应用场景，以及二叉搜索树性能分析

LuckyRich1

1376人浏览 · 2023-11-22 10:10:21

LuckyRich1 · 2023-11-22 10:10:21 发布

在这里插入图片描述

喜欢的点赞，收藏，关注一下把！

1.二叉搜索树概念

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

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

注意二查搜索树是一个单值树。 如下图：
在这里插入图片描述

2.二叉搜索的实现

2.1结点

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

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

2.1基本框架

template<class T>
class BSTree
{
	typedef BSTreeNode<K> Node;

public:
	//构造等。。

	bool Insert(const K& key)
	{}

	bool Erase(const K& key)
	{}

	bool Find(const K& key)
	{}

private:
	//先不写构造
	Node* _root=nullptr;
};

二叉搜索树，没有提供改的成员函数。更准确来说二叉搜索树K模型不能去任意修改key值，可能会破坏二叉搜索树的结构。KV模型可以修改值这个我们下面说。

2.2插入

二叉搜索树的插入不像是普通二叉树插入那样，插入结点之后还需要保持二叉搜索树的形状。因此我们需要先找到要插入结点的位置，然后再插入。

bool Insert(const K& key)
{
	//树为空
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
	
	//寻址
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)
			cur = cur->_right;
		else if (cur->_key > key)
			cur = cur->_left;
		else //相等
			return false;
	}
	//插入
	cur = new Node(key);
	return true;
}

我这样插入，有没有什么问题？
在这里插入图片描述
我们需要一个parent的指针，指向它的父亲结点，然后把9插入到父亲结点指针里，这样才能真正插入到树里。

但是这样写需要注意的是需要知道是插入父亲的左指针，还是右指针。

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

}

2.3查找

bool Find(const K& key)
	{
		if (_root == nullptr)
			return false;

		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.4删除

删除是二叉搜索树中最难的，情况很多，都需要考虑到。
在这里插入图片描述

删7（叶子结点），可以直接删除，但是直接删除7，父亲结点右指针就野指针了。因此我们需要把父亲结点指针置为空。指向7左孩子还是右孩子都可以。
删14（只有一个左孩子，右为空），需要找到14的父亲结点，然后让父亲结点右指针指向14的左孩子结点。
那还有一种情况肯定是只有一个右孩子，左为空，让父亲指针指向这个右孩子。

其实上面三种情况，可以总结成两种情况。

1. 左孩子为空
2. 右孩子为空

叶子结点，让父亲指向左孩子右孩子都可以。

左为空，父亲指针指向右孩子，右为空，父亲指针指向左孩子。

bool Erase(const K& key)
	{
		if (_root == nullptr)
			return false;

		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.左为空
				if (cur->_left == nullptr)
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					else if (parent->_right == cur)
					{
						parent->_right = cur->_right;
					}
					delete cur;
				}
				//2.右为空
				else if (cur->_right == nullptr)
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
					}
					else if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
					delete cur;
				}
				//3.左右都不为空
				else
				{

				}
				return true;
			}
			
		}
		return false;	
	}

先看前左为空，和右为空两种情况，请问有没有上面bug？
如果要被删除的是根节点呢？当前代码行不行？
在这里插入图片描述
是不是要报野指针的错误，根本没有parent指针。
那该如何解决呢？
是不是让根结点往下走一步就行了。

	bool Erase(const K& key)
	{
		if (_root == nullptr)
			return false;

		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.左为空
				if (cur->_left == nullptr)
				{
					//被删结点是根结点
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
					}
					
					delete cur;
				}
				//2.右为空
				else if (cur->_right == nullptr)
				{
					//被删结点是根结点
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
					}				
					delete cur;
				}
				//3.左右都不为空
				else
				{

				}
				return true;
			}
			
		}
		return false;	
	}

3.左右都不为空
在这里插入图片描述
删3，左右都不为空，具体做法如下：
方法1：找左子树最大结点替换删除

将左边最大孩子1，赋值给3，把删3转换成删1。
方法2：找右子树最小结点替换删除

左边最大----->左孩子最右结点
右边左小----->右孩子最左结点

//3.左右都不为空
else
{
	//1.右孩子最小
	Node* Minright = cur->_right;
	Node* parent = nullptr;
	while (Minright->_left)
	{
		parent = Minright;
		Minright = Minright->_left;
	}
	parent->_left = Minright->_right;
	delete Minright;

}

上面代码有没有上面问题？
在这里插入图片描述
对于删除3没有问题。那删除8呢？

10就是右边最小结点，不需要再往下找了。

循环进不去，parent又会带来野指针得问题。该怎么解决？

所以parent初始值不能置为空，设置为cur最好，并且parent的指针也不能那样随意指向，需要判断，Minright是parent的左孩子还是右孩子。

//3.左右都不为空
else
{
	//1.右孩子最小
	Node* Minright = cur->_right;
	Node* parent = cur;
	while (Minright->_left)
	{
		parent = Minright;
		Minright = Minright->_left;
	}
	cur->_key=Minright->_key;
	if (parent->_left == Minright)
	{
		parent->_left = Minright->_right;
	}
	else
	{
		parent->_right == Minright->_right;
	}
	delete Minright;
}

完整代码

bool Erase(const K& key)
{
	if (_root == nullptr)
		return false;

	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.左为空
			if (cur->_left == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					else if (parent->_right == cur)
					{
						parent->_right = cur->_right;
					}
				}
				
				delete cur;
			}
			//2.右为空
			else if (cur->_right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
					}
					else if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
				}				
				delete cur;
			}
			//3.左右都不为空
			else
			{
				//1.右孩子最小
				Node* Minright = cur->_right;
				Node* parent = cur;
				while (Minright->_left)
				{
					parent = Minright;
					Minright = Minright->_left;
				}
				cur->_key=Minright->_key;
				if (parent->_left == Minright)
				{
					parent->_left = Minright->_right;
				}
				else
				{
					parent->_right = Minright->_right;
				}
				delete Minright;

			}
			return true;
		}
		
	}
	return false;	
}

如果想替换成左孩子最大，代码完全类似。

//3.左右都不为空
else
{
	//2.左孩子最大
	Node* Maxleft = cur->_left;
	Node* parent = cur;
	while (Maxleft->_right)
	{
		parent = Maxleft;
		Maxleft = Maxleft->_right;
	}
	cur->_key = Maxleft->_key;
	if (parent->_left == Maxleft)
	{
		parent->_left = Maxleft->_left;
	}
	else
	{
		parent->_right = Maxleft->_left;
	}
	delete Maxleft;
}

2.5打印

二叉搜索树中序是一个递增序列。
中序遍历代码很简单。但是注意我们这是在类里面的中序遍历。

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

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

在这里插入图片描述

中序需要把_root传就去，但是_root是一个私有成员变量不能访问。
在类里面写递归函数都会遇到这样的问题。
1.写一个Getroot的函数
2.套一层，写个子函数

	void InOrder()
	{
		_InOrder(_root);
		cout<<endl;
	}

private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

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

3.二叉搜索树递归实现

递归代码量少，但是理解起来比较困难。一般建议有循环先写循环，然后再考虑写递归。

对于二叉树的递归，我们要有分治的思想，先处理根结点这棵树，然后再左子树右子树，因为左子树和右子树的处理方法和根结点这个树是一样的。

其实二叉搜索树的递归都是一个思想，空要怎么处理，比根大递归往右，比根小递归往左。

3.1查找

	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

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

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

3.2插入

如果为空就申请结点插入，比根大往右，比根小往左，和根相等插入失败。

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

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

这个代码还不完整，有问题。
假如插入为空的时候，插入8，再插入3。
在这里插入图片描述

插入3的时候，根本没有插上。
这里只修改一处地方就成了。

//给指针加个别名
bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

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

在这里插入图片描述

root虽然指向你，但是同时又是父亲的左指针或右指针的别名

在这里插入图片描述

3.3删除

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 _Erase(root->_left, key);
		}
		else
		{
			//1.左为空
			//2.右为空
			//3.左右都为空
			if (root->_left == nullptr)
			{

			}
			else if (root->_right == nullptr)
			{

			}
			else
			{

			}
			return true;
		}
	}

在这里插入图片描述

这里还需要再去申请一个parent吗？还需要知道7是父亲的左孩子还是右孩子吗？

显然是不用的，刚才说过，root虽然指向你，但是同时又是父亲的左指针或右指针的别名

root是父亲(6)的右指针的别名。这里就已经知道7是父亲的右指针了。并且也不用担心父亲为空的情况。

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.左为空
		//2.右为空
		//3.左右都为空
		Node* cur = root;//注意不能直接删除root，因为下面root已经改变了，所以必须保存要被删除的结点
		if (root->_left == nullptr)
		{
			root = root->_right;
		}
		else if (root->_right == nullptr)
		{
			root = root->_left;
		}
		else
		{

		}
		delete cur;
		return true;
	}
}

左右都不为空，可以向非递归那样删除。也可以交换删除。
在这里插入图片描述

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.左为空
		//2.右为空
		//3.左右都为空
		Node* cur = 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 cur;
		return true;
	}
}

非递归删除

在这里插入图片描述

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.左为空
			//2.右为空
			//3.左右都为空
			Node* cur = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* Minright = root->_right;
				Node* parent = root;
				while (Minright->_left)
				{
					parent = Minright;
					Minright = Minright->_left;
				}
				root->_key = Minright->_key;
				if (Minright == parent->_left)
				{
					parent->_left = Minright->_right;
				}
				else
				{
					parent->_right = Minright->_right;
				}
				delete Minright;
				return true;
			}
			delete cur;
			return true;
		}
	}

4.二叉搜索树默认成员函数

4.1构造

//构造
BSTree()
	:_root(nullptr)
{}

4.2析构

删除二叉树一般采用后序递归删除。

~BSTree()
{
	Delete(_root);
}
	
private:
	void Delete(Node* root)
	{
		if (root == nullptr)
			return;

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

4.3拷贝构造

构建一个二叉树一般建议前序递归创建

BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}

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

4.4赋值重载

传统写法

BSTree<K>& operator=(const BSTree<K>& t)
{
	if (this != &t)
	{
		Delete(_root);
		_root = Copy(t._root);
	}
	return *this;
}

现代写法，复用拷贝构造函数

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

6.二叉搜索树的应用

6.1K模型

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

K模型不允许插入相同的key值，也不允许修改key，否则可能破坏K模型的结构。

假设让写一段程序，用来检测英语作家，写作内容是否拼写错误。
这时可以采用K模型。

把词库中的单词作为Key，构建一颗搜索二叉树
在二叉搜索树中检索每个单词是否在这个树中，不再就报错。

Key的搜索模型------>判断在不在？

6.2KV模型

KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。

通过Key查找或修改Value。 K模型不允许修改，KV模型允许修改。

KV模型就是增加了一个V类型。Find成员函数的返回值需要修改一下。

template<class K,class V>
	struct BSTreeNode
	{
		BSTreeNode<K,V>* _left;
		BSTreeNode<K,V>* _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:
	//构造
	BSTree()
		:_root(nullptr)
	{}

	BSTree(const BSTree<K,V>& t)
	{
		_root = Copy(t._root);
	}


	//现代写法
	BSTree<K,V>& operator=(BSTree<K,V> t)
	{
		swap(_root, t._root);
		return *this;
	}


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


	bool Insert(const K& key,const V& value)
	{
		if (_root == nullptr)
		{
			_root = new Node(key,value);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			//往下走之前，记录一下父亲
			parent = cur;
			if (cur->_key < key)
				cur = cur->_right;
			else if (cur->_key > key)
				cur = cur->_left;
			else
				return false;
		}
		cur = new Node(key,value);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;

	}

	bool Erase(const K& key)
	{
		if (_root == nullptr)
			return false;

		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.左为空
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
					}

					delete cur;
				}
				//2.右为空
				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				//3.左右都不为空
				else
				{
					//1.右孩子最小
					/*Node* Minright = cur->_right;
					Node* parent = cur;
					while (Minright->_left)
					{
						parent = Minright;
						Minright = Minright->_left;
					}
					if (parent->_left == Minright)
					{
						parent->_left = Minright->_right;
					}
					else
					{
						parent->_right = Minright->_right;
					}
					delete Minright;*/
					//2.左孩子最大
					Node* Maxleft = cur->_left;
					Node* parent = cur;
					while (Maxleft->_right)
					{
						parent = Maxleft;
						Maxleft = Maxleft->_right;
					}
					cur->_key = Maxleft->_key;
					if (parent->_left == Maxleft)
					{
						parent->_left = Maxleft->_left;
					}
					else
					{
						parent->_right = Maxleft->_left;
					}
					delete Maxleft;

				}
				return true;
			}

		}
		return false;

	}

	Node* Find(const K& key)
	{
		if (_root == nullptr)
			return nullptr;

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


	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:

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

		Node* newnode = new Node(root->_key,root->_value);
		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);
		return newnode;
	}

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

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


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

		_InOrder(root->_left);
		cout << root->_key << ":" << root->_value << endl;
		_InOrder(root->_right);
	}

private:

	Node* _root;
};

假设，实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文。
我们可以采用KV模型实现。

void TestBSTree4()
{
	KV::BSTree<string ,string> kv;
	kv.Insert("sort", "排序");
	kv.Insert("search", "搜索");
	kv.Insert("left", "左边");
	kv.Insert("right", "右边");
	string str;
	while (cin >> str)
	{
		auto* ptr = kv.Find(str);
		if (ptr)
		{
			cout << ptr->_key << ":" << ptr->_value << endl;
		}
		else
		{
			cout << "无此单词" << endl;
		}
	}
}

统计每样水果出现的次数

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

KV搜索模型------>通过一个值去查找或者修改另一个值。

那以后想用二叉搜索树难道要手撕一个出来吗？K
其实后面学的map对应KV模型，set对应K模型，不用担心。

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

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

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

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

在这里插入图片描述
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： $log_2 N$

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

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

鲲鹏社区

鲲鹏展翅立根铸魂深耕行业数字化

更多推荐

香橙派kunpeng pro测评

https://www.bilibili.com/video/BV1jz421a77T/?spm_id_from=333.999.0.0

鲲鹏社区

OrangePi Kunpeng Pro 安装 ROS2 + Gazebo

目录1. 初识1.1 到手开箱1.2 OrangePi Kunpeng Pro1.2 上电2. 安装Ubuntu2.1 准备工作2.2 安装3. 安装ROS23.1 设置支持UTF-8的locale编码3.2 添加证书3.3 安装ROS3.4 设置环境变量3.5 小海龟来啦4. 运行实例4.1 安装Gazebo4.2 安装turtlebot总结 1. 初识 1.1 到手开箱搞来一套OrangeP

鲲鹏社区

OrangePi Kunpeng Pro深度评测：性能与体验的完美融合

目录一、引言二、硬件开箱与介绍1.硬件清单2.硬件介绍三、软件介绍四、性能测试1. 功率测试2. cpu测试2.1 单线程cpu测试2.2 多线程cpu测试五、实际开发体验1. 搭建API服务器2. ONNX推理测试3. 在线推理平台五、测评总结1. 能与硬件配置2. 系统与软件3. 实际开发体验个人总结一、引言近期，香橙派(Orange Pi) 联合华为再次发布力作—OrangePi Kun

鲲鹏社区

所有评论(0)

查看更多评论

LuckyRich1

@fight_p

已为社区贡献1条内容