C++:二叉搜索树(非平衡化)

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

C++:二叉搜索树(非平衡化)

一.二叉搜索树(key_value模型)

  • 树的节点定义:
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		//key是用于实现搜索功能以及搜索树其他功能的关键值
		K _key;
		//value用于存储数据
		V _value;
		//树结点的默认构造函数
		BSTreeNode(const K& key = K(), const V& value = V())
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};
  • 如果一颗二叉树是二叉搜索树,则其具有如下性质:
    • 左子树的所有结点的key值都比根结点的key值
    • 右子树的所有结点的key值都比根结点的key值
    • 二叉搜索树的左右子树仍为二叉搜索树
      C++:二叉搜索树(非平衡化)
  • 二叉搜索树满足递归定义
  • 容易证明,二叉搜索树的中序遍历序列是一个升序序列(因此二叉搜索树具有排序功能,也被称作二叉排序树)
  • 根据搜索树的定义可知,树中不存在key值相同的节点,因此搜索树还具有去重的功能
  • 二叉搜索树C++类模板总览:
	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
	//供外界调用的功能接口(通过复用内部私有接口实现)
		
		//强制生成类的默认构造函数
		BSTree() = default; 
		//利用前序遍历递归完成拷贝构造
		BSTree(const BSTree<K,V>& t)
		{
			_root = _Copy(t._root);
		}
		//通过复用拷贝构造实现赋值运算符重载
		BSTree<K,V>& operator =(BSTree<K,V>t)
		{
			std::swap(t._root, _root);
			return (*this);
		}
		//插入节点
		bool InsertR(const K& key, const V& value)
		{
			return _InsertR(_root,key, value);
		}
		//查找节点
		Node* Find(const K& key)
		{
			return _FindR(_root,key);
		}
		//删除节点(这里调用递归的接口)
		bool Erase(const K& key)
		{
			return _EraseR(_root, key);
		}
		//中序遍历搜索树
		void InOrder()
		{
			_InOrder(_root);
		}
		//搜索树的析构函数
		~BSTree()
		{
			_Destroy(_root);
		}
	protected:
	//私有功能接口
		//用于实现拷贝构造的辅助函数(前序递归实现)
		Node* _Copy(const Node* root);
		//后序遍历销毁二叉树
		void _Destroy(Node*& root);
		//递归实现插入节点
		bool _InsertR(Node*& root, const K& key,const V& value);
		//递归实现节点查找
		Node * _FindR(Node*& root, const K& key);
		//递归删除搜索树结点
		bool _EraseR(Node*& root, const K& key);
		//非递归删除搜索树结点
		bool _Erase(Node *&root,const K& key)//中序遍历搜索树
		void _InOrder(Node* root);
		//寻找子树key值最大的结点的接口
		Node* _FindMax(Node* root);
	private:
		//根节点指针
		Node* _root = nullptr;
	};

二.二叉搜索树的节点删除

  • 搜索树节点删除操作必须保持二叉搜索树的结构性质不变
  • 非递归删除搜索树节点
    • 接口首部:bool _Erase(Node*& root, const K& key) (删除成功则返回true,否则返回false)

    • 代码逻辑思维导图: C++:二叉搜索树(非平衡化)

    • 删除情况1演示:C++:二叉搜索树(非平衡化)

    • 删除情况3演示:C++:二叉搜索树(非平衡化)

    • 删除情况2演示:C++:二叉搜索树(非平衡化)

    • 情况2中的子树最值替换删除法保证了搜索树的结构性质以及删除方式的简洁性和逻辑唯一性

    • 非递归删除结点代码:

		//非递归删除节点
		bool _Erase(Node*& root, const K& key)
		{
			Node* precur = nullptr;
			Node* cur = root;
			while (cur)
			{
				if (cur->_key > key)
				{
					precur = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					precur = cur;
					cur = cur->_right;
				}
				else
				{
					//执行删除操作
					//找到待删除节点
					//待删除结点只可能有右孩子
					if (cur->_left == nullptr)
					{
						//判断待删结点是否为根节点
						if (root == cur)
						{
							root = cur->_right;
						}
						else
						{
							//将右孩子交给前驱指针
							if (precur->_left == cur)
							{
								precur->_left = cur->_right;
							}
							else
							{
								precur->_right = cur->_right;
							}
						}
						delete cur;
						cur = nullptr;
						return true;
					}
					//待删除结点只有左孩子
					else if (cur->_right == nullptr)
					{
						//判断待删结点是否为根节点
						if (root == cur)
						{
							root = cur->_left;
						}
						else
						{
							//将左孩子交给前驱指针
							if (precur->_left == cur)
							{
								precur->_left = cur->_left;
							}
							else
							{
								precur->_right = cur->_left;
							}
						}
						delete cur;
						cur = nullptr;
						return true;
					}
					//待删除结点既有左孩子又有右孩子
					else
					{
						//用左子树的最大结点与待删节点进行替换后,再删除待删节点
						Node* Maxpre = cur;
						Node* Max = cur->_left;
						while (Max->_right)
						{
							Maxpre = Max;
							Max = Max->_right;
						}
						std::swap(Max->_key, cur->_key);
						//将左孩子交给前驱指针
						if (Maxpre->_left == Max)
						{
							Maxpre->_left = Max->_left;
						}
						else
						{
							Maxpre->_right = Max->_left;
						}
						delete Max;
						Max = nullptr;
						return true;
					}
				}
			}
			return false;
		}
  • 递归删除搜索树节点:
    • 接口首部bool _EraseR(Node*& root, const K& key)
    • 递归删除搜索树节点算法采用节点指针变量的引用进行传参递归,形参直接引用了当前待操作节点前驱指针,因此在函数中可以直接通过形参待删除节点的前驱指针进行修改,代码书写上会简单很多
    • 递归删除搜索树节点代码:
		//寻找子树最大结点的接口
		Node* _FindMax(Node*root)
		{
			while (root->_right)
			{
				root = root->_right;
			}
			return root;
		}
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}
			else if (root->_key > key)
			{
				//在左子树中删除节点
				_EraseR(root->_left, key);
			}
			else if (root->_key < key)
			{
				//在右子树中删除节点
				_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* Max = _FindMax(root->_left);
					std::swap(Max->_key, root->_key);
					//递归删除换位后的目标节点
					_EraseR(root->_left, key);
					return true;
				}
				delete del;
				return true;
			}
		}

三.二叉搜索树类对象其他接口

构造函数,析构函数和赋值运算符重载

  • 辅助接口Node* _Copy(const Node* root)
  • 拷贝构造函数BSTree(const BSTree<K,V>& t)
		//强制编译器生成类的默认构造函数
		BSTree() = default;
		//用于实现拷贝构造的辅助函数(前序递归实现树的深拷贝)
		Node* _Copy(const Node* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			Node* Root = new Node(root->_key,root->_value);
			Root->_left = _Copy(root->_left);
			Root->_right = _Copy(root->_right);
			return Root;
		}
		BSTree(const BSTree<K,V>& t)
		{
			_root = _Copy(t._root);
		}
  • 赋值运算符重载:
    • 接口首部:BSTree<K,V>& operator =(BSTree<K,V>t),通过复用拷贝构造实现
		//通过复用拷贝构造实现赋值运算符重载
		BSTree<K,V>& operator =(BSTree<K,V>t)
		{
			std::swap(t._root, _root);
			return (*this);
		}

C++:二叉搜索树(非平衡化)文章来源地址https://www.toymoban.com/news/detail-498083.html

  • 析构函数:
    • 后序遍历递归释放所有节点
    • 辅助接口:void _Destroy(Node*& root);
		//后序遍历销毁二叉树
		void _Destroy(Node*& root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Destroy(root->_left);
			_Destroy(root->_right);
			delete root;
			root = nullptr;
		}
		//搜索树的析构函数
		~BSTree()
		{
			_Destroy(_root);
		}

节点插入接口和节点查找接口

  • 节点插入接口
    • 辅助接口bool _InsertR(Node*& root, const K& key,const V& value);,通过递归实现节点的插入
    • 供外界调用的接口:bool InsertR(const K& key, const V& value);
		//递归插入节点
		bool _InsertR(Node*& root, const K& key,const V& value)
		{
			if (root == nullptr)
			{
				//找到空位置则插入
				root = new Node(key,value);
				return true;
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key,value);
			}
			else if (root->_key < key)
			{
				return _InsertR(root->_right, key,value);
			}
			else
			{
				//找到相同节点则插入失败
				//插入操作中体现了搜索树的去重功能
				return false;
			}
		}
		//插入节点
		bool InsertR(const K& key, const V& value)
		{
			return _InsertR(_root, key, value);
		}
  • 节点查找接口
    • 递归实现:
		//递归实现查找
		Node * _FindR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				//找到空则说明结点不存在
				return nullptr;
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left,key);
			}
			else if (root->_key < key)
			{
				return _FindR(root->_right,key);
			}
			else
			{
				return root;
			}
		}
		//查找节点
		Node* Find(const K& key)
		{
			return _FindR(_root, key);
		}

key_value模型二叉搜索树类模板总体代码

namespace key_value
{
#pragma once
	template<class K, class V>
	struct BSTreeNode
	{
		BSTreeNode<K, V>* _left;
		BSTreeNode<K, V>* _right;
		K _key;
		V _value;
		BSTreeNode(const K& key = K(), const V& value = V())
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};


	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:
		//强制生成类的默认构造函数
		BSTree() = default;
		//利用前序遍历递归完成拷贝构造
		BSTree(const BSTree<K,V>& t)
		{
			_root = _Copy(t._root);
		}
		//通过复用拷贝构造实现赋值运算符重载
		BSTree<K,V>& operator =(BSTree<K,V>t)
		{
			std::swap(t._root, _root);
			return (*this);
		}
		//插入节点
		bool InsertR(const K& key, const V& value)
		{
			return _InsertR(_root, key, value);
		}
		//查找节点
		Node* Find(const K& key)
		{
			return _FindR(_root, key);
		}
		//删除节点
		bool Erase(const K& key)
		{
			return _EraseR(_root, key);
		}
		//中序遍历搜索树
		void InOrder()
		{
			_InOrder(_root);
		}
		//搜索树的析构函数
		~BSTree()
		{
			_Destroy(_root);
		}
	protected:
		//用于实现拷贝构造的辅助函数(前序递归实现树的深拷贝)
		Node* _Copy(const Node* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			Node* Root = new Node(root->_key,root->_value);
			Root->_left = _Copy(root->_left);
			Root->_right = _Copy(root->_right);
			return Root;
		}
		//后序遍历销毁二叉树
		void _Destroy(Node*& root)
		{
			if (root == nullptr)
			{
				return;
			}
			_Destroy(root->_left);
			_Destroy(root->_right);
			delete root;
			root = nullptr;
		}
		//递归插入节点
		bool _InsertR(Node*& root, const K& key,const V& value)
		{
			if (root == nullptr)
			{
				//找到空位置则插入
				root = new Node(key,value);
				return true;
			}
			else if (root->_key > key)
			{
				return _InsertR(root->_left, key,value);
			}
			else if (root->_key < key)
			{
				return _InsertR(root->_right, key,value);
			}
			else
			{
				//找到相同节点则插入失败
				return false;
			}
		}
		//递归实现查找
		Node * _FindR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				//找到空则说明结点不存在
				return nullptr;
			}
			else if (root->_key > key)
			{
				return _FindR(root->_left,key);
			}
			else if (root->_key < key)
			{
				return _FindR(root->_right,key);
			}
			else
			{
				return root;
			}
		}
		//非递归删除节点
		bool _Erase(Node*& root, const K& key)
		{
			Node* precur = nullptr;
			Node* cur = root;
			while (cur)
			{
				if (cur->_key > key)
				{
					precur = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					precur = cur;
					cur = cur->_right;
				}
				else
				{
					//执行删除操作
					//找到待删除节点
					//待删除结点只可能有右孩子
					if (cur->_left == nullptr)
					{
						//判断待删结点是否为头节点
						if (root == cur)
						{
							root = cur->_right;
						}
						else
						{
							if (precur->_left == cur)
							{
								precur->_left = cur->_right;
							}
							else
							{
								precur->_right = cur->_right;
							}
						}
						delete cur;
						cur = nullptr;
						return true;
					}
					//待删除结点只有左孩子
					else if (cur->_right == nullptr)
					{
						//判断待删结点是否为头节点
						if (root == cur)
						{
							root = cur->_left;
						}
						else
						{
							if (precur->_left == cur)
							{
								precur->_left = cur->_left;
							}
							else
							{
								precur->_right = cur->_left;
							}
						}
						delete cur;
						cur = nullptr;
						return true;
					}
					//待删除结点既有左孩子又有右孩子
					else
					{
						//用左子树的最大结点与待删节点进行替换后,再删除待删节点
						Node* Maxpre = cur;
						Node* Max = cur->_left;
						while (Max->_right)
						{
							Maxpre = Max;
							Max = Max->_right;
						}
						std::swap(Max->_key, cur->_key);
						if (Maxpre->_left == Max)
						{
							Maxpre->_left = Max->_left;
						}
						else
						{
							Maxpre->_right = Max->_left;
						}
						delete Max;
						Max = nullptr;
						return true;
					}
				}
			}
			return false;
		}
		//递归删除搜索树结点
		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
			{
				return false;
			}
			else if (root->_key > key)
			{
				_EraseR(root->_left, key);
			}
			else if (root->_key < key)
			{
				_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* Max = _FindMax(root->_left);
					std::swap(Max->_key, root->_key);
					_EraseR(root->_left, key);
					return true;
				}
				delete del;
				return true;
			}
		}
		//中序遍历搜索树
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}
			_InOrder(root->_left);
			cout << "结点的key值:" << root->_key << ' ' << "节点的value:" << root->_value << endl;
			_InOrder(root->_right);
		}
		//寻找子树最大结点的接口
		Node* _FindMax(Node* root)
		{
			while (root->_right)
			{
				root = root->_right;
			}
			return root;
		}
	private:
		Node* _root = nullptr;
	};
}

四.未经平衡化的二叉搜索树的缺陷

  • 二叉搜索树的节点插入,删除,查找操作的时间复杂度取决于搜索树的高度
  • 在相同节点数量下,完全二叉树的高度是最小的,搜索树为完全二叉树时,节点插入,删除,查找操作的时间复杂度都为O(logN)
  • 然而,相同的结点集合,构造出的二叉搜索树高度是不确定的(有时甚至会直接构造出单链表的线性形状,此时搜索树便退化为线性表),比如:C++:二叉搜索树(非平衡化)
  • 因此,想让二叉搜索树在实际场景中发挥作用,就需要平衡化算法对其进行优化(所谓平衡化就是改变搜索树的结构使其接近完全二叉树)
    C++:二叉搜索树(非平衡化)

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

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

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

相关文章

  • 【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)

    前面我们对 map / multimap / set / multiset 进行了简单的介绍,可以发现,这几个容器有个共同点是: 其底层都是按照 二叉搜索树 来实现的。 但是二叉搜索树有其自身的缺陷,假如 往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成 O(N) ,

    2024年02月06日
    浏览(45)
  • C++数据结构之平衡二叉搜索树(一)——AVL的实现(zig与zag/左右双旋/3+4重构)

    本文是介绍众多平衡二叉搜索树(BBST)的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树(BST)在极度退化的情况下,十分不平衡,不平衡到只朝一侧偏,成为一条链表,复杂度可达 O ( n ) O(n) O ( n ) ,所以我们要在“平衡”方面做一些约束,以防

    2024年02月13日
    浏览(38)
  • C++力扣题目450--删除二叉搜索树中的节点

    给定一个二叉搜索树的根节点  root  和一个值  key ,删除二叉搜索树中的  key  对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一般来说,删除节点可分为两个步骤: 首先找到需要删除的节点; 如果找到了,删除它。 示例

    2024年01月17日
    浏览(39)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(58)
  • 算法与数据结构--二叉搜索树与自平衡二叉搜索树

    注:字典的 \\\"member运算\\\" 指的是检查字典中是否存在某个特定的键的操作,即查询操作。 如果我们使用数组来实现字典/map,虽然使用二分法查询也可以达到logn,但是的话插入和删除太慢了。使用链表实现的话虽然插入和删除是O(1),但是查询的话达到了O(n),也不可取。 因此人

    2024年02月04日
    浏览(38)
  • AVL树(平衡二叉搜索树)

    如果BST树插入的顺序是有序的,那么BST树就会退化成一个双链表结构,查询的速率就会很慢, 所以有了AVL树的意义。 AVL 树的定义: 是具有下列性质的二叉搜索树         1、它的左子树和右子树都是AVL树         2、左子树和右子树的高度之差的绝对值不超过1 结点的平衡因

    2024年02月05日
    浏览(32)
  • 【平衡二叉搜索树(AVL)-- 旋转】

    打怪升级:第60天 AVLTree,也就是我们所说的:自平衡二叉搜索树,AVL命名由来是两位发明者的名字的首字母,并无其他含义。 AVL树有两个重要的特点: AVL树是一棵搜索树; AVL树左右子树的高度差的绝对值不大于1; AVL树的左右子树也是AVL树。 高度差可取0,1,-1。 注:我们将

    2024年02月02日
    浏览(31)
  • 【C++要笑着学】搜索二叉树 (SBTree) | K 模型 | KV 模型

      🔥 订阅量破千的火热 C++ 教程 👉 火速订阅 《C++要笑着学》   🔥 CSDN 累计订阅量破千的火爆 C/C++ 教程的 2023 重制版,C 语言入门到实践的精品级趣味教程。 了解更多: 👉  \\\"不太正经\\\" 的专栏介绍  ← 试读第一章 订阅链接: 🔗 《C语言趣味教程》 ← 猛戳订阅! 💭

    2023年04月13日
    浏览(63)
  • leetcode 1382. 将二叉搜索树变平衡

           本题分为两步,先用中序遍历将二叉搜索树转化为排序数组,再通过排序数组构建一个平衡二叉树。 代码如下:          本题的这两个步骤可以当作模板背下来。

    2024年02月09日
    浏览(36)
  • Java LeetCode篇-二叉树经典解法(实现:判断平衡二叉树、找两个节点最近的祖先等)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 平衡二叉树         1.1 实现判断平衡二叉树的思路         1.2 代码实现判断平衡二叉树         2.0 二叉树的层序遍历         2.1 实现二叉树层序遍历的思路          2.2

    2024年02月05日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包