• Day13：数据结构之(B-树)2-3树

    目录

    一、基本概念

            1.与AVL树进行比较：

            2.基本原理和插入操作の示意图

                    ①23树有三种节点

    ​                ②4节点一旦出现，需要拆分   从下往上

                    插入元素的流程：         

    二、2-3树插入代码实现

    一、基本概念

            1.与AVL树进行比较：

                    2-3树增删操作的次数比AVL树相对较少一点

                    保证查找效率的前提之下优化增删效率

            2.基本原理和插入操作の示意图

                    ①23树有三种节点

                             2节点 3节点 4节点；4节点只是临时状态


                    ②4节点一旦出现，需要拆分   从下往上


                             数据进来 先往下沉   再往上升

                    插入元素的流程：         

            如果是空树，创建一个节点即可。

            如果不是空树，插入的情况分为4种：

                    ①.向2-节点中插入元素；  

    如果未命中查找结束于2节点，直接将2节点替换为3节点，并将待插入元素添加到其中。

             file

                    ②.向一颗只含有一个3节点的树中插入元素；

            如果查找结束于3节点，先临时将其成为4节点，把待插入元素添加到其中，然后将4节点转化为3个2节点，中间的节点成为左右节点的父节点。如果之前临时4节点有父节点，就会变成向一个父节点为2节点的3节点中插入元素，中间节点与父节点为2节点的合并。

             file 

                    ③.向一个父节点为2节点的3节点中插入元素；

                     正常上浮即可。

                    ④.向一个父节点为3节点的3节点中插入元素。

            插入元素后一直向上分解临时的4节点，直到遇到2-节点的父节点变成3节点不再分解。如果达到树根节点还是4节点，则进行分解根节点

              file

    二、2-3树插入代码实现 

            每次函数进来，

            （1）优先处理三种情况：空节点、2节点、3节点(方法:根据该节点在对应位置是否有孩子->有则进行递归调用，无则看大小位置放入即可)

            （2）->函数体的第二部分紧接着检查是否产生了4节点(每次递归出了上一层的函数就会进行相应的检查并及时做出处理(所以在前面讨论的时候,是没有对4节点的处理的)

            对4节点的处理(最基本要新建两个结点node1、node2存储left和right的值以及指针，然后保存中间的值temp)

            ->紧接着判断parent是否为nullptr

                    ---是，则memset当前节点的值和指针，将刚才临时保存的temp放入，然后左右指针分别指向刚才开node1和node2即可。

                    ---否，则需要进行上浮的操作(父亲只可能是2节点or3节点)

                       ①若temp需要放在parent的第一个位置(parent最起码得有一个指针!(指向孩子))

                   此中分情况->parent有无第三个指针(若有代表有第二个孩子，为3节点)即可。然后进行移动与对node1和node2的连接

                       ②若temp需要放在父节点的第二个位置

                            (第一行判断是2节点,第二行判断是3节点)

                     仍然像上面一样，看有无第三个指针(有->代表有第二个孩子,为3节点).

                       ③若temp需要放在parent的第三个位置：

    最终parent记得count++; 并且释放原来的四节点，delete node。

    1. #pragma once
    2.  
    3. #include 
    4. using namespace std;
    5. //0 空节点 1 2节点 2 3节点 3 4节点
    6. enum state{null_node,two_node,three_node,four_node};
    7.  
    8. template<class T>
    9. class twoThreeTree
    10. {
    11. 	struct Node
    12. 	{				
    13. 		int			count;		//标记当前是 2节点还是3节点还是4节点
    14. 		T			data[3];	//存储数据的数组
    15. 		Node*		pArr[4];	//存储指针的数组
    16.  
    17. 		Node()
    18. 		{
    19. 			count = null_node;
    20. 			memset(data, 0, sizeof(T) * 3);
    21. 			memset(pArr, 0, sizeof(Node*) * 4);
    22. 		}
    23. 	};
    24.  
    25. 	Node* pRoot;//指向根节点
    26. public:
    27. 	twoThreeTree(){ pRoot = NULL; }
    28. 	~twoThreeTree(){}
    29.  
    30. 	void insertNode(const T& data);
    31. private:
    32. 	void _insertNode(Node* node, Node* pParent, const T& data);
    33. };
    34.  
    35. template<class T>
    36. void twoThreeTree::insertNode(const T& data)
    37. {
    38. 	if (pRoot)
    39. 	{
    40. 		_insertNode(pRoot, NULL, data);
    41. 	}
    42. 	else
    43. 	{//当前树为空树
    44. 		pRoot = new Node;
    45. 		pRoot->data[0] = data;
    46. 		pRoot->count = two_node;
    47. 	}
    48. }
    49.  
    50. template<class T>
    51. void twoThreeTree::_insertNode(Node* node, Node* pParent, const T& data)
    52. {
    53. 	if (null_node == node->count)
    54. 	{//当前节点为空
    55. 		node->data[0] = data;
    56. 		node->count++;
    57. 		return;//注意此处的return 
    58. 	}
    59. 	if (two_node == node->count)
    60. 	{//当前节点为2节点
    61. 		if (data > node->data[0])
    62. 		{//新数据比当前数据大   往右边插入
    63. 			if (node->pArr[1])
    64. 			{//当前节点有右孩子
    65. 				_insertNode(node->pArr[1], node, data);
    66. 			}
    67. 			else
    68. 			{//当前节点没有左孩子
    69. 				node->data[1] = data;
    70. 				node->count++;
    71. 			}
    72. 		}
    73. 		else
    74. 		{//往左边插入
    75. 			if (node->pArr[0])
    76. 			{//当前节点有左孩子
    77. 				_insertNode(node->pArr[0], node, data);
    78. 			}
    79. 			else
    80. 			{//当前节点没有孩子
    81. 				//原来数据往右挪
    82. 				node->data[1] = node->data[0];
    83. 				//新数据进来
    84. 				node->data[0] = data;
    85. 				//节点变化
    86. 				node->count++;
    87. 			}
    88. 		}
    89. 	}
    90. 	else
    91. 	{//当前节点是3节点
    92. 		if (data < node->data[0])
    93. 		{//往最左边插入 图上的情况3
    94. 			if (node->pArr[0])
    95. 			{//有孩子
    96. 				_insertNode(node->pArr[0], node, data);
    97. 			}
    98. 			else{//没有孩子
    99. 				//中间的放右边
    100. 				node->data[2] = node->data[1];
    101. 				//前面的放中间
    102. 				node->data[1] = node->data[0];
    103. 				//新数据放前面
    104. 				node->data[0] = data;
    105. 				//节点变化
    106. 				node->count++;
    107. 			}
    108. 		}
    109. 		else if (data < node->data[1])
    110. 		{//往中间插入 图上的情况2
    111. 			if (node->pArr[1])
    112. 			{//有孩子
    113. 				_insertNode(node->pArr[1], node, data);
    114. 			}
    115. 			else
    116. 			{//没有孩子
    117. 				//中间的放右边
    118. 				node->data[2] = node->data[1];
    119. 				//新数据放中间
    120. 				node->data[1] = data;
    121. 				//节点变化
    122. 				node->count++;
    123. 			}
    124. 		}
    125. 		else{//往右边插入 图上的情况1
    126. 			if (node->pArr[2])
    127. 			{//有孩子
    128. 				_insertNode(node->pArr[2], node, data);
    129. 			}
    130. 			else{//没有孩子
    131. 				//新数据放右边
    132. 				node->data[2] = data;
    133. 				//节点变化
    134. 				node->count++;
    135. 			}
    136. 		}
    137. 	}
    138.  
    139. 	//每次递归回溯的时候,都会检查是否产生了4节点
    140. 	if (four_node == node->count){//如果产生了4节点
    141. 		//1 创建两个节点
    142. 		Node* node1 = new Node;//左
    143. 		Node* node2 = new Node;//右
    144.  
    145. 		//node1是左边的
    146. 		node1->data[0] = node->data[0];
    147. 		node1->pArr[0] = node->pArr[0];
    148. 		node1->pArr[1] = node->pArr[1];
    149. 		node1->count = two_node;
    150.  
    151. 		//node2是右边的
    152. 		node2->data[0] = node->data[2];
    153. 		node2->pArr[0] = node->pArr[2];
    154. 		node2->pArr[1] = node->pArr[3];
    155. 		node2->count = two_node;
    156.  
    157. 		//2 临时存储中间值
    158. 		T temp = node->data[1];
    159.  
    160. 		if (pParent)
    161. 		{//当前节点有父节点
    162. 			//5 找位置 做插入(分为三个位置)
    163. 			if (temp < pParent->data[0])
    164. 			{//左边
    165. 				if (pParent->pArr[2])
    166. 				{//最右边有孩子
    167. 					pParent->data[2] = pParent->data[1];
    168. 					pParent->data[1] = pParent->data[0];
    169. 					pParent->data[0] = temp;
    170.  
    171. 					pParent->pArr[3] = pParent->pArr[2];
    172. 					pParent->pArr[2] = pParent->pArr[1];
    173. 					pParent->pArr[1] = node2;
    174. 					pParent->pArr[0] = node1;
    175. 				}
    176. 				else if(pParent->pArr[1])
    177. 				{//最右边没有孩子，中间有孩子
    178. 					pParent->data[1] = pParent->data[0];
    179. 					pParent->data[0] = temp;
    180.  
    181. 					pParent->pArr[2] = pParent->pArr[1];
    182. 					pParent->pArr[1] = node2;
    183. 					pParent->pArr[0] = node1;
    184. 				}
    185. 			}
    186. 			else if (two_node == pParent->count  ||    //这边利用短路特性
    187. 				(pParent->count > 1)&&temp < pParent->data[1])
    188. 				{//temp需要放中间(因为此层的else if已经避开temp小于第一个元素的情况,那么必定是大于第一个元素，而小于第二个元素)
    189. 				if (pParent->pArr[2])
    190. 				{//最右边有孩子
    191. 					pParent->data[2] = pParent->data[1];
    192. 					pParent->data[1]  = temp;
    193.  
    194. 					pParent->pArr[3] = pParent->pArr[2];
    195. 					pParent->pArr[2] = node2;
    196. 					pParent->pArr[1] = node1;
    197. 				}
    198. 				else if (pParent->pArr[1])
    199. 				{//3节点的最右边无孩子，中间有孩子
    200. 					pParent->data[1] = temp;
    201.  
    202. 					pParent->pArr[2]  = node2;
    203. 					pParent->pArr[1] = node1;
    204. 				}
    205. 			}
    206. 			else if (three_node == pParent->count ||
    207. 				(pParent->count > 2) && (temp < pParent->data[2]))
    208. 			{//右边
    209. 				if (pParent->pArr[2])
    210. 				{
    211. 					pParent->data[2] = temp;
    212. 					pParent->pArr[3] = node2;
    213. 					pParent->pArr[2] = node1;
    214. 				}
    215. 			}
    216. 			pParent->count++;
    217. 			//6 释放内存
    218. 			delete node;
    219. 		}
    220. 		else
    221. 		{//当前节点没有父节点
    222. 			//3 当前节点变成2节点
    223. 			memset(node->data, 0, sizeof(T)* 3);//清空数据
    224. 			memset(node->pArr, 0, sizeof(Node*)* 4);//清空指针
    225. 			node->data[0] = temp;
    226. 			node->count = two_node;
    227. 			//4 node1成为当前节点的左孩子 node2成为当前节点的右孩子
    228. 			node->pArr[0] = node1; node->pArr[1] = node2;
    229. 		}
    230.  
    231. 	}
    232. }

    test：

  • 相关阅读:
    NB的Github项目，看到最后一个我惊呆了！
    【发表案例】网络智能类SCI&EI，仅25天录用，录用后15天见刊，见刊后16天检索
    React报错之React hook ‘useState‘ cannot be called in a class component
    vue2.x版本中computed和watch的使用入门详解-watch篇
    linux安装jdk1.8并启动jar包（又一次配置环境，简单记录下，要是小白，刚接触，按照步骤来即可）
    50、Flink 数据源的事件时间和水印详解
    性能测试面试问题，一周拿3个offer不嫌多
    linux共享文件问题
    Double4 VR智能互动教学应用系统演示
    Oracle EBS form开发 提示 FRM-15500:Valid and unique object name must be entered
  • 原文地址：https://blog.csdn.net/zjjaibc/article/details/126194415