• 机械转码日记【26】二叉搜索树

    目录

    前言 

    1.二叉搜索数的概念

    2.二叉搜索树的实现

    2.1 基本架构

    2.2二叉搜索树的插入

    2.2.1普通版本 

    2.2.2递归版本 

    2.3二叉搜索树的查找

    2.3.1普通版本

    2.3.2递归版本

    2.4二叉搜索树的删除 

     2.4.1普通版本代码

    2.4.2递归版本代码 

    2.5搜索树的析构函数

    2.6搜索树的拷贝构造 

    2.7搜索树的赋值重载

    3.二叉搜索树的应用

    4.二叉搜索树的性能分析

    前言 

    二叉搜索树是一种特殊的树形结构 ,二叉搜索树又称二叉排序树，它与我们前面学习的堆机械转码日记【3】同属树形结构，但它不是用来排序的，而是用来搜索的。

    1.二叉搜索数的概念

     二叉搜索树是具有以下性质的二叉树：

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

    2.二叉搜索树的实现

    为了更好的了解二叉搜索树的原理和构造，我们直接来实现一个二叉搜索树

    2.1 基本架构

    想要构建一个搜索二叉树，首先我们需要一个树的节点的结构，它里面有节点的值，以及指向左右子节点的指针：

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

    然后再封装一个二叉搜索树类，并且将我们刚刚创建的节点作为二叉搜索树的成员： 

    1. template<class K>
    2. class BSTree
    3. {
    4. typedef BSTreeNode Node;//方便使用，不用写BSTreeNode那么长
    5. private:
    6.     //成员变量
    7. 	Node* _root=nullptr;
    8. }

    2.2二叉搜索树的插入

    增删查改，都是数据结构的基本操作，一般二叉搜索树不支持修改（因为一修改可能大小关系就变了），那么我们先来实现增，也就是插入操作。

    二叉搜索树的插入逻辑为：

    1. 判断根节点是否为空，如果为空，直接构造一个插入值的根节点就行
    2. 如果根节点非空，那么就需要通过大小判断来找寻正确的插入位置，比根节点大往右子树走，比根节点小往左子树走。（注意找的过程中要记录父亲节点的位置，方便链接父节点和插入的节点）
    3. 链接父节点和子节点

    2.2.1普通版本 

    1. 	bool Insert(const K& key)
    2. 	{
    3. 		//判断根节点是否为空，如果为空，直接构造一个插入值的根节点就行
    4. 		if (_root == nullptr)
    5. 		{
    6. 			_root = new Node(key);
    7. 			return true;
    8. 		}
    9.  
    10. 		//非空，开始找合适的插入位置
    11. 		//定义父节点和目标节点
    12. 		Node* parent = nullptr;
    13. 		Node* cur = _root;
    14. 		//开始寻找合适插入位置
    15. 		while (cur != nullptr)
    16. 		{
    17. 			if (cur->_key < key)//插入的值比根节点大，往右子树走
    18. 			{
    19. 				parent = cur;
    20. 				cur = cur->_right;//更新子节点和父节点
    21. 			}
    22. 			else if (cur->_key > key)//插入的值比根节点小，往左子树走
    23. 			{
    24. 				parent = cur;
    25. 				cur = cur->_left;//更新子节点和父节点
    26. 			}
    27. 			else
    28. 			{
    29. 				return false;//如果插入的值和根节点相等，则不允许插入，返回false
    30. 			}
    31. 		}
    32.  
    33. 		cur = new Node(key);//将节点的键值赋给cur
    34. 		//链接子节点个父节点
    35. 		if (parent->_key < key)
    36. 		{
    37. 			parent->_right = cur;
    38. 		}
    39. 		else
    40. 		{
    41. 			parent->_left = cur;
    42. 		}
    43. 	}

    2.2.2递归版本 

     除了上面的循环版本，我们还可以写一个递归版本来实现插入操作

    1. ///递归版本//
    2. 	bool InsertR(const K& key)
    3. 	{
    4. 		return _InsertR(_root, key);
    5. 	}
    6.  
    7. 	//子函数：
    8. 	//引用传参是精髓
    9. 	//使用引用，这时候的root就是上一个节点的左右子树的别名
    10.     //修改root的同时也会修改上一个子树的左右节点（完成链接操作）
    11.     //因为我们修改的是指针，所以要实现址传递，也可以用二级指针来完成这个操作，原理相同
    12. 	bool _InsertR(Node*& root, const K& key)
    13. 	{
    14. 		//判断根节点是否为空，如果为空，直接构造一个插入值的根节点就行
    15. 		//递归到最后，要插入的那个合适的位置也是空节点
    16. 		if (root == nullptr)
    17. 		{
    18. 			root = new Node(key);
    19. 			return true;
    20. 		}
    21.  
    22. 		//插入值比根节点大，往右子树插入
    23. 		if (root->_key < key)
    24. 			return _InsertR(root->_right, key);
    25. 		//插入值比根节点小，往左子树插入
    26. 		else if (root->_key > key)
    27. 			return _InsertR(root->_left, key);
    28. 		//插入值和根节点相等，不允许插入
    29. 		else
    30. 			return false;
    31. 	}

    2.3二叉搜索树的查找

    二叉搜索树的查找的时间复杂度最高为0(N)，此种情况为二叉搜索数的插入为有序，最低为O(logn)，当二叉搜索树为完全二叉树的时候会出现这种情况。

    其实在插入的时候我们就已经嵌入了查找的逻辑了，在这里再说一遍。

    实现二叉搜索树的查找的逻辑为：

    1. 从根节点开始查找
    2. 如果查找的目标值比根节点大，往右子树找，比根节点小就往左子树找。
    3. 找到最后不为空就找到了，为空就找不到

    2.3.1普通版本

    1. bool Find(const K& key)//搜索的时间复杂度：O(N),当有序时，为O（n）
    2. 	{
    3. 		Node* cur = _root;
    4. 		while (cur)
    5. 		{
    6. 			if (cur->_key < key)
    7. 			{
    8. 				cur = cur->_right;
    9. 			}
    10. 			else if (cur->_key > key)
    11. 			{
    12. 				cur = cur->_left;
    13. 			}
    14. 			else
    15. 			{
    16. 				return true;
    17. 			}
    18. 		}
    19. 		return false;
    20. 	}

    2.3.2递归版本

    与上面插入的递归版本不同，由于查找并不需要修改节点指针，只需要用普通指针传参就可以，不需要用引用传参。

    1.     ///递归版本//
    2. 	bool FindR(const K& key)
    3. 	{
    4. 		return _FindR(_root, key);
    5. 	}
    6.     //子函数
    7. 	bool _FindR(Node* root, const K& key)
    8. 	{
    9. 		if (root == nullptr)
    10. 			return false;
    11.  
    12. 		if (root->_key < key)
    13. 		{
    14. 			return _FindR(root->_right, key);
    15. 		}
    16. 		else if (root->_key > key)
    17. 		{
    18. 			return _FindR(root->_left, key);
    19. 		}
    20. 		else
    21. 		{
    22. 			return true;
    23. 		}
    24. 	}
    25.

    2.4二叉搜索树的删除 

    要说二叉搜索树的增删查，逻辑最复杂最难搞的还得是删除，它的逻辑是：

    • 先找到需要删除的元素，如果没找到，就返回false，找到了，需要分以下情况进行处理：
    1. 要删除的结点无孩子结点
    2. 要删除的结点只有左孩子结点
    3. 要删除的结点只有右孩子结点
    4. 要删除的结点有左、右孩子结点

    看起来有待删除节点有4种情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

    • 要删除的结点只有左孩子结点或无孩子节点，则删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点——我们把它归类为直接法删除
    • 要删除的结点只有右孩子结点或无孩子节点，则删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点——我们把它归类为直接法删除
    • 要删除的结点有左、右孩子结点，则找到它左子树中的最大子节点或右子树的最小子节点，与要删除的节点的值替换，再来处理该节点的删除问题——我们把它归类为替代法删除

     

     2.4.1普通版本代码

    1. 	//搜索树最大的问题是删除
    2. 	bool Erase(const K& key)
    3. 	{
    4. 		Node* parent = nullptr;
    5. 		Node* cur = _root;
    6. 		//找到这个节点和它的父亲
    7. 		while (cur != nullptr)
    8. 		{
    9. 			if (cur->_key < key)
    10. 			{
    11. 				parent = cur;
    12. 				cur = cur->_right;
    13. 			}
    14. 			else if (cur->_key > key)
    15. 			{
    16. 				parent = cur;
    17. 				cur = cur->_left;
    18. 			}
    19. 			//等于说明找到了
    20. 			else
    21. 			{
    22. 				//分	情况
    23. 				//一个孩子，分为左孩子和右孩子，if和else if值执行一个，小心root节点，没孩子也属于一个孩子的特殊点，也可以实现
    24. 				if (cur->_left == nullptr)//只有右孩子
    25. 				{
    26. 					//cur为root需要特殊处理
    27. 					if (cur == _root)
    28. 					{
    29. 						_root = cur->_right;
    30. 					}
    31. 					//再分cur是parent的什么孩子
    32. 					else
    33. 					{
    34. 						if (parent->_left == cur)
    35. 						{
    36. 							parent->_left = cur->_right;//和右孩子链接上
    37. 						}
    38. 						else if (parent->_right == cur)
    39. 						{
    40. 							parent->_right = cur->_right;//和右孩子链接上
    41. 						}
    42.  
    43. 					}
    44. 				}
    45. 				else if (cur->_right == nullptr)//只有一个左孩子
    46. 				{
    47. 					//cur为root需要特殊处理
    48. 					if (cur == _root)
    49. 					{
    50. 						_root = cur->_left;
    51. 					}
    52. 					//再分cur是parent的什么孩子
    53. 					else
    54. 					{
    55. 						if (parent->_left == cur)
    56. 						{
    57. 							parent->_left = cur->_left;//和左孩子链接上
    58. 						}
    59. 						else if (parent->_right == cur)
    60. 						{
    61. 							parent->_right = cur->_left;//和左孩子链接上
    62. 						}
    63. 					}
    64. 				}
    65. 				else//两个孩子
    66. 				{
    67. 					//找右子树的最小节点
    68. 					Node* minnode_parent = cur;
    69. 					Node* minnode = cur->_right;
    70. 					while (minnode->_left != nullptr)
    71. 					{
    72. 						minnode_parent = minnode;
    73. 						minnode = minnode->_left;
    74. 					}
    75. 					swap(minnode->_key, cur->_key);
    76. 					//Erase(minnode->_key);//交换之后不符合搜索树的规则，会找不到
    77. 					if (minnode_parent->_left == minnode)
    78. 					{
    79. 						minnode_parent->_left = minnode->_right;//链接子节点
    80. 					}
    81. 					else
    82. 					{
    83. 						minnode_parent->_right = minnode->_right;
    84. 					}
    85.  
    86. 					delete minnode;//删掉需要删除的节点
    87. 				}
    88. 				return true;
    89. 			}
    90. 		}
    91. 		return false;
    92. 	}

    2.4.2递归版本代码 

    1. 	bool EraseR(const K& key)
    2. 	{
    3. 		return _EraseR(_root, key);
    4. 	}
    5.  
    6.     //子函数
    7. 	bool _EraseR(Node*& root, const K& key)
    8. 	{
    9. 		if (root == nullptr)
    10. 			return false;
    11.  
    12. 		if (root->_key < key)
    13. 		{
    14. 			return _EraseR(root->_right, key);
    15. 		}
    16. 		else if (root->_key > key)
    17. 		{
    18. 			return _EraseR(root->_left, key);
    19. 		}
    20. 		else
    21. 		{
    22. 			Node* del = root;
    23. 			// 删除
    24. 			//由于是引用传参，root既是父亲指向子节点指针的别名，同时也是要删除节点指针的别名
    25. 			if (root->_left == nullptr)//左为空，
    26. 			{
    27. 				root = root->_right;//链接父亲和要删除节点的孩子
    28. 			}
    29. 			else if (root->_right == nullptr)//右为空
    30. 			{
    31. 				root = root->_left;//链接父亲和要删除节点的孩子
    32. 			}
    33. 			//找右子树的最小节点
    34. 			else
    35. 			{
    36. 				Node* minRight = root->_right;
    37. 				while (minRight->_left)
    38. 				{
    39. 					minRight = minRight->_left;
    40. 				}
    41.  
    42. 				swap(root->_key, minRight->_key);//替换法删除
    43.  
    44. 				return _EraseR(root->_right, key);//到右子树删除，一定能找到
    45. 			}
    46.  
    47. 			delete del;
    48. 			return true;
    49. 		}
    50. 	}
    51.

    2.5搜索树的析构函数

    析构函数其实很简单，我们只需要递归释放树的每个节点就可以：

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

    2.6搜索树的拷贝构造 

    如果我们自己不写拷贝构造，编译器会生成默认的拷贝构造，这个时候生成的是浅拷贝函数，浅拷贝会有造成野指针的风险，因此我们必须显式写出一个深拷贝构造，与析构函数递归类似，我们也可以写一个递归拷贝构造：

    1. 	BSTree(const BSTree& t)
    2. 	{
    3. 		_root = CopyTree(t._root);
    4. 	}
    5.  
    6. 	Node* CopyTree(Node* root)
    7. 	{
    8. 		if (root == nullptr)
    9. 			return nullptr;
    10.  
    11. 		Node* copyNode = new Node(root->_key);
    12. 		copyNode->_left = CopyTree(root->_left);
    13. 		copyNode->_right = CopyTree(root->_right);
    14.  
    15. 		return copyNode;
    16. 	}

    2.7搜索树的赋值重载

    按我们前面几篇博客写赋值重载的现代写法，我们可以很容易写出搜索树的赋值重载，我们只需要在传参过程中深拷贝一个搜索树对象，并将被赋值对象和拷贝的搜索树对象的根节点的值交换，函数调用完之后拷贝的搜索树对象就自动析构了。

    1. 	BSTree& operator=(BSTree t)
    2. 	{
    3. 		swap(_root, t._root);
    4. 		return *this;
    5. 	}

    3.二叉搜索树的应用

     搜索有两种模型，K模型和KV模型

       1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜      索到的值。

        比如：查找一篇文章中是否有错误的单词，具体方式如下：

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

    K模型简而言之就是查找关键字在不在，如扫车牌系统，就是搜索看看也没有车牌的关键字，有就抬杆。 

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

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

    不难看出，我们刚刚在上面实现的二叉搜索树是K模型，那么我们可不可以改造一下，将上面的K模型改成KV模型呢？

    1. 	template<class K, class V>
    2. 	class BSTree
    3. 	{
    4. 		typedef BSTreeNode Node;
    5. 	public:
    6.  
    7. 		void InOrder()
    8. 		{
    9. 			_InOrder(_root);
    10. 			cout << endl;
    11. 		}
    12.  
    13. 		///
    14. 		Node* FindR(const K& key)
    15. 		{
    16. 			return _FindR(_root, key);
    17. 		}
    18.  
    19. 		bool InsertR(const K& key, const V& value)
    20. 		{
    21. 			return _InsertR(_root, key, value);
    22. 		}
    23.  
    24. 		bool EraseR(const K& key)
    25. 		{
    26. 			return _EraseR(_root, key);
    27. 		}
    28.  
    29. 	private:
    30. 		bool _EraseR(Node*& root, const K& key)
    31. 		{
    32. 			if (root == nullptr)
    33. 				return false;
    34.  
    35. 			if (root->_key < key)
    36. 			{
    37. 				return _EraseR(root->_right, key);
    38. 			}
    39. 			else if (root->_key > key)
    40. 			{
    41. 				return _EraseR(root->_left, key);
    42. 			}
    43. 			else
    44. 			{
    45. 				Node* del = root;
    46. 				// 删除
    47. 				if (root->_left == nullptr)
    48. 				{
    49. 					root = root->_right;
    50. 				}
    51. 				else if (root->_right == nullptr)
    52. 				{
    53. 					root = root->_left;
    54. 				}
    55. 				else
    56. 				{
    57. 					Node* minRight = root->_right;
    58. 					while (minRight->_left)
    59. 					{
    60. 						minRight = minRight->_left;
    61. 					}
    62.  
    63. 					swap(root->_key, minRight->_key);
    64.  
    65. 					return _EraseR(root->_right, key);
    66. 				}
    67.  
    68. 				delete del;
    69. 				return true;
    70. 			}
    71. 		}
    72.  
    73. 		bool _InsertR(Node*& root, const K& key, const V& value)
    74. 		{
    75. 			if (root == nullptr)
    76. 			{
    77. 				root = new Node(key, value);
    78. 				return true;
    79. 			}
    80.  
    81. 			if (root->_key < key)
    82. 				return _InsertR(root->_right, key, value);
    83. 			else if (root->_key > key)
    84. 				return _InsertR(root->_left, key, value);
    85. 			else
    86. 				return false;
    87. 		}
    88.  
    89. 		Node* _FindR(Node* root, const K& key)//返回Node*，可以修改value
    90. 		{
    91. 			if (root == nullptr)
    92. 				return nullptr;
    93.  
    94. 			if (root->_key < key)
    95. 			{
    96. 				return _FindR(root->_right, key);
    97. 			}
    98. 			else if (root->_key > key)
    99. 			{
    100. 				return _FindR(root->_left, key);
    101. 			}
    102. 			else
    103. 			{
    104. 				return root;
    105. 			}
    106. 		}
    107.  
    108. 		void _InOrder(Node* root)
    109. 		{
    110. 			if (root == nullptr)
    111. 				return;
    112.  
    113. 			_InOrder(root->_left);
    114. 			cout << root->_key << ":" << root->_value << endl;
    115. 			_InOrder(root->_right);
    116. 		}
    117. 	private:
    118. 		Node* _root = nullptr;
    119. 	};
    120.  
    121. 	void TestBSTree1()
    122. 	{
    123. 		BSTree ECDict;
    124. 		ECDict.InsertR("root", "根");
    125. 		ECDict.InsertR("string", "字符串");
    126. 		ECDict.InsertR("left", "左边");
    127. 		ECDict.InsertR("insert", "插入");
    128. 		//...
    129. 		string str;
    130. 		while (cin >> str)  //while (scanf() != EOF)多组输入
    131. 		{
    132. 			//BSTreeNode* ret = ECDict.FindR(str);//写这种也行
    133. 			auto ret = ECDict.FindR(str);
    134. 			if (ret != nullptr)
    135. 			{
    136. 				cout << "对应的中文:" << ret->_value << endl;
    137. 			}
    138. 			else
    139. 			{
    140. 				cout << "无此单词，请重新输入" << endl;
    141. 			}
    142. 		}
    143. 	}
    144.  
    145. 	void TestBSTree2()
    146. 	{
    147. 		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    148. 		//统计水果出现的次数
    149. 		BSTreeint> countTree;
    150. 		for (const auto& str : arr)
    151. 		{
    152. 			auto ret = countTree.FindR(str);//找到这个水果，
    153. 			if (ret == nullptr)//如果为空，说明不存在，则插入，value+1
    154. 			{
    155. 				countTree.InsertR(str, 1);
    156. 			}
    157. 			else
    158. 			{
    159. 				ret->_value++;  //修改value
    160. 			}
    161. 		}
    162.  
    163. 		countTree.InOrder();//中序遍历打印出水果和它的出现次数
    164. 	}
    165. }

    在STL的库里面，使用K模型的数据结构是set，使用KV模型的数据结构是map，在后面几篇博客中我们将会学习到它们。

    4.二叉搜索树的性能分析

    插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

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

    最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：O(log2N)

    最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：O(N/2)

  • 相关阅读:
    模拟版图设计工程师要学些什么？从入门到入行，你想知道的都在这里了
    Spring基础(2)：放弃XML，走向注解
    区块链轻节点的问答
    淘宝API接口
    UG\NX二次开发 用程序修改“用户默认设置”
    go语言实现二叉树的迭代后续遍历
    人脑部神经网络分布特点,人脑部神经网络分布图
    rhce--第四次作业（DNS主从服务器、iptables的使用）
    时间序列预测模型实战案例(八)(Informer)个人数据集、详细参数、代码实战讲解
    AMEYA360：村田首款1608M尺寸/100V静电容量1µF的MLCC实现商品化
  • 原文地址：https://blog.csdn.net/qq_52378490/article/details/127990954