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

重复的发了一个帖子，不知道怎么删。

好难得啊啊   
AppledeMacBook-Pro-5:hw7 apple$ javac -g dict/*.java
AppledeMacBook-Pro-5:hw7 apple$ java 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
AppledeMacBook-Pro-5:hw7 apple$

交作业～

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

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

就是繁琐，没有难度，耐心分析耐心debug总能做出来

打卡！搞来搞去 做的头晕。。。

作业写了两个多小时，但是debug了将近3个小时…… 确实没有仔细考虑，只把新split的node的child定义了，没有把child的parent指向新node。

C:\Users\Kuo Pei\Desktop\Homework and Projects\hw7\screenShotOfResult\Untitled picture.png
终于做完了，感觉这个还是挺耗时间的，由于题中的node没有使用数组，所以每种节点情况都得分开写，开头那里newRoot也是单独写的，感觉这样浪费了好多时间，准备再去查查其他人写得更好的实现方法/
不过，需要注意的一点是：1、处理一切这种双向节点链接的问题时，都应该注意把两头连在一起，不能只连一端；
2、在开始编码之前，手动从头实现一下数据结构，有利于深入理解，梳理各个步骤；
3、复杂的数据结构实现时，依照top-down的设计模式，先写好最顶层接口，再逐层细分任务；
4、ADT的invariants是由fields与methods共同维护的;类似child n<key n+1 <child n+1这种关系：在node的class中仅需保证每个节点是两组升序排列的key和child，而insert() method人为保证了两个序列元素之间的大小关系正确。在本题234树中，method的作用更大一些。