[公开课] Berkeley CS 61B Data Structures(in Java) Homework7 加分+讨论帖

感觉代码重复量有点高，已经特意把几个重复的多的写成method了，但感觉还是很难避免大量的if else。
我重写了一个 insert（Tree234Node node, int key)的方法然后用recursive的方法实现，debug的时候要舒服很多。

1. Inserting 84.
   
2. 84
   
3. 
   
4. Inserting 7.
   
5. 7 84
   
6. 
   
7. Inserting 22.
   
8. 7 22 84
   
9. 
   
10. Inserting 95.
    
11. (7)22(84 95)
    
12. 
    
13. Inserting 50.
    
14. (7)22(50 84 95)
    
15. 
    
16. Inserting 11.
    
17. (7 11)22(50 84 95)
    
18. 
    
19. Inserting 37.
    
20. (7 11)22(37 50)84(95)
    
21. 
    
22. Inserting 60.
    
23. (7 11)22(37 50 60)84(95)
    
24. 
    
25. Inserting 1.
    
26. (1 7 11)22(37 50 60)84(95)
    
27. 
    
28. Inserting 23.
    
29. (1 7 11)22(23 37)50(60)84(95)
    
30. 
    
31. Inserting 16.
    
32. ((1)7(11 16)22(23 37))50((60)84(95))
    
33. 
    
34. Inserting 100.
    
35. ((1)7(11 16)22(23 37))50((60)84(95 100))
    
36. 
    
37. Inserting 28.
    
38. ((1)7(11 16)22(23 28 37))50((60)84(95 100))
    
39. 
    
40. Inserting 86.
    
41. ((1)7(11 16)22(23 28 37))50((60)84(86 95 100))
    
42. 
    
43. Inserting 49.
    
44. ((1)7(11 16)22(23)28(37 49))50((60)84(86 95 100))
    
45. 
    
46. Inserting 81.
    
47. ((1)7(11 16)22(23)28(37 49))50((60 81)84(86 95 100))
    
48. 
    
49. Inserting 51.
    
50. ((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86 95 100))
    
51. 
    
52. Inserting 99.
    
53. ((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86)95(99 100))
    
54. 
    
55. Inserting 75.
    
56. ((1)7(11 16)22(23)28(37 49))50((51)60(75 81)84(86)95(99 100))
    
57. 
    
58. Inserting 66.
    
59. ((1)7(11 16)22(23)28(37 49))50((51)60(66 75 81))84((86)95(99 100))
    
60. 
    
61. Inserting 4.
    
62. ((1 4)7(11 16))22((23)28(37 49))50((51)60(66 75 81))84((86)95(99 100))
    
63. 
    
64. Inserting 80.
    
65. (((1 4)7(11 16))22((23)28(37 49)))50(((51)60(66)75(80 81))84((86)95(99 100)))
    
66. 
    
67. Final tree:
    
68.                100
    
69.                99
    
70.           95
    
71.                86
    
72.      84
    
73.                81
    
74.                80
    
75.           75
    
76.                66
    
77.           60
    
78.                51
    
79. 50
    
80.                49
    
81.                37
    
82.           28
    
83.                23
    
84.      22
    
85.                16
    
86.                11
    
87.           7
    
88.                4
    
89.                1
    
90. 
    
91. Process finished with exit code 0

复制代码

交作业了~
总的来说这次作业考虑的条件很多，但实际上其实难度不太大，这次忽略的一点是在给同level的节点分配完child后，忘了将child的parent指定为新的节点

折腾好久才debug完毕，之前设置好node.child后，忘记设置child.parent，导致一直不对

分类讨论到天荒地老。。。不知道有没有优化的方法TAT

Final tree:
               100
               99
          95
               86
     84
               81
               80
          75
               66
          60
               51
50
               49
               37
          28
               23
     22
               16
               11
          7
               4
               1

tree's size: 22

渣渣只能靠参考别人的代码运行成功 下面是我本次运行成功参考的文章以及code

1.https://blog.csdn.net/qy844083265/article/details/80716065
2.https://github.com/convexshiba/C ... 7/dict/Tree234.java

有个注意的地方是1中博客中的说法当我们要split一个3keys结点的时候，要去除原结点中的被移到其他节点中的key，
但是在2中code没有做移除的操作，只有一个keys=1；这让我一度认为2中code存在问题，后来发现
readme.pdf中有一段话解释了为什么在本次hw中不需要这样处理   The "keys" field is the number of keys stored in the node, and must be 1, 2, or
3.  The fields "key1", "key2", and "key3" are filled in (in order) with the int
keys stored in the node.  If keys == 1, the value of key2 doesn’t matter.  If
keys <= 2, the value of key3 doesn’t matter.  
还需要好好理解一下整个思路，妈耶，写个insert都这么费力了，要是手写remove，原地去世。

debug真的弄了很久，前前后后大概搞了4、5个小时1. 时间主要花忘了新的node的parent指针，而且每个单独的情况居然都为这个专门debug了一下，脑子又在偷懒，应该想到其他也会有类似情况，而不是改一点是一点。。。

2. 分类写的很繁琐，一方面要精简，另一方面有同学指出是有recursive的方法的，等刷题再来看好了，先赶赶进度。。。
3. 还有一个是我对insert的逻辑理解不太到位，一开始我以为在find的过程中，一遇到3个node的就拆，然后相应代码跟test code就不对，可是不然到了该插key的地方eject上去parent如果本来有3个就又爆了。。。我总觉得我的想法比较符合lecture notes，它说“Specifically, whenever insert() encounters a 3-key node, the middle key is ejected, and is placed in the parent node instead. Since the parent was previously treated the same way, the parent has at most two keysand always has room for a third.” 我最后改了一下是可以过testcode，但感觉如果遇到parent再爆好像就不行了。。。好想知道大家怎么处理的呀～～～～

附上截图：

花了三个小时，一个小时写，两个小时debug（手动微笑）

主要考验的是对数据结构的熟悉以及特殊情况的分析：

只说特殊情况吧，主要有三点值得注意的地方：
1、当root有三个key和当non-root 有三个key时有不同的解法，前者是root中间的key 不变，将两边的key各新创建一个node（left和right）；后者是 将node中间的key2提到parent里，因为parent也是这么处理的，所以parent最多有两个key，可以有一个空位给key2插。【但是插完后parent有三个key了】只新创建一个node即可。

2、root的parent问题，假设我们depth+1，那么原来root里面的child1-4（如果不是null的话）分别分配给新创建的left和right。但是它们的parent变量指向的还是原来的root，所以要重新分配。

3、有点迷糊的一个点，也是花时间最长的一个地方在于【restructure的顺序和insert判断的顺序之间的关系】。比如说从root出发，一路上遇到三个key的进行restruct，然后在进行判断要insert的key应该在哪个child方向走。但是注意这时node所在的中间点已经upstair到它的parent了，所以我们如果进行了restructure，我们要使node=node.parent。回到parent重新选择要走的方向，直至到leaf。（insert一定在leaf上，restructure的目的就是确保我们插入leaf的时候，有空位给我们插）

3.1、这里有一个很特殊的情况在于如果parent原来有两个，restruct后变成了三个key。而我们回滚到parent判断时要插入的key比这三个key都大，因此我们要走child4，这个child4是必有的。（因为我们刚在下面restruct，原来有三个child，新建了个就是四个child）

呀 写完啦！ 如图！一直在坚持的做 但发了hw1发现现在不加学分了 所以后面的几个就都没有传了，这次的这个搞了快两个小时，纪念一下~