Advertisement
Guest User

Untitled

a guest
Jul 19th, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.19 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.List;
  4.  
  5. /**
  6. * 2-3树实现/仅供学习使用
  7. *
  8. * @author yangtianrui
  9. */
  10. public class TwoThreeTree {
  11.  
  12. public static void main(String[] args) {
  13. TwoThreeTree tree = new TwoThreeTree();
  14. tree.put(1);
  15. tree.put(2);
  16. tree.put(3);
  17. tree.put(4);
  18. tree.put(5);
  19. tree.put(6);
  20. tree.put(7);
  21. tree.put(8);
  22. tree.put(9);
  23. }
  24.  
  25.  
  26. /**
  27. * 2-3树节点,这里把2-节点和3-节点都放在一起了
  28. */
  29. private static class Node {
  30.  
  31. private Node parent = null;
  32. // 该节点保存的数据
  33. private final List<Integer> keys = new ArrayList<>();
  34. // 子节点
  35. private final List<Node> children = new ArrayList<>();
  36.  
  37. /**
  38. * 向节点中插入元素,2-3树无法向下增长,需要在当前节点插入后向上分裂
  39. *
  40. * @param num
  41. */
  42. public void insert(int num) {
  43. keys.add(num);
  44. Collections.sort(keys);
  45. }
  46.  
  47. public boolean isLeaf() {
  48. return children.isEmpty();
  49. }
  50.  
  51. /**
  52. * 需要分裂
  53. *
  54. * @return true/false
  55. */
  56. public boolean needSplit() {
  57. return keys.size() > 2;
  58. }
  59.  
  60.  
  61. @Override
  62. public String toString() {
  63. return "Node{" +
  64. "keys=" + keys +
  65. '}';
  66. }
  67. }
  68.  
  69. private Node mRoot;
  70.  
  71. public TwoThreeTree() {
  72. }
  73.  
  74.  
  75. /**
  76. * 向2-3树中插入节点
  77. *
  78. * @param key key
  79. * @return true 成功 false 失败
  80. */
  81. public boolean put(int key) {
  82. if (mRoot == null) {
  83. mRoot = new Node();
  84. mRoot.insert(key);
  85. return true;
  86. }
  87. final Node insertNode = findInsertNode(mRoot, key);
  88. if (insertNode == null) {
  89. return false;
  90. }
  91. insertNode.insert(key);
  92. if (insertNode.needSplit()) {
  93. split(insertNode);
  94. }
  95. return true;
  96. }
  97.  
  98. /**
  99. * 当前节点向上分裂,2-3树保持平衡的核心
  100. *
  101. * @param pivot 需要分裂的节点
  102. */
  103. private void split(Node pivot) {
  104. if (pivot == null) {
  105. return;
  106. }
  107. Node parent = pivot.parent;
  108. // 中间键
  109. int middle = pivot.keys.get(1);
  110. // 新分裂的节点
  111. Node n2 = new Node();
  112.  
  113. // 开始分裂
  114. if (pivot.isLeaf()) {
  115. /*
  116. 此时是叶子节点分裂,初始分裂状态一定是根节点
  117. */
  118.  
  119. // n2 获取右键
  120. n2.keys.add(pivot.keys.get(2));
  121. // 原节点删除右键和中键
  122. pivot.keys.remove(2);
  123. pivot.keys.remove(1);
  124. } else {
  125. /*
  126. 此时是中间节点分裂,这个状态一般是叶子节点分裂完后出现的。
  127. */
  128.  
  129. // n2 获取后两个键,注意添加顺序
  130. n2.children.add(pivot.children.get(2));
  131. n2.children.add(pivot.children.get(3));
  132.  
  133. // 删除两个孩子
  134. pivot.children.remove(3);
  135. pivot.children.remove(2);
  136.  
  137. n2.keys.add(pivot.keys.get(2));
  138. n2.children.get(0).parent = n2;
  139. n2.children.get(1).parent = n2;
  140.  
  141. // 原节点删除右键和中键
  142. pivot.keys.remove(2);
  143. pivot.keys.remove(1);
  144. }
  145.  
  146. // 分裂根节点
  147. if (parent == null) {
  148. mRoot = new Node();
  149. mRoot.parent = null;
  150. mRoot.children.add(pivot);
  151. mRoot.children.add(n2);
  152.  
  153. // root 节点取中间键
  154. mRoot.keys.add(middle);
  155. pivot.parent = mRoot;
  156. n2.parent = mRoot;
  157. } else {
  158. // 把当前分类的n2插入到父节点的孩子节点中
  159. int indexInParent = pivot.parent.children.indexOf(pivot);
  160. pivot.parent.children.add(indexInParent + 1, n2);
  161. pivot.parent.insert(middle);
  162. n2.parent = parent;
  163. if (parent.needSplit()) {
  164. split(parent);
  165. }
  166. }
  167.  
  168. }
  169.  
  170. /**
  171. * 根据当前key查找到应该插入的位置
  172. *
  173. * @param start 初始节点
  174. * @param key key
  175. * @return null key已经存在/Node 可以在此插入
  176. */
  177. private Node findInsertNode(Node start, int key) {
  178. if (mRoot == null) {
  179. return null;
  180. }
  181. if (start.keys.contains(key)) {
  182. return null;
  183. }
  184. if (start.isLeaf()) {
  185. return start;
  186. }
  187. int keyCount = start.keys.size();
  188. if (key < start.keys.get(0)) {
  189. // 查找左节点
  190. return findInsertNode(start.children.get(0), key);
  191. } else if (key > start.keys.get(keyCount - 1)) {
  192. // 查找右节点
  193. // 根据2-3树的定义,右节点一定是keyCount
  194. return findInsertNode(start.children.get(keyCount), key);
  195. } else {
  196. // 查找中间节点
  197. // 这个时候1代表的是2-3树的中间节点
  198. return findInsertNode(start.children.get(1), key);
  199. }
  200. }
  201.  
  202. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement