172 Lectures

Questions

What's a double rotation?
What are examples of rotations with real nodes and arcs, not triangles?
What's wrong with Figs 4.35, 4.36 (double rotation with triangles) anyway?
How know which of the four rotation cases we're in?
How keep track of heights?
Wouldn't it be easier to look at the code directly? Maybe easier than English? Or pictures?

What's a double rotation?

Literally it is two single rotations performed on three consecutive nodes k3, k1, k2 (headed down a path from the root) to address imbalance in the top node k3. k2 winds up a new subtree root with k1 and k3 the roots of k2's left and right subtrees. Weiss's labeling of these k's may not be consistent....

Generally, we recall that imbalance from insertion into subtrees A or D can be dealt with by a single rotation. We saw why that won't fix that problem arising from insertion into B or C.

The figure below shows cases 1, 2, 3, 4: balance condition ruined by insertion into A, B, C, D respectively.

What's wrong with Figs 4.35 and 4.36?

It's meant to show double rotation caused by insertion into B that causes an imbalance condition at k3. It's badly drawn. The k1-k3 circles aren't lined up with the arrows, nor are the tops of the triangles for subtrees A-D. There aren't enough levels, AND finally subtree B, which insertion has made too deep, should be shown with a level more altitude, not the same height as others.

Double rotations with nodes and arcs

Weiss goes thru a long sequence of insertions, with figures and commentary, in the book. Here, we see two double rotations and a single.

Another single shown, another couple suppressed, we get to last insertion of 9, causing a double rotation because of an imbalance condition at 13.

Above k3 is 10, k1 is 8, k2 (sketchy) is the 9 we insert as 8's R. child. Below is the result of the double rot.

How know which case we're in?

That is, which of the four cases (just inserted into A, B, C, or D) below are we in?

This decision, along with balancing itself, is done by Weiss's balance method (Fig. 4.39, p. 134).

Given you've found a height imbalance at node t, use subtree heights to figure which side is bigger, (determines cases 1 or 2 vs 3 or 4). then look at sub-subtree heights (e.g. height(t.left.left) vs height(t.left.right) to pick between the remaining two cases (single or double rot.).

How keep track of heights?

Only need to update tree heights on a path from the insertion point back up to root. The depths of other trees may change but not their heights.

Weiss manages the operations like this in Fig. 4.39:
insert recursively calls itself on the left or right subtree of the current node it's considering until it finds the null pointer. The base case is to return a newly-created node with the inserted value in it.

In the recursive case, after every call to insert and before returning, the tree whose root is the node being considered at that level is balanced. So the rebalancing proceeds up the path followed by the search to the root, rebalancing all the way.

Code vs. English

I'm pretty convinced here that the clearest and neatest way to see what's going on is to head straight to the code (which I could flash up but will not).

So for this I'm a Pawlickian! I assume you have the book. Read it. As you see, I mark mine up a bit... it's not a romance novel (hmmm...I mark those up, too...).

"Her breathless excitement surged to a crescendo *wrong word!* as his strong sure fingers..."