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

作业入口：  http://www.cs.berkeley.edu/~jrs/61b/hw/hw7/

折滕234Tree
不是很好写，总是会犯小错误，后来也是请教了一下高人才弄好

完整的输出如下：

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

终于成功了。。求学分

画图是解决树和图类问题最好的办法~
这题的关键是理解每次遇到 3-key-node之后怎么处理，处理的过程中考虑各种情况，千万注意设置child的同时也要设置parent，同时不要忘记考虑root的情形~

真的debug了好久。。
虽然问题只要求写出insert函数，而不需要写出remove函数，但是工作量依然挺大的。
犯的错误主要是在给一个TreeNode增加child时没有相应地把child的parent改为这个TreeNode。

极其恶心
https://www.1point3acres.com/bbs/forum.php?mod=attachment&aid=MjYyNjY5fDJiMjMwMjJkZDIwNmY4MDczODU1MmExYjViNTQyZGFkfDE3ODgzMzE1MzU%3D&request=yes&_f=.pngattach://262670.pnghttps://www.1point3acres.com/bbs/forum.php?mod=attachment&aid=MjYyNjcxfGUwYjFjN2FiMTFhY2I4YzJhMjE0ZjhmZTJlMGM3MjFhfDE3ODgzMzE1MzU%3D&request=yes&_f=.png

马上开学了，估计是弄不完了

好复杂啊，光是拆那个3 key node就把我搞得头晕了。

这次作业，逻辑不难，主要难在debug，太多小地方需要注意了。 debug了太长时间了。 争取这个月把其他作业全部攻破，坚持住。

这次作业不难！只要注意各节点之间的连接是双向的，注意改好往回的引用即可！
各位加油！

不知道这次作业大家写了多久，本人用了2小时。。而且代码不美观。不知道什么水平。。10分钟的大神有木有。。

还是应该把作业做完，有始有终。

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

弱弱的问一下，insert的时候，如果node的keys(key number)已经是3了，但是insert的key刚好又和key1,key2,key3其中一个match了，那么还需要eject middle key吗？