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

懒得整个截下来了 确实挺麻烦的 做了一个早上
我觉得最难的地方是，三个keys的node更新了以后，就算他连接了原来的child1~4，还要把那些child的parent连接到新的node上。。。
另外每次重新连接的时候还要考虑child!=null

三年多了，看到这个贴子还有人顶，真是不容易，祝大家都有大OFFER拿

hw7打卡

图片添加的有点丑陋。。。这次作业写的bug满地飞，花了很久debug..

最後在三個key的child.parent上卡了一下
解了

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

复制代码

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南

"C:\Program Files\Java\jdk-9.0.1\bin\java" "-javaagent:D:\Program Files\JetBrains\IntelliJ IDEA Community Edition 2017.3.2\lib\idea_rt.jar=51494:D:\Program Files\JetBrains\IntelliJ IDEA Community Edition 2017.3.2\bin" -Dfile.encoding=UTF-8 -classpath "D:\GitHub\CS61b-Berkeley\out\production\Homework 7" dict.Tree234

Inserting 84.
84

Inserting 7.
7 84

Inserting 22.
7 22 84

Inserting 95.
(7)22(84 95)

Inserting 50.
(7)22(50 84 95)

Inserting 11.
(7 11)22(50 84 95)

Inserting 37.
(7 11)22(37 50)84(95)

Inserting 60.
(7 11)22(37 50 60)84(95)

Inserting 1.
(1 7 11)22(37 50 60)84(95)

Inserting 23.
(1 7 11)22(23 37)50(60)84(95)

Inserting 16.
((1)7(11 16)22(23 37))50((60)84(95))

Inserting 100.
((1)7(11 16)22(23 37))50((60)84(95 100))

Inserting 28.
((1)7(11 16)22(23 28 37))50((60)84(95 100))

Inserting 86.
((1)7(11 16)22(23 28 37))50((60)84(86 95 100))

Inserting 49.
((1)7(11 16)22(23)28(37 49))50((60)84(86 95 100))

Inserting 81.
((1)7(11 16)22(23)28(37 49))50((60 81)84(86 95 100))

Inserting 51.
((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86 95 100))

Inserting 99.
((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86)95(99 100))

Inserting 75.
((1)7(11 16)22(23)28(37 49))50((51)60(75 81)84(86)95(99 100))

Inserting 66.
((1)7(11 16)22(23)28(37 49))50((51)60(66 75 81))84((86)95(99 100))

Inserting 4.
((1 4)7(11 16))22((23)28(37 49))50((51)60(66 75 81))84((86)95(99 100))

Inserting 80.
(((1 4)7(11 16))22((23)28(37 49)))50(((51)60(66)75(80 81))84((86)95(99 100)))

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

Process finished with exit code 0

原来和大家遇到的都是同一个问题，new 节点 的child的parent指向。
另外感觉代码重复很厉害，已经把一部分重复代码写成了method，不过分类讨论好像又少不了（3-node是不是root, 是第几个child，它的parent的keys == 1 OR 2），最后插值时又要对当前节点分类讨论。if else遍地。精简的空间还是挺大的

Inserting 84.
84

Inserting 7.
7 84

Inserting 22.
7 22 84

Inserting 95.
(7)22(84 95)

Inserting 50.
(7)22(50 84 95)

Inserting 11.
(7 11)22(50 84 95)

Inserting 37.
(7 11)22(37 50)84(95)

Inserting 60.
(7 11)22(37 50 60)84(95)

Inserting 1.
(1 7 11)22(37 50 60)84(95)

Inserting 23.
(1 7 11)22(23 37)50(60)84(95)

Inserting 16.
((1)7(11 16)22(23 37))50((60)84(95))

Inserting 100.
((1)7(11 16)22(23 37))50((60)84(95 100))

Inserting 28.
((1)7(11 16)22(23 28 37))50((60)84(95 100))

Inserting 86.
((1)7(11 16)22(23 28 37))50((60)84(86 95 100))

Inserting 49.
((1)7(11 16)22(23)28(37 49))50((60)84(86 95 100))

Inserting 81.
((1)7(11 16)22(23)28(37 49))50((60 81)84(86 95 100))

Inserting 51.
((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86 95 100))

Inserting 99.
((1)7(11 16)22(23)28(37 49))50((51 60 81)84(86)95(99 100))

Inserting 75.
((1)7(11 16)22(23)28(37 49))50((51)60(75 81)84(86)95(99 100))

Inserting 66.
((1)7(11 16)22(23)28(37 49))50((51)60(66 75 81))84((86)95(99 100))

Inserting 4.
((1 4)7(11 16))22((23)28(37 49))50((51)60(66 75 81))84((86)95(99 100))

Inserting 80.
(((1 4)7(11 16))22((23)28(37 49)))50(((51)60(66)75(80 81))84((86)95(99 100)))

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

继续学习，发现编程真的是很强调逻辑。首先Track down the whole tree, split 3-key node into 2 node, move the middle element to the parent node. If the parent node is null, then creat a new one.  针对node上keys 的数量进行分类讨论，同时设置position变量用于判断key的插入位置。如果position==0，则插入第一位，以此类推。