首页 > 编程语言 >C++--二叉搜索树

C++--二叉搜索树

时间：2024-08-19 19:51:45浏览次数：11  
标签：right cur parent -- C++ 二叉 key else left

 

目录

 1.1二叉搜索树概念

1.2二叉搜索树操作 

1.2.1查找

1.2.2插入

1.2.3删除

2.3二叉搜索树实现 

2.4二叉搜索树的应用 

2.5二叉搜索树的性能分析

 1.1二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树 ，或者是具有以下性质的二叉树 : --若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 --若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 --它的左右子树也分别为二叉搜索树

1.2二叉搜索树操作 

1.2.1查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。 b、最多查找高度次，走到到空，还没找到，这个值不存在。
1.2.2插入
a. 树为空，则直接新增节点，赋值给root指针 b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

1.2.3删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回 , 否则要删除的结点可能分下面四种情 况： a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有 4 中情况，实际情况 a 可以与情况 b 或者 c 合并起来，因此真正的删除过程 如下： 情况 b ：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 -- 直接删除 情况 c ：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 -- 直接删除 情况 d ：在它的右子树中寻找中序下的第一个结点 ( 关键码最小 ) ，用它的值填补到被删除节点 中，再来处理该结点的删除问题 -- 替换法删除
2.3二叉搜索树实现 
template<class T>
struct BSTNode
{
    BSTNode(const T& data = T())
        : _pLeft(nullptr), _pRight(nullptr), _data(data)
    {}
    BSTNode<T>* _pLeft;
    BSTNode<T>* _pRight;
    T _data;
};
template<class T>
class BSTree
{
    typedef BSTNode<T> Node;
    typedef Node* PNode;
public:
    BSTree() : _pRoot(nullptr)
    {}
    // 同学们自己实现，与二叉树的销毁类似
    ~BSTree();
    // 根据二叉搜索树的性质查找：找到值为data的节点在二叉搜索树中的位置
    PNode Find(const T& data);
    bool Insert(const T& data)
    {
        // 如果树为空，直接插入
        if (nullptr == _pRoot)
        {
            _pRoot = new Node(data);
            return true;
        }
        // 按照二叉搜索树的性质查找data在树中的插入位置
        PNode pCur = _pRoot;
        // 记录pCur的双亲，因为新元素最终插入在pCur双亲左右孩子的位置
        PNode pParent = nullptr;
        while (pCur)
        {
            pParent = pCur;
            if (data < pCur->_data)
                pCur = pCur->_pLeft;
            else if (data > pCur->_data)
                pCur = pCur->_pRight;  // 元素已经在树中存在
            else
                return false;
        }
        // 插入元素
        pCur = new Node(data);
        if (data < pParent->_data)
            pParent->_pLeft = pCur;
        else
            pParent->_pRight = pCur;
        return true;
    }
    bool Erase(const T& data)
    {
        // 如果树为空，删除失败
        if (nullptr == _pRoot)
            return false;
        // 查找在data在树中的位置
        PNode pCur = _pRoot;
        PNode pParent = nullptr;
        while (pCur)
        {
            if (data == pCur->_data)
                break;
            else if (data < pCur->_data)
            {
                pParent = pCur;
                pCur = pCur->_pLeft;
            }
            else
            {
                pParent = pCur;
                pCur = pCur->_pRight;
            }
        }
        // data不在二叉搜索树中，无法删除
        if (nullptr == pCur)
            return false;
        // 分以下情况进行删除，大家自己画图分析完成
        if (nullptr == pCur->_pRight)
        {
            // 当前节点只有左孩子或者左孩子为空---可直接删除
        }
        else if (nullptr == pCur->_pRight)
        {
            // 当前节点只有右孩子---可直接删除
        }
        else
        {
            // 当前节点左右孩子都存在，直接删除不好删除，可以在其子树中找一个替代结点，
            比如：
                // 找其左子树中的最大节点，即左子树中最右侧的节点，或者在其右子树中最小的节
                点，即右子树中最小的节点
                // 替代节点找到后，将替代节点中的值交给待删除节点，转换成删除替代节点
        }
        return true;
    }
private:
    PNode _pRoot;
};
2.4二叉搜索树的应用 
1. K 模型： K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到 的值 。 比如： 给一个单词 word ，判断该单词是否拼写正确 ，具体方式如下： 以词库中所有单词集合中的每个单词作为 key ，构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。 2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即 <Key, Value> 的键值对 。该种方 式在现实生活中非常常见： 比如 英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文 <word, chinese> 就构成一种键值对； 再比如 统计单词次数 ，统计成功后，给定单词就可快速找到其出现的次数， 单词与其出 现次数就是 <word, count> 就构成一种键值对 。 key结构二叉搜索树 
namespace key
{
	template<class K>
	struct BSTNode
	{
		BSTNode(const K& key = K())
			: _left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}

		BSTNode<K>* _left;
		BSTNode<K>* _right;
		K _key;
	};

	template<class K>
	class BSTree
	{
		typedef BSTNode<K> Node;
	public:
		BSTree() : _root(nullptr)
		{}

		bool Find(const K& key) {
			Node* cur = _root;
			while (cur) {
				if (key > cur->_key) {
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					cur = cur->_left;
				}
				else {
					return true;
				}
			}
			return false;
		}
		bool Insert(const K& key)
		{
			if (_root == nullptr) {
				_root = new Node(key);
				return true;
			}
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					return false;
				}
			}
			cur = new Node(key);
			if (key > parent->_key) {
				parent->_right = cur;
			}
			else {
				parent->_left = cur;
			}
			return true;
		}
		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else {//找到了删除
					//删除无孩子或一个孩子的节点
					if (cur->_left == nullptr) {

						if (parent == nullptr) {
							_root = cur->_right;
						}
						else {
							if (cur == parent->_left) {
								parent->_left = cur->_right;
							}
							else if (cur == parent->_right) {
								parent->_right = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr) {

						if (parent == nullptr) {
							_root = cur->_left;
						}
						else {
							if (cur == parent->_left) {
								parent->_left = cur->_left;
							}
							else if (cur == parent->_right) {
								parent->_right = cur->_left;
							}
						}
						delete cur;
						return true;
					}//删除两个孩子的节点
					else {
						//找右子树的最左替换，再删除用来替换的节点
						Node* rightMinP = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left) {
							rightMinP = rightMin;
							rightMin = rightMin->_left;
						}
						cur->_key = rightMin->_key;
						if (rightMin == rightMinP->_left) {
							rightMinP->_left = rightMin->_right;
						}
						else {
							rightMinP->_right = rightMin->_right;
						}
						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}
		void InOrder() {
			_InOrder(_root);
			cout << endl;
			return;
		}

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

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

			return;
		}
	private:
		Node* _root;
	};
}
kv结构搜索二叉树 
namespace keyValue {
	template<class K, class V>
	struct BSTNode
	{
		BSTNode(const K& key = K(), const V& value = V())
			: _left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
			,_parent(nullptr)
		{}

		BSTNode<K, V>* _left;
		BSTNode<K, V>* _right;
		BSTNode<K, V>* _parent;
		K _key;
		V _value;
	};

	template<class K, class V>
	class BSTree
	{
		typedef BSTNode<K, V> Node;
	public:
		bool Insert(const K& key, const V& value) {
			if (_root == nullptr) {
				_root = new Node(key, value);
				return true;
			}
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					return false;
				}
			}
			cur = new Node(key, value);
			if (key > parent->_key) {
				parent->_right = cur;
			}
			else {
				parent->_left = cur;
			}
			return true;
		}
		Node* Find(const K& key) {
			Node* cur = _root;
			while (cur) {
				if (key > cur->_key) {
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					cur = cur->_left;
				}
				else {
					return cur;
				}
			}
			return nullptr;
		}
		bool Erase(const K& key) {
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (key > cur->_key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key) {
					parent = cur;
					cur = cur->_left;
				}
				else {//找到了删除
					//删除无孩子或一个孩子的节点
					if (cur->_left == nullptr) {

						if (parent == nullptr) {
							_root = cur->_right;
						}
						else {
							if (cur == parent->_left) {
								parent->_left = cur->_right;
							}
							else if (cur == parent->_right) {
								parent->_right = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					else if (cur->_right == nullptr) {

						if (parent == nullptr) {
							_root = cur->_left;
						}
						else {
							if (cur == parent->_left) {
								parent->_left = cur->_left;
							}
							else if (cur == parent->_right) {
								parent->_right = cur->_left;
							}
						}
						delete cur;
						return true;
					}//删除两个孩子的节点
					else {
						//找右子树的最左替换，再删除用来替换的节点
						Node* rightMinP = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left) {
							rightMinP = rightMin;
							rightMin = rightMin->_left;
						}
						cur->_key = rightMin->_key;
						if (rightMin == rightMinP->_left) {
							rightMinP->_left = rightMin->_right;
						}
						else {
							rightMinP->_right = rightMin->_right;
						}
						delete rightMin;
						return true;
					}
				}
			}
			return false;
		}
		void _InOrder(Node* cur) {
			if (cur == nullptr) {
				return;
			}
			_InOrder(cur->_left);
			cout << cur->_key << ":" << cur->_value << " ";
			_InOrder(cur->_right);

			return;
		}
		void InOrder() {
			_InOrder(_root);
			cout << endl;
			return;
		}
	private:
		Node* _root = nullptr;
	};
}
2.5二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 对有 n 个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树： 最优情况下，二叉搜索树为完全二叉树 ( 或者接近完全二叉树 ) ，其平均比较次数为： $log_2 N$ 最差情况下，二叉搜索树退化为单支树 ( 或者类似单支 ) ，其平均比较次数为： $\frac{N}{2}$ 问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插 入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的 AVL 树和红黑树就可以上 场了。

标签：right,cur,parent,--,C++,二叉,key,else,left
From： https://blog.csdn.net/m0_74085682/article/details/141311337

相关文章

  • Node-RED开源流程网络工具
    文章目录Node-RED开源流程网络工具Node-RED介绍特点和设计理念Node-RDE安装Windows安装Docker安装基础功能示列HTTP发送请求MQTT-示列TCP-示列MQTT-Modbus示列Node-RED综合示列示列Node-RED开源流程网络工具Node-RED介绍Node-RED是一个基于Node.js的开源流程......
  • 重生 之 被裁员后开滴滴之前学习了鸿蒙(part2)
    12.ArkUI-界面1.组件1.定义容器组件()｛//内容｝基础组件(参数)ps：UI界面构建的最小元素是组件ps：最外层只能有一个容器组件(距离build最近的)2.组件属性方法组件()｛｝.属性方法1(参数).属性方法2(参数).属性方法3(参数)……ps：若是基本组件可......
  • ECON10004: INTRODUCTORY MICROECONOMICS
    ECON10004:INTRODUCTORYMICROECONOMICSASSIGNMENT1:SEMESTER2,2024Due:Wednesday,August21,6pm•AssignmentsmustbesubmittedviatheLMSsubjectwebpage.•Remembertokeepacopyofyourassignment.•Thisassignmentwillaccountfor15%ofyour......
  • ssh配置文件安全设置
    1.在/etc/ssh/sshd_config中设置空闲超时值为200秒2.在/etc/ssh/sshd_config中禁用空密码3.在SSH配置文件（/etc/ssh/sshd_config）中禁用X11（图形服务器）转发功能，Shell访问不需要4.将MaxAuthenticationTries调整为/etc/ssh/sshd_config中的较低值，因此攻击者在尝试使用失败的密......
  • python随笔day4
    python实战面试题目1、列出你知道的http协议的状态码，说出表示什么意思？1xx临时响应2xx成功3xx重定向4xx请求错误5xx服务器错误我经常遇到的：200成功、404未找到网页文件、403服务器拒绝请求（禁止）、304未修改（自从上次请求后该网页就未修改过）、500服务器内部错误、503服务器......
  • CSCI 4210 — Operating Systems
    CSCI 4210 — Operating SystemsSimulation Project Part II (document version 1.0)Processes and CPU SchedulingOverview•  This assignment is due in Submitty by 11:59PM EST on Thursday,August 15, 2024• Thisprojectistobecom......
  • 动态dp & 矩阵加速递推
    广义矩阵乘法我们定义两个矩阵\(A,B\)在广义矩阵乘法下的乘积为\(C\)，其中\[C=\begin{bmatrix}\max\limits_{i=1}\limits^{m}A_{1,i}+B_{i,1}&\max\limits_{i=1}\limits^{m}A_{1,i}+B_{i,2}&\dots&\max\limits_{i=1}\limits^{m}A_{1,i}+B_{i,k}\\\......
  • 网络
    找到了一种比较严谨的证明将一次连边，看做合并节点，如下，假设连接\(5,7\)新图变成这样：然后再在新图上继续进行操作，每次删掉的边就是桥的数量将上述过程缩的点的内部形态仍然看做原树的形态，即可知上述过程可以用书中的并查集优化（集合的代表元素就是深度最浅的节点）以后树上路......
  • 性能测试之中间件：告诉你什么是 kafka 和 MQ ？
    在如今这个数据驱动的时代，中间件在性能测试中扮演着至关重要的角色。你是否曾听说过Kafka和MQ，却不清楚它们在实际应用中具体的作用是什么？让我们一起来揭开它们的神秘面纱。Kafka和MQ究竟是什么？它们在性能测试中如何发挥作用，又为何成为现代分布式系统中的关键组成部分？ Kafka是......
  • CHC5223 Data Structures and Algorithms
    CHC5223DataStructuresandAlgorithms2023-2024-21of6AssignmentValue100%ofCourseworkResitIndividualworkBackgroundThesubwaysystemofacityisanetworkofundergroundorelevatedtrainsthatproviderapidtransitforpassengerswithint......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99