• 数据结构: 二叉搜索树

    目录

    1.二叉搜索树概念

    2.二叉搜索树的操作

    3.二叉搜索树的实现

    3.1定义BST

    3.2功能实现

    1.默认成员函数

    2.非递归

    插入

    查找

    删除

    3.递归

    插入

    查找

    删除

    4.二叉搜索树的应用

    1.二叉搜索树概念

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

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

    2.二叉搜索树的操作

    1.查找

    从根开始查找:

    --若查找的值比根节点的值大, 向右查找. 

    --若比根节点的值小向左查找.

    --循环下去,若到nullptr都没找到,返回false

    2.插入

    a.空树

    1.直接将其设为根节点

    b.非空树

    1.根据二叉搜索树的性质,找到插入的位置

    2.在该位置上新生成一个节点,并与父节点链接

    (可能是左,也可能是右) 根据这个节点的key与parent的key值判断在那边链接

    3.删除

    1.找到要删除的节点

    2.对该节点进行讨论:

    a.该节点没有节点或只有1子个节点

    --可以直接删除, 并将它的子节点给它的父点

    b.该节点有2个子节点

    --找到它左子树最大节点/右子树最小节点来代替它, 并将其删除

    3.细节处理

    当删除到root->left/right为空的时候, 需要更新头节点

    3.二叉搜索树的实现

    3.1定义BST

    节点

    1. template<class K >
    2. struct BSTreeNode 
    3. {
    4. 	BSTreeNode* _left;
    5. 	BSTreeNode* _right;
    6. 	K _key;
    7.  
    8. 	//构造函数
    9. 	BSTreeNode(const K& k) 
    10. 		:_left(nullptr)
    11. 		,_right(nullptr)
    12. 		,_key(k)
    13. 	{}
    14. };

    BSTree

    1. template<class K, class V>
    2. class BSTree
    3. {
    4. 	typedef BSTreeNode Node;
    5. public:
    6.  
    7.     //功能
    8. 	bool Insert(const K& key, const V& value);
    9. 	Node* Find(const K& key);
    10. 	bool Erase(const K& key);
    11. 	void _InOrder(Node* root);
    12. 	void InOrder();
    13.  
    14. private:
    15. 	Node* _root = nullptr;
    16. };

    3.2功能实现

    1.默认成员函数

    构造函数

    1. 	//构造函数
    2. 	BSTree()
    3. 		:_root(nullptr)
    4. 	{}

    拷贝构造

    1. 	//拷贝构造
    2. 	BSTree(const BSTree<K>& t) 
    3. 	{
    4. 		Copy(t._root);
    5. 	}
    6. 	Node* Copy(Node* root)
    7. 	{
    8. 		if (root == nullptr)
    9. 			return nullptr;
    10. 		//前序遍历拷贝
    11. 		Node* newRoot = new Node(root->_key);
    12. 		newRoot->_left = Copy(root->_left);
    13. 		newRoot->_right = Copy(root->_right);
    14.  
    15. 		return newRoot;
    16. 	}

    赋值运算符

    1. 	//赋值运算符
    2. 	BSTree<K>& operator=(BSTree<K> t)
    3. 	{
    4. 		swap(_root,t._root);
    5. 		return *this;
    6. 	}

    析构函数

    1. 	//析构函数
    2. 	~BSTree() 
    3. 	{
    4. 		Destory(_root);
    5. 	}
    6.  
    7. 	void Destory(Node*& root) 
    8. 	{
    9. 		if (root == nullptr)
    10. 			return;
    11. 		Destory(root->_left);
    12. 		Destory(root->_right);
    13. 		
    14. 		delete root;
    15. 		root = nullptr;
    16. 	}

    2.非递归

    插入

    a.空树

    --插入的节点直接变为根节点

    b.非空树

    --根据二叉搜索树性质找到插入的位置

    --与父节点链接(讨论parent的key与插入节点的key值来决定链接在parent的那边)

    1. 	bool Insert(const K& key)
    2. 	{
    3. 		//a.空树(直接将该节点设为根节点)
    4. 		if (_root == nullptr)
    5. 		{
    6. 			_root = new Node(key);
    7. 			return true;
    8. 		}
    9.  
    10. 		//b.非空树
    11. 		//1.找到插入的位置
    12. 		Node* cur = _root;
    13. 		Node* parent = nullptr;
    14. 		while (cur)
    15. 		{
    16. 			if (key < cur->_key)
    17. 			{
    18. 				parent = cur;
    19. 				cur = cur->_left;
    20. 			}
    21. 			else if (key > cur->_key)
    22. 			{
    23. 				parent = cur;
    24. 				cur = cur->_right;
    25. 			}
    26. 			else
    27. 			{
    28. 				return false;
    29. 			}
    30. 		}
    31. 		//2.链接节点
    32. 		cur = new Node(key);
    33. 		if (parent->_key > key)
    34. 		{
    35. 			parent->_left = cur;
    36. 		}
    37. 		else
    38. 		{
    39. 			parent->_right = cur;
    40. 		}
    41. 		return true;
    42. 	}

    查找

    1. 	Node* Find(const K& key)
    2. 	{
    3. 		Node* cur = _root;
    4. 		while (cur) 
    5. 		{
    6. 			if (key < cur->_key) 
    7. 			{
    8. 				cur = cur->_left;
    9. 			}
    10. 			else if (key > cur->_key) 
    11. 			{
    12. 				cur = cur->_right;
    13. 			}
    14. 			else 
    15. 			{
    16. 				return cur;
    17. 			}
    18. 		}
    19. 		return nullpte;
    20. 	}

    删除

    找到删除节点的位置

    1.删除的节点只有1个节点或者没有节点(直接删除,将cur的子节点给parent)

    --没有节点也可以这么操作,相当于把空的子节点给父亲

    --若有1个子节点,把该子节点给父亲 (讨论cur的位置,可能是p的左也可能是p的右)

    2.删除的节点有2个节点:  找到它左子树最大的节点/ 右子树最小的节点代替它, 并删除

    --找到删除的节点

    --找到左子树最大节点/右子树最小节点来代替它(把cur存的key变为leftMax/rightMin的key)

    --找该节点的过程, cur是在leftMax/rightMin的位置,删除cur节点

    (当然要处理它的子节点,讨论一下leftMax是pleftMax左边还是右边)

    3.处理空指针: 当删除的节点为cur, 并且cur只有左子树或者只有右子树,更新头节点

    1. 	bool Erase(const K& key) 
    2. 	{
    3. 		//找到要删除的节点
    4. 		Node* parent = nullptr;
    5. 		Node* cur = _root;
    6.  
    7. 		while (cur) 
    8. 		{
    9. 			if (cur->_key > key) 
    10. 			{
    11. 				parent = cur;
    12. 				cur = cur->_left;
    13. 			}
    14. 			else if (cur->_key < key)
    15. 			{
    16. 				parent = cur;
    17. 				cur = cur->_right;
    18. 			}
    19. 			else 
    20. 			{
    21. 				//删除
    22. 				//1.左为空
    23. 				if (cur->_left == nullptr) 
    24. 				{
    25. 					//处理删除到根节点只有左子树/右子树
    26. 					if (cur == _root) 
    27. 					{
    28. 						_root = cur->_right;
    29. 					}
    30. 					else 
    31. 					{
    32. 						//将子节点给父节点
    33. 						if (parent->_left == cur)
    34. 						{
    35. 							parent->_left = cur->_right;
    36. 						}
    37. 						else
    38. 						{
    39. 							parent->_right = cur->_right;
    40. 						}
    41. 					}
    42. 					delete cur;
    43. 				}
    44. 				//2.右为空
    45. 				else if (cur->_right == nullptr) 
    46. 				{
    47. 					if (cur = _root) 
    48. 					{
    49. 						_root = cur->_left;
    50. 					}
    51. 					else 
    52. 					{
    53. 						if (parent->_left == cur) 
    54. 						{
    55. 							parent->_left = cur->_left;
    56. 						}
    57. 						else 
    58. 						{
    59. 							parent->_right = cur->_left;
    60. 						}
    61. 					}
    62. 				}
    63. 				//3.左右不为空(找左子树最大节点/右子树最小节点)
    64. 				else 
    65. 				{
    66. 					Node* pmaxLeft = cur;
    67. 					Node* maxLeft = cur->_left;
    68.  
    69. 					while (maxLeft->_right) 
    70. 					{
    71. 						pmaxLeft = maxLeft;
    72. 						maxLeft = maxLeft->_right;
    73. 					}
    74. 					cur->_key = maxLeft->_key;
    75. 					
    76. 					//把maxLeft的子节点交给其parent,然后删除maxLeft
    77. 					if (pmaxLeft->_left == maxLeft) 
    78. 					{
    79. 						pmaxLeft->_left = maxLeft->_left;
    80. 					}
    81. 					else 
    82. 					{
    83. 						pmaxLeft->_right = maxLeft->_left;
    84. 					}
    85. 					delete maxLeft;
    86. 				}
    87. 				return true;
    88. 			}
    89. 		}
    90. 		return false;
    91. 	}

    3.递归

    插入

    1. 	//1.插入
    2. 	bool _InsertR(Node*& root, const K& key)
    3. 	{
    4. 		if (root == nullptr)
    5. 		{
    6. 			root = new Node(key);
    7. 			return true;
    8. 		}
    9.  
    10. 		if (root->_key > key)
    11. 		{
    12. 			return _InsertR(root->_left, key);
    13. 		}
    14. 		else if (root->_key < key)
    15. 		{
    16. 			return _InsertR(root->_right, key);
    17. 		}
    18. 	}

    查找

    根据二叉搜索树的性质查找:

    1. 	//2.查找
    2. 	bool _FindR(Node*& root, const K& key)
    3. 	{
    4. 		if (root == nullptr)
    5. 		{
    6. 			return false;
    7. 		}
    8.  
    9. 		if (root->_key == key)
    10. 			return true;
    11.  
    12. 		if (root->_key > key)
    13. 			return _FindR(root->_left, key);
    14. 		else
    15. 			return _FindR(root->_right, key);
    16.  
    17. 	}

    删除

    1. 	//3.删除
    2. 	bool _EraseR(Node*& root, const K& key) 
    3. 	{
    4. 		if (root == nullptr)
    5. 			return false;
    6.  
    7. 		//找到要删除的节点
    8. 		if (root->_key > key) 
    9. 		{
    10. 			return _EraseR(root->_left, key);
    11. 		}
    12. 		else if (root->_key < key) 
    13. 		{
    14. 			return _EraseR(root->_right, key);
    15. 		}
    16. 		else 
    17. 		{
    18. 			//删除
    19. 			Node* del = root;
    20. 			//1.左为空
    21. 			if (root->_left == nullptr) 
    22. 			{
    23. 				root = root->_right;
    24. 			}
    25. 			//2.右为空
    26. 			else if (root->_right == nullptr) 
    27. 			{
    28. 				root = root->_left;
    29. 			}
    30. 			//3.左右不为空
    31. 			else 
    32. 			{
    33. 				Node* minRight = root->_right;
    34. 				while (minRight->_left) 
    35. 				{
    36. 					minRight = minRight->_left;
    37. 				}
    38. 				swap(root->_key,minRight->_key );
    39.  
    40. 				//转换为在它的右子树去删除
    41. 				return _EraseR(root->_right,key);
    42. 			}
    43. 			delete del;
    44.  
    45. 			return true;
    46. 		}
    47. 	}

    效果:

    4.二叉搜索树的应用

    1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
    比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

    • 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
    • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

    2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方
    式在现实生活中非常常见：

    • 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
    • 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对

    示例

    英汉词典

    统计次数

    中序遍历打印的时候,补上value就行:

    达到上面的效果:把K改为KV型

    节点:

    BSTree

    5.性能分析

    最优: logN

    最差: N

    代码:BSTree-K/BSTree · 朱垚/数据结构练习 - 码云 - 开源中国 (gitee.com)

  • 相关阅读:
    开源WebRTC库放大器模式在采集桌面图像时遇到的DPI缩放与内存泄漏问题排查
    【Visual Leak Detector】源码编译 VLD 库
    only id(String) method calls allowed in plugins {} script block
    关于GBDT算法、XGBoost算法的基本原理概述
    npm下载的包分类
    【python数据可视化】利用Python爬取天气数据并实现数据可视化，绘制天气轮播图
    基于jQuery HTML5的全屏背景视频插件
    【C语言】数据类型之结构体
    Zone 和 Zoneset 是什么关系
    86、移除推理路径上的所有内存操作
  • 原文地址：https://blog.csdn.net/m0_70402487/article/details/133881110