Introduction to Algorithms 3rd Edition
Part III - Data Structures
Chapter 12: Binary Search Trees
树在数据结构中是非常重要的，而二叉树又是应用最多的，重要性不言而喻。在二叉排序树中，对每个节点，其左子树中节点的值比它小，右子树中节点的值比它大，左右子树都是一棵二叉排序树。平均而言，二叉排序树具有非常均衡的插入、删除和查找性能，都是O(h)，因而备受亲睐。
对二叉排序树，查找和插入比较简单，删除稍微复杂：如果左子树和右子树至少有一个空，那么很简单；如果两个子树都不为空，那么需要找到待删除节点的后继，这时又有两种情况，该后继或者是待删除节点的右孩子，或者不是，如果不是的话多一步操作。其实也是比较简单的，画个图就能理解了，但是指针的修改要特别注意，否则很容易出错。
Exercises
12.1-2
BST中左孩子的值小于节点小于右孩子，而小顶堆中节点的值小于左子树和右子树。
当然不行了，如果可以的话，堆排序的时间复杂度就变成O(n)了，而我们知道这是不可能的……
12.1-3
一种方法是用栈。
另外一种方法的思路是：首先遍历左子树，根据之前访问的节点判断当前应该执行的操作。如果之前访问的是父节点，那么就应该先打印左子树；如果之前访问的是左孩子，那么就应该返回父节点并打印父节点，然后转向右子树；如果之前访问的是右孩子，那就应该返回父节点。因此，代码如下：
1 void inorder_walk_nonrecursive_nostack(Node *t)
2 {
3 Node *prev = NULL;
4 Node *curr = t;
5 Node *next = NULL;
6 while (curr != NULL) {
7 if (prev == curr->parent) {
8 next = curr->left;
9 if (next == NULL) {
10 print(curr);
11 next = curr->right;
12 if (next == NULL)
13 next = curr->parent;
14 }
15 } else if (prev == curr->left) {
16 print(curr);
17 next = curr->right;
18 if (next == NULL)
19 next = curr->parent;
20 } else {
21 next = next->parent;
22 }
23 prev = curr;
24 curr = next;
25 }
26 }
12.1-4
太简单了
12.1-5
因为中序遍历BST只需要O(n)的时间，因此构造至少需要Omega(nlgn)的时间，否则基于比较的排序就能在少于O(nlgn)的时间内完成了。
12.2-4
5(1(#, 3(2, 4)), #)
检索4时，搜索路径是5->1->3->4，因此A = {2}, B = {1, 3, 4, 5}, C为空，显然A中的2比B中的1要大
12.2-5
根据定义，显然的
12.2-7
每条边最多遍历两次，而边数是n-1，因此时间复杂度是O(n)
12.3-2
检索时还得比较插入的节点，所以多一次
12.3-3
最坏情况就是原数组有序，复杂度是O(n^2)；最好情况是随机，树的高度是lg(n)，复杂度是O(nlgn)
12.3-4
5(2(1, 4(3, #)), #), 删除1后变成5(2(#, 4(3, #)), #)，再删除2变成5(4(3, #), #)。如果先删除2则变成5(3(1, 4), #)，再删除1变成5(3(#, 4), #)。删除的顺序不同导致最后的树不同
12.4-3
当n=3时，排列共有6种：123, 132, 213, 231, 312, 321，建树之后分别为：1(#, 2(#, 3)), 1(#, 3(2, #)), 2(1, 3), 2(1, 3), 3(1(#, 2), #), 3(2(1, #), #)，其中树一共只有5种，所以随机选一种BST的话概率是1/5，但是随机选择一种输入构建BST的话，生成2(1, 3)的概率是1/3，其它4种的概率是1/6。因此二者是不同的。
Problems
12-2
将S中的字符串逐个插入到radix tree中，复杂度与字符串长度成正比，为O(n)，之后先序遍历radix tree，碰到表示字符串的节点就输出，遍历的边数最多为字符串总长的两倍，因此复杂度仍为O(n)，因此排序的复杂度就是O(n)
12-4
这个其实就是Catalan数的小例子，接下来要专门分析一下Catalan数及其广泛的形式，可以参考http://en.wikipedia.org/wiki/Catalan_number
No comments:
Post a Comment