二叉搜索树(Binary_Search_Tree)

这篇具有很好参考价值的文章主要介绍了二叉搜索树(Binary_Search_Tree)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉搜索树概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
若它的左子树不为空,则左子树上所有节点的值都小于根节点的值。
若它的右子树不为空,则右子树上所有节点的值都大于根节点的值。
它的左右子树也分别为二叉搜索树。
如:
二叉搜索树(Binary_Search_Tree),C++,c++,数据结构

二叉搜索树的操作

查找

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

插入

插入的具体过程如下:
a. 树为空,则直接新增节点,赋值给root指针
b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

删除

首先查找元素是否在二叉搜索树中,如果不存在,则返回。
如果存在,可以分为下面三种情况:
1.删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
2.删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
3.在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点
中,再来处理该结点的删除问题–替换法删除(与堆中删除数据类似)

二叉搜索树的应用

  1. K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。
    比如:给一个单词word,判断该单词是否拼写正确,具体方式如下:
    a.以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树
    b.在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。
  2. **KV模型:每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。**该种方
    式在现实生活中非常常见:
    a.比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英
    文单词与其对应的中文<word, chinese>就构成一种键值对;
    b.再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出
    现次数就是<word, count>就构成一种键值对.

二叉搜索树的实现

K模型

template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _l;
	BSTreeNode<K>* _r;
	K _k;

	BSTreeNode(const K& k)
		:_l(nullptr)
		, _r(nullptr)
		, _k(k)
	{}
};

首先定义一个二叉搜索树K模型的结构体。同二叉树一样包含左右孩子节点,还有_k值,一般情况下,二叉搜索树的_k值是唯一的,因为当前节点左孩子的_k小于当前节点的_k,而右孩子的则比当前节点的_k大,所以当插入一个在二叉搜索树中存在的值时,会返回false,不进行插入。

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


public:
	bool insert(const K& k)
	{
		if (_root == nullptr)
		{
			_root = new Node(k);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_k < k)
			{
				parent = cur;
				cur = cur->_r;
			}
			else if (cur->_k > k)
			{
				parent = cur;
				cur = cur->_l;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(k);
		if (parent->_k < k)
		{
			parent->_r = cur;
		}
		else
		{
			parent->_l = cur;
		}
		return true;
	}

在二叉搜索树中查找结点比较简单,根据二叉搜索树的性质,左子树小于根小于右子树能确定,当x大于当前节点的_k时,去右子树中找,小于则去左子树中找,遇到空节点则说明不存在。

bool find(const K& k)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_k < k)
		{
			cur = cur->_r;
		}
		else if (cur->_k > k)
		{
			cur = cur->_l;
		}
		else
		{
			return true;
		}
	}
	return false;
}

二叉搜索树的删除则比较麻烦,首先因为删除节点后要保证树的完整性,所以find节点时也要标记当前节点的父节点,当找到要删除的节点时,就要判断该节点的孩子节点的情况,可以分为左孩子为空、右孩子为空、左右孩子都存在。(左右孩子都不存在并入1、2情况中)
a.左孩子节点为空:
首先判断当前节点是否为根节点,如果是根节点,直接使右孩子为根节点
二叉搜索树(Binary_Search_Tree),C++,c++,数据结构
若不是根节点,则判断当前节点是父节点的左孩子还是右孩子,如果是左孩子,则父节点的右指针指向该节点的右孩子,否则让父节点的左指针指向当前节点的右孩子
二叉搜索树(Binary_Search_Tree),C++,c++,数据结构
二叉搜索树(Binary_Search_Tree),C++,c++,数据结构

b.右孩子节点为空:
同样先判断当前节点是否为根节点,为根节点则让根节点为左孩子节点
二叉搜索树(Binary_Search_Tree),C++,c++,数据结构
再判断当前节点是父节点左孩子还是右孩子,为左孩子则让父节点的左指针指向被删节点的左孩子,反之让父节点的右指针指向当前节点的左孩子

二叉搜索树(Binary_Search_Tree),C++,c++,数据结构
二叉搜索树(Binary_Search_Tree),C++,c++,数据结构

c.被删节点左右孩子都存在,此时用交换法使被删节点成为前面只有单个孩子或者没有孩子节点的情况。我们可以让被删节点与右子树的最左的节点或左子树的最右节点交换。
交换的合法性:
1.二叉搜索树的性质右>根>左,对于当前节点的右子树的最左节点,在右子树中,最左代表最小,所以它比右子树其他节点小,但它又在被删节点的右子树中,所以它比被删节点大,同时就比被删节点的左子树的所有结点大,所以交换后对右子树最左结点没有影响。
2.因为是右子树的最左结点,它没有左孩子,交换后可以将被删结点带入a情况解决。

左子树的最右节点同理。

	bool erase(const K& k)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_k < k)
			{
				parent = cur;
				cur = cur->_r;
			}
			else if (cur->_k > k)
			{
				parent = cur;
				cur = cur->_l;
			}
			else
			{
				if (cur->_l == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_r;
					}
					else
					{
						if (cur == parent->_l)
						{
							parent->_l = cur->_r;
						}
						else
						{
							parent->_r = cur->_r;
						}
					}
					delete cur;
				}
				else if (cur->_r == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_l;
					}
					else
					{
						if (cur == parent->_l)
						{
							parent->_l = cur->_l;
						}
						else
						{
							parent->_r = cur->_l;
						}
					}
					delete cur;
				}
				else
				{
					Node* rightMinParent = cur;
					Node* rightMin = cur->_r;
					while (rightMin->_l)
					{
						rightMinParent = rightMin;
						rightMin = rightMin->_l;
					}
					swap(cur->_k, rightMin->_k);
					if (rightMinParent->_l == rightMin)
					{
						rightMinParent->_l = rightMin->_r;
					}
					else
					{
						rightMinParent->_r = rightMin->_r;
					}
					delete rightMin;
				}
				return true;
			}
		}
	}

完整代码

namespace K_model
{
	//K模型
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _l;
		BSTreeNode<K>* _r;
		K _k;

		BSTreeNode(const K& k)
			:_l(nullptr)
			, _r(nullptr)
			, _k(k)
		{}
	};

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


	public:
		bool insert(const K& k)
		{
			if (_root == nullptr)
			{
				_root = new Node(k);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					parent = cur;
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					parent = cur;
					cur = cur->_l;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(k);
			if (parent->_k < k)
			{
				parent->_r = cur;
			}
			else
			{
				parent->_l = cur;
			}
			return true;
		}


		bool find(const K& k)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					cur = cur->_l;
				}
				else
				{
					return true;
				}
			}
			return false;
		}


		bool erase(const K& k)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					parent = cur;
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					parent = cur;
					cur = cur->_l;
				}
				else
				{
					if (cur->_l == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_r;
						}
						else
						{
							if (cur == parent->_l)
							{
								parent->_l = cur->_r;
							}
							else
							{
								parent->_r = cur->_r;
							}
						}
						delete cur;
					}
					else if (cur->_r == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_l;
						}
						else
						{
							if (cur == parent->_l)
							{
								parent->_l = cur->_l;
							}
							else
							{
								parent->_r = cur->_l;
							}
						}
						delete cur;
					}
					else
					{
						Node* rightMinParent = cur;
						Node* rightMin = cur->_r;
						while (rightMin->_l)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_l;
						}
						swap(cur->_k, rightMin->_k);
						if (rightMinParent->_l == rightMin)
						{
							rightMinParent->_l = rightMin->_r;
						}
						else
						{
							rightMinParent->_r = rightMin->_r;
						}
						delete rightMin;
					}
					return true;
				}
			}
		}

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

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_l);
			cout << root->_k;
			_InOrder(root->_r);
		}
	private:
		Node* _root = nullptr;

	};
}

测试一下:

void testBSTree1()
{
	
	int a[] = { 3,7,5,9,11,3,2,6,4,1 ,8};
	K_model::BSTree<int> t1;
	for (auto& e : a)
	{
		t1.insert(e);
	}
	t1.InOrder();
	t1.erase(8);
	t1.InOrder();
	for (auto& e : a)
	{
		t1.erase(e);
		t1.InOrder();
	}

}

二叉搜索树(Binary_Search_Tree),C++,c++,数据结构

KV模型

KV模型的具体思路和代码实现与K模型几乎一样,只需加入一个V值与k对应即可

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		bool Insert(const K& k, const V& v)
		{
			if (_root == nullptr)
			{
				_root = new Node(k,v);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					parent = cur;
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					parent = cur;
					cur = cur->_l;
				}
				else
				{
					return false;
				}
			}
			cur = new Node(k,v);
			if (parent->_k < k)
			{
				parent->_r = cur;
			}
			else
			{
				parent->_l = cur;
			}
			return true;
		}

		
		Node* Find(const K& k)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					cur = cur->_l;
				}
				else
				{
					return cur;
				}
			}
			return nullptr;
		}

		bool Erase(const K& k)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_k < k)
				{
					parent = cur;
					cur = cur->_r;
				}
				else if (cur->_k > k)
				{
					parent = cur;
					cur = cur->_l;
				}
				else
				{
					if (cur->_l == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_r;
						}
						else
						{
							if (cur == parent->_l)
							{
								parent->_l = cur->_r;
							}
							else
							{
								parent->_r = cur->_r;
							}
						}
						delete cur;
					}
					else if (cur->_r == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_l;
						}
						else
						{
							if (cur == parent->_l)
							{
								parent->_l = cur->_l;
							}
							else
							{
								parent->_r = cur->_l;
							}
						}
						delete cur;
					}
					else
					{
						Node* rightMinParent = cur;
						Node* rightMin = cur->_r;
						while (rightMin->_l)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_l;
						}
						swap(cur->_k, rightMin->_k);
						if (rightMinParent->_l == rightMin)
						{
							rightMinParent->_l = rightMin->_r;
						}
						else
						{
							rightMinParent->_r = rightMin->_r;
						}
						delete rightMin;
					}
					return true;
				}
			}
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_l);
			cout << root->_k << ":" << root->_v << endl;
			_InOrder(root->_r);
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		Node* _root = nullptr;
	};

测试:

	void TestBSTree()
	{
		BSTree<string, string> dict;
		dict.Insert("insert", "插入");
		dict.Insert("erase", "删除");
		dict.Insert("left", "左边");
		dict.Insert("string", "字符串");
		dict.Insert("right", "右边");

		string str;
		while (cin >> str)
		{
			auto ret = dict.Find(str);
			if (ret)
			{
				cout << str << ":" << ret->_v << endl;
			}
			else
			{
				cout << "单词拼写错误" << endl;
			}
		}

		string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };
		// 统计水果出现的次
		BSTree<string, int> countTree;
		for (auto str : strs)
		{
			auto ret = countTree.Find(str);
			if (ret == NULL)
			{
				countTree.Insert(str, 1);
			}
			else
			{
				ret->_v++;
			}
		}
		countTree.InOrder();
	}

二叉搜索树(Binary_Search_Tree),C++,c++,数据结构

二叉搜索树的性能分析

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
二叉搜索树(Binary_Search_Tree),C++,c++,数据结构
最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为:lgN
最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为:N文章来源地址https://www.toymoban.com/news/detail-861001.html

到了这里,关于二叉搜索树(Binary_Search_Tree)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 最优二叉搜索树(Optimal Binary Search Tree)_20230401

    前言 如果有序数组或有序表中的各个元素查找概率相等,那么采用二叉搜索树(BST)进行折半查找,性能最优。如果有序表中各个记录的查找概率不相等,情况又如何呢? 先看一个具体例子。已知有序表keys, 同时给出各个元素的查询频率,注意到各个元素的查询频率不相同。

    2024年02月12日
    浏览(51)
  • 【C++庖丁解牛】二叉搜索树(Binary Search Tree,BST)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,

    2024年03月28日
    浏览(64)
  • 二叉查找树(binary search tree)(难度7)

    C++数据结构与算法实现(目录) 答案在此:二叉查找树(binary search tree)(答案) 写在前面 部分内容参《算法导论》 基本接口实现 1 删除 删除值为value的第一个节点 删除叶子节点1 删除叶子节点1 (3)删除叶子节点1 删除有两个孩子的节点z 分成下面几个步骤进行: 1 找到

    2024年02月10日
    浏览(44)
  • 浙大数据结构第四周之04-树6 Complete Binary Search Tree

    A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node\\\'s key. The right subtree of a node contains only nodes with keys greater than or equal to the node\\\'s key. Both the left and right subtrees must also be binary search trees. A Comple

    2024年02月16日
    浏览(49)
  • 数据结构与算法 | 二叉树(Binary Tree)

    二叉树(Binary Tree)是一种树形数据结构,由节点构成,每个节点最多有两个子节点:一个左子节点和一个右子节点。 \\\"二叉树\\\"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树

    2024年02月08日
    浏览(41)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(45)
  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • 「二分搜索Binary Search」

    二分搜索其实也是双指针,左右指针。 题解 直接二分搜索解决。 Code 但是这个数有缺陷,假如有重复的数,例如[1,2,2,2,3],想要找左边界的2,应该返回索引为1,;或者右边界的2,返回索引3,但是发现找不了,只会给你返回中间的2,返回索引2,改进在下边。 结果 Code 注意此

    2024年02月15日
    浏览(37)
  • 二叉树(binary tree)

    二叉树(Binary Tree)是一种常见的树状数据结构,它由一组节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点: 每个节点最多有两个子节点,分别称为左子节点和右子节点。 左子树和右子树也是二叉树,它们的结构与父节点类似。

    2024年02月09日
    浏览(42)
  • 数据结构与算法(三):树论(树形结构、二叉树、二叉搜索树、红黑树、Btree&B+Tree、赫夫曼树、堆树)

    树论(树形结构、二叉树、二叉搜索树、红黑树、Btree、B+Tree、赫夫曼树、堆树) 在树形结构里面重要的术语: 结点:树里面的元素。 父子关系:结点之间相连的边 子树:当结点大于1时,其余的结点分为的互不相交的集合称为子树 度:一个结点拥有的子树数量称为结点的

    2024年02月01日
    浏览(94)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包