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

>我来写笔记

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

  • [已注销]

    [已注销]

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

    2015-10-02 23:51

  • [已注销]

    [已注销]

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

    2015-10-02 18:38

  • 水月痴人

    水月痴人

    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

  • 水月痴人

    水月痴人

    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

  • 水月痴人

    水月痴人

    有N个结点的二叉树具有N+1个null引用,理由: N个结点共有2N个引用,其中有N-1个引用都指向了具体的节点(没有引用指向根节点),所以空引用的个数=2N-(N-1)=N+1. 线索二叉树是利用N+1个结点实现能通过节点的值找到前驱和后继,例如: 具体实现是:如果左节点为空则指向其前驱,右节点为空则指向其后继。 维基百科:http://en.wikipedia.org/wiki/Threaded_binary_tree

    2013-03-12 15:26

  • 水月痴人

    水月痴人

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

    2013-03-12 11:03

  • 水月痴人

    水月痴人

    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

  • 水月痴人

    水月痴人

    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

  • 水月痴人

    水月痴人

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

    2013-03-11 13:53

  • 水月痴人

    水月痴人

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

    2013-03-11 11:38

笔记是你写在书页留白边上的内容;是你阅读中的批注、摘抄及随感。

笔记必须是自己所写,不欢迎转载。摘抄原文的部分应该进行特殊标明。

Data Structures and Algorithm Analysis in Java

>Data Structures and Algorithm Analysis in Java