# Data Structures and Algorithm Analysis in Java的笔记(10)

## 按有用程度按页码先后最新笔记

• ### 展开 收起 第314页

在Figure 7.25 Radix sort for variable length strings中最开始使用了下面几行代码: /代码内容已省略/ 但是在Java中是不允许建立泛型数组的，因为数组是具体化的，而泛型是非具体化的，不能混合使用，具体可以参考Effective Java Second Edition的第25条：列表由于数组。 因此可以写成下面这样： /代码内容已省略/ 因为Java中的泛型是类...

2015-10-02 23:51

• ### 展开 收起 第327页

Gonet and Baeza-Yates[5] 应该改为[8]。标注出现错误。

2015-10-02 18:38

• ### 展开 收起 第229页

Heap-order definition: In a heap, for every node X, the key in the parent of X is smaller than (or equal to) the key in X, with the exception of the root (which has no parent).

2013-03-25 10:28

• ### 展开 收起 第194页

Theorem 5.3. If N items are placed into a primary hash table containing N bins, then the total size of the secondary hash tables has expected value at most 2N. 这个定理的证明没怎么看懂，证明如下：

2013-03-15 16:34

• ### 展开 收起 第166页

2013-03-12 15:26

• ### 展开 收起 第153页

Java API中的TreeSet是有序地进行存储的，TreeMap也是（根据Key的值进行排序）。 两者都是通过平衡的二叉查找树来实现的（balanced binary search tree），实现方式不是AVL Trees，而是通过自上而下的红黑树(Top-Down Red-Black Tree)来实现。

2013-03-12 11:03

• ### 展开 收起 第152页

A B-tree of order M is an M-ary tree with the following properties: 1. The data items are stored at leaves. 2. The nonleaf nodes store up to M âˆ’ 1 keys to guide the searching; key i represents the smallest key in subtree i + 1. 3. The root is either a leaf or has between two and M children. 4. All nonleaf nodes (except the root) have between M/2 and M children. 5. All leaves are at the ...

2013-03-11 18:21

• ### 展开 收起 第125页

Let us call the node that must be rebalanced α. Since any node has at most two chil- dren, and a height imbalance requires that α’s two subtrees’ height differ by two, it is easy to see that a violation might occur in four cases: 1. An insertion into the left subtree of the left child of α. 2. An insertion into the right subtree of the left child of α. 3. An insertion into the left su...

2013-03-11 14:32

• ### 展开 收起 第137页

Splay Tree的基本思想是不保证每次插入的时间复杂度为O(logN),但是保证M次操作的时间复杂度不大于Mlog(N)，即是平均时间复杂度为O(logN)。

2013-03-11 13:53

• ### 展开 收起 第123页

AVL Trees的基本思想是保持任何二叉树的任何一颗子树的左右子树的深度差不超过1，以此来平衡二叉树的左右深度和节点数。保证这些的方式是通过Single Rotaion和Double Rotation。

2013-03-11 11:38