Status at 20130122

I went through Chapter 6 again.  I still feel some kind of disharmony in it.   Especially when I compare heap with binary tree.  There are something deeply mathematical I don't grok.

But I decide to move on (again).

Browse reading: (2nd time) 170/1144

Exercises up to 6-1.2. (Skipped Chapter 4 and 5)

Revisit : 4.2-{3-5}, 4-4.3 after section 4.5, revisit Chapter 4 and 5
when time allowed.

Checking : up to P2.1

Needs write up: 2-3.7 (nice solution using merging), P2.1c, 3-2.4,
3-2.8, P3.1

Exercises checked: 2.1-2, 2.1-3, 2.2-{1,4}, 2.3-{3,7}

Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3,
P1-1, The whole Section 4.4 except 4.4-3, 4.5-{1,3}, P4.4(a-c), P4.6b,
5.1-{1,2}, whole Section 6.1, 6.2-{1,2,4,5,6}, 6.3-1, 6.4-1 whole
Section 7.1, 7.2-{1-5}, whole Section 7.3 and 7.4.{2,3}, 8.2-1, 8.3-1,
8.3-4, , 10.1-{1-4,6,7}, 10.2-{1,2,6,7}, 12.1-{1,2,3,4}
12.2-{1,2,3,5,6},12.3-{2-4} 12.4-4, P12-1a, P12.4(a),13.2-2, 15-1.1,
15.1-3, 15.3-3, 15.5, 17-1.1, 18.1-1, 18.1-2, 18.2-1, 21-1.1, 21-1.2,
22-1.{1-3,6,7}, 23.1-1 and 23.1-3, P30-1{a,b}, P30-2b, 30-1.1,
31-1.{1-7}, 32.1-{1,2}, A.1-{1,2,3,4,5,7}, C.1-{2,4,5,7,8,9,14},
C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2.

Reread Chapter 12 and 13 again

After rereading the chapter on binary search tree (Chapter 12), I think I finally grok deletion. In fact there are two non-trivial issues of binary search tree, one is to find a successor node when the right node is empty.  (In that case, you are always look for an ancestor whose left child is also an ancestor of the node.

The other is in deletion of a node with two child nodes, you always want to delete the tree-minimum of the right sub tree.  Once these two issues are thought through, you understand all operations of binary trees. (The others are more like simple recursive thinking).

Another good news is that I also reread red-black tree, this time, it starts to make sense on why we have this funny color fix-up algorithm.    The most important is to visualize the two different cases where the red-black properties should be handled.   I don't really grok at this point but I think I understand way more. It is super-complicated but it's also how the thing should work.   I stopped at deletion because it is even more complicated.

It's funny to see the whole business of building a balanced tree is so difficult.  This read is good.  I also finished in my head some exercises.