Red Black BST

2020-10-15

Invented the red-black BST. When inserting: Use a red link. If there is a right leaning “3-node”, we have a Left Leaning Violation. Rotate left the appropriate node to fix. // 右子树连续三个节点倾斜，左旋 If there are two consecutive left links, we have an Incorrect 4 Node Violation. Rotate right the

Priority Queue

2020-10-15

To understand this ADT, consider a bag of items. You can add items to this bag, you can remove items from this bag, etc. The one caveat is that you can only interact with the smallest items of this bag.

Data Structures Summary

2020-10-15

summary

B Tree

2020-10-15

所有叶子节点距离根节点一定相同。每个节点有 k 项，一定有 k+1 项叶子节点 B-Tree invariants Because of how we add to our tree, we get two nice invariants for B-Trees: All leaves must be the same distance from the source A non-leaf node with k items mut has exactly k+1

Interface Callback

2020-10-15

Josh 的比喻: 你把电话号码给了他，告诉他你的狗有什么问题就打给你。 max 需要 compare，compare 做了主要工作，是一个 helper function，把

The Rules of Dynamic Method Selection

2020-10-15

Compiler allows memory box to hold any subtype. Compiler allows calls based on static type. Overridden non-static methods are selected at run time based on dynamic type. Everything else is based on static type, including overloaded methods. Note: No overloaded method for problem at left. 强制类型转换会改变 static type(compiler-tyep) 但不会改变 dynamic-type. Object o2 = new show

Java 和 C 参数传递的区别

2020-10-15

Java 与 C 为函数传递数值是相同的，都为复制相同数值至函数，只有返回值会影响原数值。原以为在传递引用类型（地址）时也相同，传递至函数会直接影响原地