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

debug 真心不容易

太恶心了。。。。觉得自己很多地方代码重用的非常厉害，即使不是直接重用，样子也很像；但是这个规律又没有强到能写出可复用结构。。。

14 spring 课上JRS说这样top down 比 bottom up要快一些；我觉得未必：
Asymptotically 是一样的：
－top down一路下来直接是logn； bottom up是先直插下来再往上调整，相当于走两趟logn， 两个都是O(logn)的；
况且：
－我觉得top down的每一步操作要复杂的多，那这样两者还指不定谁快呢。。

终于debug 成功。。。。


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
               100
               99
          95
               86
               81
               80
          75
               66
          60
               51
               49
               37
          28
               23
     22
               16
               11
          7
               4
               1

感觉这次作业是在干体力活。。求加分呀，最近这两次作业都没分加的？

必须要纪念一下这场史诗级的debug战役
感觉自己的代码很丑很啰嗦，，Anyway坚持～

改完上来吐槽一下，难怪hw7就一个question....真是史上最恶心的一道题

不是很难的一次作业，当keys =3的时候还是有点绕，会犯一些小错误
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

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

确实是要记得把child的parent改为新生成的node。

交作業
(私心覺得透過寫作業學習這門課才知道在學甚麼, 尤其是非本科生Orz)