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

好久没交作业了，还有一个月就要开学了，完蛋，担心找不到实习了5555555555

终于写完了，心累，题目一开始理解错，几乎重写了一遍，

顺利完成，交作业。稍微繁琐一点，细心就好。不过remove估计不容易。。。

零基础还是痛苦唉，做了好久，继续坚持！

写了一个小时，debug目测接近两个小时，不过做出来的一下还是很开心的。对于BST究其原理确实简单，但是真正要实现还是得费一番功夫。
看了一下大家的回复，原来我们遇到的是同一个问题。。。。就是更新了爹之后儿子还得认爹的意思。。。。

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)))

卧槽 辛辛苦苦打了那么多. 转换成高级模式就没了..

嗯 逻辑不难

首先考虑循环(node!=null)
1.拆分3个keys的node
  1.1 考虑当前node是root
  1.2 考虑当前node是非root
      考虑node的keys都怎么插入其parent
         1.2.1 考虑parent的keys数
         1.2.2 考虑当前node属于parent 哪个child
   都需要考虑node是否有后代. 如果有的话,要将4个child 新建的左右两个node下
2. 考虑node的key是否和插入key相同 如果相同则直接返回
3. 如果既不是3keys的node,也不相同, 则考虑去下一层,直到node=null,在去下层之前标记下nodeParent, 毕竟等到node=null的时候,就不好用node.parent这个指令了

循环结束后 就找了需要插入的node了. 那么直接插入就好.

全程需要考虑的更新keys数 和 size(有时是一下加两个)

唯一的一个失误是  我以为 A指向B, B指向C. 然后B改成指向D, A也会跟着改变成指向D...结果发现A还是指向C.... 感觉自己基础还是不太牢固

Debug了三个多钟头。。。尼玛恶心死我了

呼，这次的作业还是有点麻烦，虽然结果跑出来了，但是代码乱七八糟，还要好好再整理一下