【C++】– 搜索二叉树

  • Post author:
  • Post category:其他



目录


一、二叉搜索树概念


二、二叉搜索树操作(非递归)


1.二叉搜索树的查找 (非递归)


(1)查找


(2)中序遍历


2.二叉搜索树的插入(非递归)


3.二叉搜索树的删除(非递归)


三、二叉搜索树操作(递归)


1.二叉搜索树的查找(递归)


2.二叉搜索树的插入(递归)


3.二叉搜索树的删除(递归)


四、二叉搜索树的默认成员函数


1.构造


2.拷贝构造


3.赋值运算符重载


4.析构


五、K模型和KV模型搜索树


1.K模型搜索树


2.KV模型搜索树


六、二叉搜索树性能分析



一、二叉搜索树概念

二叉搜索树也叫做二叉排序树,它要么是一棵空树,要么具有以下性质:

(1)若它的左子树不为空,则左子树上所有节点的值都小于根节点的值

(2)若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

(3)它的左右子树也分别为二叉搜索树

如下就是二叉搜索树,对于任何一个节点,它的左子树的所有节点值都比它小,它的右子树的所有节点值都比它大:

int a[] = {9,6,15,4,13,5,1,20,8,27};

总结:在左子树值比根小,右子树值比根大。 当树走中序遍历时,序列都是有序的。

二叉搜索树的结构定义:

#include<iostream>
using namespace std;

//树的节点可以支持多种类型
template<class K>

//树节点结构
struct BSTreeNode
{
	BSTreeNode<K>* _left;//左指针
	BSTreeNode<K>* _right;//右指针
	K _key;//值

	//树节点构造函数
	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

template<class K>
class BStree//树结构
{
	typedef BSTreeNode<K> Node;
public:

	//构造函数只需要将根初始化为空就行了
	BSTree()
		:_root(nullptr)
	{}

private:
	Node* _root;//根
};


二、二叉搜索树操作(非递归)


1.二叉搜索树的查找


(非递归)

二份查找借助排序查找,二叉搜索树借助结构

查找的时间复杂度,最坏查找高度次,就可以确认一个值在不在树中:

(1)当树接近完全二叉树或满二叉树 ,时间复杂度为O(N):

(2)查找的时间复杂度

最坏为O(N)

,如下这种情况:

因此二叉搜索树在极端情况下没办法保证效率。


(1)查找

查找比较简单:

①key比当前节点值大,向左走

②key比当前节点值小,向右走

③key等于当前节点值,找到了

	//查找
	Node* Find(const K& key)
	{
		Node* cur = _root;
		if (cur->_key > key)//比当前节点小,就向左走
		{
			cur = cur->_left;
		}
		else if (cur->_key < key)//比当前节点大,就向右走
		{
			cur = cur->_right;
		}
		else
		{
			return cur;//找到了,返回
		}

		return nullptr;
	}


(2)中序遍历

由于根节点的访问限定符是私有的,那么在main函数中要终须遍历一棵树时,就无法将二叉搜索树的对象根节点传给中序遍历,因为类外面访问不到私有成员。

因此可以这样考虑:这个二叉搜索树对象是有根节点的,可以考虑在里面套一层,给套在里面的函数传参_root ,去递归调用自己:

	//内层函数使用_root
    void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);//递归调用自己
		cout << root->_key << " ";
		_Inorder(root->_right);//递归调用自己
	}

	//先调不传参数的InOrder
	void InOrder()
	{
		//把_root传给子函数,让子函数去使用_root
		_InOrder(_root);
		cout << endl;
	}


2.二叉搜索树的插入(非递归)

插入节点分两步:

(1)找位置

①key比当前节点值大,向左走

②key比当前节点值小,向右走

③key等于当前节点值,该节点值已经存在,插入失败

(2)插入

①key比父亲节点值小就插入父亲左子树

②key比父亲节点值大就插入父亲右子树

由于插入后,要将节点链接到树中,因此要定义parent节点,用来链接新节点:

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

		//2.树不为空 非递归方式,两步:(1)找位置  (2)插入节点
		//(1)找位置
		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
			{
				return false;//树里面已经有这个节点了,就返回flase
			}
		}

		//(2)插入节点
		cur = new Node(key);
		if(parent->_key > key)//比父亲节点值小就连接在父亲左子树
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;//比父亲节点值大就连接在父亲右子树
		}
		return true;
	}


3.二叉搜索树的删除(非递归)

(1)找位置

①key比当前节点值大,向左走

②key比当前节点值小,向右走

③key等于当前节点值,找到了,准备删除

(2)删除,有两种删除方法:非递归和递归

非递归删除:

①该节点没有孩子,即该节点是叶子节点,删除节点后把父亲指向自己的指针置空

②该节点有一个孩子,就把该节点的孩子节点的链接给该节点的父亲,顶替自己的位置,①可以当成②的特殊情况

③该节点有两个孩子,找比它自己的左孩子大,比它自己的右孩子小的节点替换它(也就是拿它的左子树的最大节点或右子树的最小节点替换它),替换之后,该节点就只有一个孩子或没有孩子了,就变成①或②了。

	//删除
	bool Erase(const 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//找到了,要删除
			{
				//1.删除的是叶子节点, 删除节点后把父亲指向自己的指针置空
				//2.删除的是有一个孩子的节点,就把它的孩子节点的链接给它的父亲,顶替自己的位置
				//3.删除的是有两个孩子的节点,找比它自己的左孩子大,比它自己的右孩子小的节点替换它,
				//也就是它的左子树的最大节点或右子树的最小节点替换它,它就只有一个孩子或没有孩子了

				//第1可以当成第2去处理,当前节点的父亲节点指向空就可以了

				if (cur->_left == nullptr)//cur左为空,就让父亲指向cur的右
				{
					//如果要删除根,直接让根的右孩子做根
					if (cur == _root)
					{
						_root = cur->_right;
					}
                    else
                    {
					    if (parent->_left == cur)//当cur是父亲的左时,就让父亲的左指向cur的右
					    {
						    parent->_left = cur->_right;
					    }
					    else//当cur是父亲的右时,就让父亲的右指向cur的右
					    {
						    parent->_right = cur->_right;
					    }
                    }

					delete cur;
				}
				else if (cur->_right == nullptr)//cur右为空,就让父亲指向cur的左
				{
					//如果要删除根,直接让根的右孩子做根
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)//当cur是父亲的左时,就让父亲的左指向cur的左
						{
							parent->_left = cur->_left;
						}
						else//当cur是父亲的右时,就让父亲的右指向cur的左
						{
							parent->_right = cur->_left;
						}
					}

					delete cur;//删除
				}
				else//左右都不为空,替换法删除
				{
					//找右子树最左节点  当右子树的左孩子不为空时就继续遍历
					Node* minRight = cur->_right;
					Node* minParent = cur;//这里不要初始化成null,否则左为空时,minParent->_left就会崩掉

					//当左不为空时,就一直向左走,直到找到右子树最左节点
					while (minRight->_left)
					{
						minParent = minRight;
						minRight = minRight->_left;
					}

					//保存替换节点的值
					cur->_key = minRight->_key;

					//删除替换节点
					if (minParent->_left == minRight)//如果右子树最左节点是minParent的左,那就让minParent的左指向右子树最左节点的右
					{
						minParent->_left = minRight->_right;
					}
					else//如果右子树最左节点是minParent的右,那就让minParent的右指向右子树最左节点的右
					{
						minParent->_right = minRight->_right;
					}
					delete minRight;//删除
				}

				return true;
			}
			
		}
		return false;//cur不存在,直接返回
	}

递归删除:

相对于非递归,只需要修改找到了要修改的代码:找到了后不需要管cur到底左为空、右为空、还是左右都不为空

① 找要删除节点的右子树的最小节点并把它的值保存起来

② 删除右子树的最小节点

③ 把要删除的节点值替换成右子树的最小节点值

                else//左右都不为空,替换法删除
                {
					//找右子树最小节点
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						minRight = minRight->_left;
					}

					//用min保存右子树最小节点的值
					K min = minRight->_key;

					//递归调用自己去替换删除节点,一定会走到左为空的情况处理
					this->Erase(min);

					//删除完毕替换节点之后,把cur的值替换成min
					cur->_key = min;
				}


三、二叉搜索树操作(递归)

理解了非递归操作以后, 递归操作就很简单了:

#include<iostream>
using namespace std;

//树的节点可以支持多种类型
template<class K>
//树节点结构
struct BSTreeNode
{
	BSTreeNode<K>* _left;//左指针
	BSTreeNode<K>* _right;//右指针
	K _key;//值

	//构造函数
	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

template<class K>
class BStree//树结构
{
	typedef BSTreeNode<K> Node;
public:
	//递归查找
	Node* 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);
	}
private:
	Node* _root;
};

由于_root是私有的,可以把递归子函数查找、插入、删除都定义成私有的


1.二叉搜索树的查找(递归)

递归查找:

private:
    //查找
	Node* _FindR(Node* root, const K& key)
	{
		if (root == nullptr)//没找到
		{
			return nullptr;
		}

		if (key < root->_key)//到左子树去找
		{
			FindR(root->_left, key);
		}
		else if (key > root->_key)//到右子树去找
		{
			FindR(root->_right, key);
		}
		else//找到了
		{
			return root;
		}
	}


2.二叉搜索树的插入(递归)

递归插入:当找到的位置为空时才插入

	//插入 加了&,root是_root的别名,修改root就直接修改到上一层调用,不用找父亲
	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)//找到位置了
		{
			root = new Node(key);
			return true;
		}
		if (key < root->_key)//到左子树去找位置
		{
			_InsertR(root->_left, key);
		}
		else if (key > root->_key)//到右子树去找位置
		{
			_InsertR(root->_right, key);
		}
		else//已存在,无需插入
		{
			return false;
		}
	}


3.二叉搜索树的删除(递归)

递归删除:和二叉树的删除(非递归)一样,找到后的删除也有两种方式,递归和非递归

找到后的非递归删除:

    //插入 加了&,root是_root的别名,修改root就直接修改到上一层调用,不用找父亲	
    bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)//没找到
		{
			return false;
		}
		if (key < root->_key)//到左子树去找
		{
			_EraseR(root->_left, key);
		}
		else if (key > root->_key)//到右子树去找
		{
			_EraseR(root->_right, key);
		}
		else
		{
			//找到了,root就是要删除的节点
			if (root->_left == nullptr)//root左为空
			{
				Node* del = root;
				root = root->_right;
				delete del;
			}
			else if (root->_right == nullptr)//root右为空
			{
				Node* del = root;
				root = root->_left;
				delete del;
			}
			else//root左右都不为空
			{
				//找到右子树最左节点替换
				Node* minParent = root;
				Node* minRight = root->_right;

				while (minRight->_left)
				{
					minParent = minRight;
					minRight = minRight->_left;
				}

				//保存替换节点的值
				cur->_key = minRight->_key;

				//链接
				if (minParent->_left == minRight)
				{
					minParent->_left = minRight->_right;
				}
				else
				{
					minParent->_right = minRight->_right;
				}

				//删除
				delete minRight;
			}
			return true;
		}
	}

找到后的递归删除:

			else//root左右都不为空
			{				
                //找右子树最左节点
				Node* minRight = root->_right;
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}

				//保存右子树最左节点的值
				K min = minRight->_key;

				//使用递归方法删除右子树最左节点
				_Erase(root->_right, min);
			}


四、二叉搜索树的默认成员函数

现在还剩下二叉搜索树的构造、拷贝构造、赋值运算符重载、析构函数。


1.构造

前面已经写过构造函数了, 即只需要把根初始化为空就行了:

public:
	//构造函数需要将根初始化为空就行了
	BSTree()
		:_root(nullptr)
	{}


2.拷贝构造

拷贝构造利用递归调用子函数不断拷贝节点:

	//拷贝构造
	BSTree(const BSTree<K>& t)
	{
		_root = t.copy(t._root);
	}

在子函数处:

	Node* _copy(Node* root)
	{
		if (root == nullptr)//如果根为空,直接返回
		{
			return;
		}

		Node* copyNode = new Node(root->_key);//创建根节点
		copyNode->_left = _copy(root->_left);//递归拷贝左子树节点
		copyNode->_right = _copy(root->_right);//递归拷贝右子树节点
		
		return copyNode;//返回根
	}


3.赋值运算符重载

借助拷贝构造用现代写法写:

	//赋值运算符重载(现代写法)
	BSTree& operator=(const BSTree<K>& t)
	{
		swap(_root,t._root);
		return *this;
	}


4.析构

递归调用子函数去析构

	//析构
	~BSTree()
	{
		_Destroy(_root);
		_root = nullptr;
	}

在子函数处:

	_Destroy(root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}


五、K模型和KV模型搜索树


1.K模型搜索树

K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。K模型不存在重复值。

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

(1)以单词集合中的每个单词作为key,构建一棵二叉搜索树

(2)在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。

#pragma once
#include<iostream>
using namespace std;

namespace K
{
	//树的节点可以支持多种类型
	template<class K>
	//树节点结构
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;//左指针
		BSTreeNode<K>* _right;//右指针
		K _key;//值

		//构造函数
		BSTreeNode(const K& key)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};

	template<class K>
	class BStree//树结构
	{
		typedef BSTreeNode<K> Node;
	private:
		//查找
		Node* _FindR(Node* root, const K& key)
		{
			if (root == nullptr)//没找到
			{
				return nullptr;
			}

			if (key < root->_key)//到左子树去找
			{
				FindR(root->_left, key);
			}
			else if (key > root->_key)//到右子树去找
			{
				FindR(root->_right, key);
			}
			else//找到了
			{
				return root;
			}
		}

		//插入 加了&,root是_root的别名,修改root就直接修改到上一层调用,不用找父亲
		bool _InsertR(Node*& root, const K& key)
		{
			if (root == nullptr)//找到位置了
			{
				root = new Node(key);
				return true;
			}
			if (key < root->_key)//到左子树去找位置
			{
				_InsertR(root->_left, key);
			}
			else if (key > root->_key)//到右子树去找位置
			{
				_InsertR(root->_right, key);
			}
			else//已存在,无需插入
			{
				return false;
			}
		}

		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)//没找到
			{
				return false;
			}
			if (key < root->_key)//到左子树去找
			{
				_EraseR(root->_left, key);
			}
			else if (key > root->_key)//到右子树去找
			{
				_EraseR(root->_right, key);
			}
			else
			{
				//找到了,root就是要删除的节点
				if (root->_left == nullptr)//root左为空
				{
					Node* del = root;
					root = root->_right;
					delete del;
				}
				else if (root->_right == nullptr)//root右为空
				{
					Node* del = root;
					root = root->_left;
					delete del;
				}
				else//root左右都不为空
				{
					//找右子树最左节点
					Node* minRight = root->_right;
					while (minRight->_left)
					{
						minRight = minRight->_left;
					}

					//保存右子树最左节点的值
					K min = minRight->_key;

					//使用递归方法删除右子树最左节点
					_Erase(root->_right, min);
				}
				return true;
			}
		}

		Node* _copy(Node* root)
		{
			if (root == nullptr)//如果根为空,直接返回
			{
				return;
			}

			Node* copyNode = new Node(root->_key);//创建根节点
			copyNode->_left = _copy(root->_left);//递归拷贝左子树节点
			copyNode->_right = _copy(root->_right);//递归拷贝右子树节点

			return copyNode;//返回根
		}

		_Destroy(root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Destroy(root->_left);
			_Destroy(root->_right);
			delete root;
		}
	public:
		//构造函数需要将根初始化为空就行了
		BSTree()
			:_root(nullptr)
		{}

		//拷贝构造
		BSTree(const BSTree<K>& t)
		{
			_root = t.copy(t._root);
		}

		//赋值运算符重载(现代写法)
		BSTree& operator=(const BSTree<K>& t)
		{
			swap(_root, t._root);
			return *this;
		}

		//析构
		~BSTree()
		{
			_Destroy(_root);
			_root = nullptr;
		}

		//中序遍历
		void _Inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Inorder(root->_left);//递归调用自己
			cout << root->_key << " ";
			_Inorder(root->_right);//递归调用自己
		}

		//先调不传参数的InOrder
		void InOrder()
		{
			//把_root传给子函数,让子函数去使用_root
			_InOrder(_root);
			cout << endl;
		}
	public:
		//递归查找
		Node* 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);
		}
	private:
		Node* _root;
	};
}


2.KV模型搜索树

KV模型:每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方式在现实生活中非常常见:比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英文单词与其对应的中文<word, chinese>就构成一种键值对;再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出现次数就是<word, count>就构成一种键值对。

比如:实现一个简单的英汉词典dict,可以通过英文找到与其对应的中文,具体实现方式如下:

(1)<单词,中文含义>为键值对构造二叉搜索树,注意:二叉搜索树需要比较,键值对比较时只比较Key。

(2)查询英文单词时,只需给出英文单词,就可快速找到与其对应的key。

KV模型可以插入重复值,在K模型的基础上,节点增加了_value成员,用来_key去查找_value,_value的类型不确定,再增加一个模板参数即可:

namespace KV
{
	//树的节点可以支持多种类型
	template<class K, class V>
	//树节点结构
	struct BSTreeNode
	{
		BSTreeNode<K,V>* _left;//左指针
		BSTreeNode<K,V>* _right;//右指针
		K _key;
		V _value;//增加了_value成员

		//构造函数
		BSTreeNode(const K& key)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			,_value(value)//初始化_value成员
		{}
	};

	template<class K, class V>//模板类型从K变成了KV
	class BStree//树结构
	{
		typedef BSTreeNode<K,V> Node;//模板类型从K变成了KV
	private:
		//查找
		Node* _FindR(Node* root, const K& key)
		{
			if (root == nullptr)//没找到
			{
				return nullptr;
			}

			if (key < root->_key)//到左子树去找
			{
				FindR(root->_left, key);
			}
			else if (key > root->_key)//到右子树去找
			{
				FindR(root->_right, key);
			}
			else//找到了
			{
				return root;
			}
		}

		//插入 加了&,root是_root的别名,修改root就直接修改到上一层调用,不用找父亲
		bool _InsertR(Node*& root, const K& key, const V& value)//增加了_value成员
		{
			if (root == nullptr)//找到位置了
			{
				root = new Node(key, value);
				return true;
			}
			if (key < root->_key)//到左子树去找位置
			{
				_InsertR(root->_left, key, value);
			}
			else if (key > root->_key)//到右子树去找位置
			{
				_InsertR(root->_right, key, value);
			}
			else//已存在,无需插入
			{
				return false;
			}
		}

		bool _EraseR(Node*& root, const K& key,const V& value)//增加了_value成员
		{
			if (root == nullptr)//没找到
			{
				return false;
			}
			if (key < root->_key)//到左子树去找
			{
				_EraseR(root->_left, key, value);
			}
			else if (key > root->_key)//到右子树去找
			{
				_EraseR(root->_right, key, value);
			}
			else
			{
				//找到了,root就是要删除的节点
				if (root->_left == nullptr)//root左为空
				{
					Node* del = root;
					root = root->_right;
					delete del;
				}
				else if (root->_right == nullptr)//root右为空
				{
					Node* del = root;
					root = root->_left;
					delete del;
				}
				else//root左右都不为空
				{
					//找右子树最左节点
					Node* minRight = root->_right;
					while (minRight->_left)
					{
						minRight = minRight->_left;
					}

					//保存右子树最左节点的值
					K kMin = minRight->_key;
					V vMin = minRight->value;//增加了_value成员

					//使用递归方法删除右子树最左节点
					_Erase(root->_right, kMin);
					root->_key = kMin;
					root->_value = vMin;//增加了_value成员
				}
				return true;
			}
		}

		Node* _copy(Node* root)
		{
			if (root == nullptr)//如果根为空,直接返回
			{
				return nullptr;
			}

			Node* copyNode = new Node(root->_key,root->_value);//创建根节点,增加了_value成员
			copyNode->_left = _copy(root->_left);//递归拷贝左子树节点
			copyNode->_right = _copy(root->_right);//递归拷贝右子树节点

			return copyNode;//返回根
		}

		_Destroy(root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Destroy(root->_left);
			_Destroy(root->_right);
			delete root;
		}
	public:
		//构造函数需要将根初始化为空就行了
		BSTree()
			:_root(nullptr)
		{}

		//拷贝构造
		BSTree(const BSTree<K>& t)
		{
			_root = t.copy(t._root);
		}

		//赋值运算符重载(现代写法)
		BSTree& operator=(const BSTree<K>& t)
		{
			swap(_root, t._root);
			return *this;
		}

		//析构
		~BSTree()
		{
			_Destroy(_root);
			_root = nullptr;
		}

		//中序遍历
		void _Inorder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Inorder(root->_left);//递归调用自己
			cout << root->_key << ":" << root->_value<<endl;//增加了_value成员
			_Inorder(root->_right);//递归调用自己
		}

		//先调不传参数的InOrder
		void InOrder()
		{
			//把_root传给子函数,让子函数去使用_root
			_InOrder(_root);
			cout << endl;
		}
	public:
		//递归查找
		Node* FindR(const K& key)
		{
			return _FindR(_root, key);
		}

		//递归插入
		bool InsertR(const K& key,const V& value)//增加了_value成员
		{
			return _InsertR(_root, key, value);
		}

		//递归删除
		bool EraseR(const K& key)
		{
			return _EraseR(_root, key);
		}
	private:
		Node* _root;
	};
}


六、二叉搜索树性能分析

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

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


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

例如按照序列{1,4,5,6,8,9,13,15,20,27},构建二叉树:

元素相同,但是次序不同的序列{27,20,15,13,9,8,6,5,4,1},构建二叉树:

最优情况下,二叉搜索树为完全二叉树,其平均比较次数为:


最差情况下,二叉搜索树退化为单支树,其平均比较次数为:



版权声明:本文为gx714433461原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。