代码实现参见github/algorithm中各个类别下wz包中的代码。
1.数据结构中常犯错误
1.14 二叉查找树
- 28）对于指针类型的数据结构一定要画图
通过画图整理好各个结点之间关系的变化 - 29）对于复杂的操作
先理清思路，写出完整操作步骤，再写代码，然后再进行优化合并。
1.15 红黑树——最复杂的数据结构
- 30）忘了更新size
- 31）对算法的理解，尤其是当结点为null结点时，此时null结点被当作什么至关重要，因为《算法导论》算法假设是null结点有作用的！这个处理参考parentOf()、leftOf()、rightOf()、colorOf()
- 32）中间容易忘记对结点是否为null进行判断
- 33）leftRotate()、rightRotate()少了更新xy这一对关系
- 总结：对于极其复杂的数据结构，建议做到如下几点来控制复杂度
a.定义清楚算法各种状态含义、前置条件和后置条件
b.用注释+部分的方式（更新size等状态）勾勒出代码骨架
c.对代码功能进行模块化拆分
d.对于链式结构，一定要画图，并检查各修改结点的各状态是否正确被赋值
1.16 跳表
- 34）将rnd >>>=1错写成rnd>>>1，导致死循环
- 35）for循环精心的控制，注意要防止null
for (Index<K,V> prev = head; prev != null; prev = prev.down) {
// 这一句不能放在for循环更新语句中，只能放在这里，因为prev可能为null，所以只有检查完之后才能赋值
Index<K,V> right = prev.right;
1.17 trie树
- 36）while循环更新变量时，有两个变量需要更新，少更新一个人
- 37）delete递归方法，后置条件需要定义清楚：结点置为null的充要条件是：value为null且所有孩子结点为null
1.18 三向trie树
- 38）keysWithPrefix()方法，prefix本身忘记处理
// prefix本身忘记处理
if (node.value != null) {
results.add(prefix);
}
