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

交作业，还能拿得到学分吗、

我都不好意思说自己折腾了三天……

这次作业不难 还是花了一个晚上加半个上午  感觉自己代码编的不太好 导致了一堆bug  特别是if我的条件取得不好  在嵌套的过程中一个if结束后 我本来想跳出这个if 但经常进入了下个if语句里 导致一些无厘头的错误。
自己定义了三个方法   findsubtree（迭代用的，类似于find）   split1st split2nd（这俩是用来把3个的节点变成俩，注意child的选取，要考虑child是否为null，这样null.parent就会报错）
感觉用的打印的方法还是很厉害的  这次的tostring和lab10的tostring代码感觉不错。
Inserting 84.
84

Inserting 7.
7 84

Inserting 22.
7 22 84

Inserting 95.
84 0 0 1
84 0 0 1
(7)22(84 95)

Inserting 50.
84 95 0 2
84 95 0 2
yues
(7)22(50 84 95)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Inserting 80.
84 0 0 1
60 0 0 1
66 75 81 3
81 0 0 1
(((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

交作业。
谢天谢地不用写remove

多发了一楼，版主删除吧。

图太长了不好截，直接复制了
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



话说好像不加分了诶，连续三个作业没给分了

自己加了size的测试。

有一点注意的是，key总是从leaf node插入。

加一段自己写的insert的algorithm分析。

1. <div>   *  The basic algorithm is that while traversing the tree, whenever a 3-key</div><div>   *  node is encountered, kicking the middle key to the node's parent. And</div><div>   *  the traversal starts from its parent. Becasue of this algorthim, it can be</div><div>   *  guranteed that (1) there is room for the new key in the lead node. The</div><div>   *  new key is always inserted into a leaf node. (2) there is room for a</div><div>   *  middle key to be inserted into a node's parent.</div>

复制代码

难点在于３-entries node restructure，包括２种情况：（１）root; （２）internal node;
设置child的同时，不能忘记设置相应的parent.

逻辑不难但很繁琐，写了一下午。最终遇到一个终极大bug。。。怎么从debug模式里看最后的树的节点都是对的，但是printTree出来就错了。。有人遇到一样的问题吗？基础差真是没办法了。。