Tutorial on threaded binary tree part 3: AVL-like updating of height differences

[Alf P. Steinbach]

Part 3. This tutorial, if it works (it's an experiment), is intended to
work this way:

* I post some working code.
* Learner(s) study it and ask about things.
* Others answer questions and post critique or get bogged down in long
sub-threads about sausages and swearing.

Part 2 added logic to maintain a height difference value in each node.
Namely, height of right subtree minus height of left subtree. One nice
thing about a difference, as opposed to just storing the heights
directly, is that when balancing is introduced the diff can be encoded
in just 2 bits, e.g., for joy-joy hacking delight, in the least
significant bits of the pointers – but I'm not going to do that. :)

Tim Rentsch suggested an alternative way to do the updating, using O(1)
memory instead of O(log n) memory as in the code I posted. That's one
reason for this posting. Another reason is that I'd like comments on my
thoughts about balancing, outlined at the end here, before I code it up.

----------------------------------------------------------------------

The part 2 updating code, using O(log n) memory, looked like this:

// Called after a new node, the `p_new_child`, has been inserted:
void update_height_differences(
Node* const p_new_child,
stack<Node*> parent_nodes
)
{
Node* p_child = p_new_child;
while( not parent_nodes.empty() )
{
Node* const p_parent = popped_top_of(
parent_nodes );
int& height_diff = p_parent->height_diff;
int const old_height_diff = height_diff;

height_diff += (p_parent->right == p_child? +1 : -1);

bool const this_height_increased =
(abs( height_diff ) > abs( old_height_diff ));
if( not this_height_increased )
{
break;
}
p_child = p_parent;
}
}

void add( Value const& value )
{
stack<Node*> parent_nodes;
Node** p_ptr = &root_;
while( *p_ptr != nullptr )
{
Node*& ref_ptr = *p_ptr;
parent_nodes.push( ref_ptr );
p_ptr = &(value < ref_ptr->value? ref_ptr->left :
ref_ptr->right);
}
*p_ptr = new Node{ nullptr, nullptr, value, 0 };
update_height_differences( *p_ptr, move( parent_nodes ) );
}

An implementation of Tim's suggested O(1) memory updating, which as I
understand it is a common implementation:

// Called after a new node with value `new_value` has been inserted:
static void update_height_differences_down_from(
Node* const highest_node_with_change,
Value const& new_value
)
{
Node* node = highest_node_with_change;
while( node )
{
bool const go_left = (new_value < node->value);
bool const is_leaf_node = not(node->left or node->right);
if( not is_leaf_node )
{
node->height_diff += (go_left? -1 : +1);
}
node = (go_left? node->left : node->right);
}
}

void add( Value const& value )
{
Node** p_ptr = &root_;
Node* lowest_newheight_absorber = nullptr;
while( *p_ptr != nullptr )
{
Node*& ref_ptr = *p_ptr;
bool const go_left = (value < ref_ptr->value);
bool const go_right = not go_left;
bool const right_is_higher = (ref_ptr->height_diff > 0);
bool const left_is_higher = (ref_ptr->height_diff < 0);

if( go_left and right_is_higher or go_right and
left_is_higher )
{
lowest_newheight_absorber = ref_ptr;
}

p_ptr = &(go_left? ref_ptr->left : ref_ptr->right);
}

*p_ptr = new Node{ nullptr, nullptr, value, 0 };
update_height_differences_down_from(
lowest_newheight_absorber? lowest_newheight_absorber : root_,
value
);
}

I haven't measured these but the O(1) memory scheme avoids any dynamic
allocation even for the most naïve direct implementation, so for the
case of non-optimized code it should be faster.

It brings more complexity to the `add` member function, and simplifies
the `update_height_differences`... function.

----------------------------------------------------------------------

My thinking about balancing.

I've yet to read up on this in Wikipedia. Hopefully that won't be
necessary! :) I think the last I read about it was in Wirth's Algorithms
+ Data Structures = Programs, around 1984.

Basic idea for the situation at the left below, put current root at
maximum right of its left of subtree (its value is guaranteed greater):

|
40
/ |
30 → 30
/ / \
20 20 40
/ / \
10 10 30

How a naïve implementation can then produce an equally bad tree:

|
40
/ \ |
30 45 → 30
/ \ / \
20 35 20 35
/ / \
10 10 40
\
45

One fix is to make current root R = 40 the right subtree of its left
node N = 30, put current right subtree of N as left subtree of R:

|
40
/ \ |
30 45 → 30
/ \ / \
20 35 20 40
/ / / \
10 10 35 45

But is this all, modulo symmetry for the opposite imbalance?


Cheers!, & Happy New Year soon!,

- Alf

[Tim Rentsch]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> Part 3. This tutorial, if it works (it's an experiment), is intended
> to work this way:
>
> * I post some working code.
> * Learner(s) study it and ask about things.
> * Others answer questions and post critique or get bogged down in long
> sub-threads about sausages and swearing.
>
> Part 2 added logic to maintain a height difference value in each
> node. Namely, height of right subtree minus height of left
> subtree. One nice thing about a difference, as opposed to just storing
> the heights directly, is that when balancing is introduced the diff
> can be encoded in just 2 bits, e.g., for joy-joy hacking delight, in

> the least significant bits of the pointers ? but I'm not going to do
> that. :)

The code still doesn't discard (or simply count) duplicate values.
I really recommend that you do that, especially before you get to
rebalancing. (I have no other specific comments on that version
of the code so I snipped it.)

> Tim Rentsch suggested an alternative way to do the updating, using
> O(1) memory instead of O(log n) memory as in the code I posted. That's
> one reason for this posting. Another reason is that I'd like comments
> on my thoughts about balancing, outlined at the end here, before I
> code it up.
>
> ----------------------------------------------------------------------
>

> An implementation of Tim's suggested O(1) memory updating, which as I
> understand it is a common implementation:

It corresponds to what is done in the AVL algorithm given in
Knuth. I don't know how common it is, only that I thought it
worth pointing out.

> // Called after a new node with value `new_value` has been inserted:
> static void update_height_differences_down_from(
> Node* const highest_node_with_change,
> Value const& new_value
> )
> {
> Node* node = highest_node_with_change;
> while( node )
> {
> bool const go_left = (new_value < node->value);
> bool const is_leaf_node = not(node->left or node->right);
> if( not is_leaf_node )
> {
> node->height_diff += (go_left? -1 : +1);
> }
> node = (go_left? node->left : node->right);
> }
> }

Another way the termination test could be done is to pass in the
address of the newly created leaf node, and compare for it. That
would make the while() loop be something like

while( node != new_leaf ) ...

and it would allow the updating of node->height_diff to be lifted
up a level rather than being inside an if().

> void add( Value const& value )
> {
> Node** p_ptr = &root_;
> Node* lowest_newheight_absorber = nullptr;
> while( *p_ptr != nullptr )
> {
> Node*& ref_ptr = *p_ptr;
> bool const go_left = (value < ref_ptr->value);
> bool const go_right = not go_left;
> bool const right_is_higher = (ref_ptr->height_diff > 0);
> bool const left_is_higher = (ref_ptr->height_diff < 0);
>
> if( go_left and right_is_higher or go_right and left_is_higher )
> {
> lowest_newheight_absorber = ref_ptr;
> }
>
> p_ptr = &(go_left? ref_ptr->left : ref_ptr->right);
> }
>
> *p_ptr = new Node{ nullptr, nullptr, value, 0 };
> update_height_differences_down_from(
> lowest_newheight_absorber? lowest_newheight_absorber : root_,
> value
> );
> }
>
> I haven't measured these but the O(1) memory scheme avoids any dynamic

> allocation even for the most naive direct implementation, so for the

> case of non-optimized code it should be faster.

A downside of this approach is that the value comparisons (or some
of them anyway) are done a second time. An intermediate scheme,
which I kind of like, is to have a "stack" of bits reflecting the
left/right choices made past the point of the tipping point node.
The "stack" of bits can be stored in 2 or 3 'unsigned long' words,
which is more than enough to handle any feasible tree.

Incidentally, kind of a side comment, I find the code composition
style shown to be somewhat cumbersome. I don't know if you have
changed your normal style for tutorial reasons, and it's really
tangential to the main discussion anyway, but I thought it might
be good to mention it.

> It brings more complexity to the `add` member function, and simplifies
> the `update_height_differences`... function.

It turns out some sort of tracking like this will be important
when we get to rebalancing, so it's probably better to introduce
it now.

Also, you may find it helpful to split off the special case of
adding a value to an empty tree. The general case code has an
easier time of it if that code doesn't have to deal with the tree
being completely empty.

> ----------------------------------------------------------------------
>
> My thinking about balancing.
>

> I've yet to read up on this in Wikipedia. [...]

For those who are interested I will try to walk through a general
outline. If anyone wants to figure it out on their own then stop
reading here.

Here is a canonical tree that may need rebalancing after a new
value is inserted (and obviously there are the corresponding
mirror image cases):

20
/ \
/ \
10 40
/ \
/ \
30 50

Note: the tree is shown as complete, with '20' at the top, but
that isn't actually necessary for what follows. The '20' node
could be in the middle of the tree, and there could be additional
subtrees below the '10', '30', and '50' nodes, as long as:

one: the height of those three leaf nodes is all the same; and
two: all nodes after '20' along the insertion path are "level",
ie, their left and right subtrees have equal heights.

So, if we're going to insert a new value, there are three cases:
somewhere under the 10 (eg, 5 or 15), somewhere under the 30 (eg,
25 or 35), or somewhere under the 50 (eg 45 or 55). Let's look at
the "under 10" case first. The new tree looks like this:

20
/ \
/ \
10 40
.... / \
/ \
30 50

where the .... means something got added somewhere in the left or
right subtree of the 10. The "balance" factor of the 10 node will
have been adjusted already, by virtue of being downstream from the
"tipping point" node, which is the 20 node in this case. The
height of 20's left side has grown by one, so the 20 node needs to
be marked as "level", but nothing else needs to happen.

Now let's look at the "under 50" case. The new tree looks like
this:

20
/ \
/ \
10 40
/ \
/ \
30 50
....

For sure this tree needs to be rebalanced. After inserting a new
value, rebalancing an AVL tree is a local operation, involving
just a few nodes in the interior of the tree. Here we have the
easier of the two cases where rebalancing needs to happen.
Typically the transformation done is described as a "rotation".
Conceptually it could be described thusly:

one: move the 20 node down and to the left;
two: move the 40 node up to where the 20 node used to be;
three: change the left link in the 40 node to point to the
20 node, and set the right link of the 20 node (which
used to point to the 40 node) to point to the 30 node.

Here is the post-rotation picture:

40
/ \
/ \
20 50
/ \ ....
/ \
10 30

To adjust the balance factors, the 20 node and the 40 node both
need to be set to "level". (The balance on the 50 node will have
been adjusted already, according to whether the insertion happened
on the left or the right.) Whatever parent pointer used to point
to the 20 node needs to be set to point to the 40 node. The
parent pointer could be a left- or right- pointer in what was 20's
parent node, or it could the root_ pointer if the 20 node was at
the top of the tree.

Now let's look at the "under 30" case. Here is what the tree
looks like after the new value is inserted:

20
/ \
/ \
10 40
/ \
/ \
30 50
....

Suppose we try the same rotation we did for the "under 50" case.
The resulting tree would be:

40
/ \

/ \
20 50
/ \
/ \

10 30
....

Obviously that didn't help - the tree shown has the same out-of-
balance problem as the original, except on the left instead of on
the right. We need to do something different, but what?

It's common to see the transformation needed here described as a
"double rotation", but I think it might be easier to understand if
described like this:

one: reach down, grab the 30 node, pull it up to the top;
two: set 30's left link to point to the 20 node, 30's right
link to point to the 40 node;
three: set 20's right link to point to the original value of
30's left link, and 40's left link to point to the
original value of 30's right link

Here is the resulting picture:

30
/ \
/ \
20 40
/ .? ?. \
/ \
10 50

Note the .... that was under the 30 got split, with half of it put
under the 20, and half of it put under the 40. If the 30 node was
previously a leaf, only one of those two pointers will be
non-null.

For balance factors: the 30 node should be set level; the 20
node should be set level if the insertion happened down 30's left
side, and "leftish" otherwise; the 40 node should be set level if
the insertion happened down 30's right side, and "rightish"
otherwise.

And of course whatever parent node was previously pointing to 20
needs to be set to point to the 30 node.

NOTE: The discussion above assumes all nodes along the insertion
path and downstream of the 20 node have had their balance factors
adjusted already. Nodes upstream of the 20 node all keep the same
balance factors they had before the insertion.

[Alf P. Steinbach]

On 31.12.2016 22:12, Tim Rentsch wrote:
> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> [snip]

>
> Incidentally, kind of a side comment, I find the code composition
> style shown to be somewhat cumbersome. I don't know if you have
> changed your normal style for tutorial reasons, and it's really
> tangential to the main discussion anyway, but I thought it might
> be good to mention it.

Oh.

You probably have some good points even though it seems clear that you
have more of a C background than C++, and I'd love to hear them.

Re background hypothesis: I noticed things like using `struct` for
`namespace`.

Re probably good points anyway: so far all you've written has been spot
on. And I remember in the old days, I heard from people in HR that the
partners in Accenture Norway took a dim view towards criticism that
wasn't accompanied by solutions. But I reasoned that when one spots a
proposal for square car wheels, flying through the approval process,
then one has an obligation to point it out even if one doesn't have the
slightest competence at all in wheels design, just common sense and
maybe a heck of a lot of experience in driving various vehicles.


>[snip]

Thanks for the discussion of rebalancing (snipped). I'll probably have
to study this. :)

The various ways to do height information updating are also interesting.

Except I think that the originally posted code with a stack of parent
pointers, which worked its way up (instead of down) the tree, may be far
more suitable for doing balancing at the lowest possible level -- at
least until threading is in place?


Cheers!,

- Alf

[Tim Rentsch]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> On 31.12.2016 22:12, Tim Rentsch wrote:
>> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
>> [snip]
>>
>> Incidentally, kind of a side comment, I find the code composition
>> style shown to be somewhat cumbersome. I don't know if you have
>> changed your normal style for tutorial reasons, and it's really
>> tangential to the main discussion anyway, but I thought it might
>> be good to mention it.
>
> Oh.
>
> You probably have some good points even though it seems clear that you
> have more of a C background than C++, and I'd love to hear them.

It's true that I am more familiar with C than with some of the
recent additions to C++, but for the most part I think what I
would say should be equally applicable to both.

> Re background hypothesis: I noticed things like using `struct` for
> namespace`.

(I guessed that winapi was a namespace rather than a struct but
since I was just throwing it together I took the path of least
resistance...)

> Re probably good points anyway: so far all you've written has been
> spot on.

Thank you, that's always nice to hear.

> And I remember in the old days, I heard from people in HR
> that the partners in Accenture Norway took a dim view towards
> criticism that wasn't accompanied by solutions.

I deliberately didn't give any details because I thought it
was off the main line. But since you're interested certainly there
will be some constructive suggestions as part of the comments.
Let me do that in a second followup....

>> [snip]
>
> Thanks for the discussion of rebalancing (snipped). I'll probably have
> to study this. :)
>
> The various ways to do height information updating are also interesting.
>
> Except I think that the originally posted code with a stack of parent
> pointers, which worked its way up (instead of down) the tree, may be
> far more suitable for doing balancing at the lowest possible level --
> at least until threading is in place?

It is a remarkable result for AVL trees that, after an insertion,
at most one rebalancing operation needs to take place, and where
that is in the tree can be precisely identified during the walk
along the path from the root to the insertion point. Nodes
downstream of that point will need their balance factors
adjusted, but the only place where nodes may need to be moved
around is at the one place identified during the initial walk.

When we get to threading, we will find that for the most part
threading takes care of itself, except in a few cases where nodes
with thread links are directly moved as part of a rebalancing
operation. So there again we don't need to worry about any
downstream nodes, just those near the "tipping point" node as
I have been calling it.

[Tim Rentsch]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> On 31.12.2016 22:12, Tim Rentsch wrote:
>> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
>> [snip]
>>
>> Incidentally, kind of a side comment, I find the code composition
>> style shown to be somewhat cumbersome. I don't know if you have
>> changed your normal style for tutorial reasons, and it's really
>> tangential to the main discussion anyway, but I thought it might
>> be good to mention it.
>

> You probably have some good points [...]

Okay I promised a followup, here we go. A few preliminaries
before we get started. First the code I am posting has been
compiled but it has not been tested. (Yes, lazy me. Also minor
errors may have been introduced during editing, but the code did
compile when I started.) Second there are some minor changes
with horizontal white space but I hope you will disregard those,
that isn't what I was reacting to. Third I am used to K&R
bracing style (and find BSD style almost painful to try to read),
and I use a K&R-ish style in what follows but that also is not
what I was reacting to, so I hope that won't be too distracting.

To begin, here is my starting point - your code adjusted for
bracing style (and some accidental line wraps?) but otherwise as
originally posted. (There may also be some other whitespace
changes introduced without my meaning to do so.) Oh, I also
switched the order of the two functions.

void
add( Value const& value ){
Node** p_ptr = &root_;
Node* lowest_newheight_absorber = nullptr;
while( *p_ptr != nullptr ){
Node*& ref_ptr = *p_ptr;
bool const go_left = (value < ref_ptr->value);
bool const go_right = not go_left;
bool const right_is_higher = (ref_ptr->height_diff > 0);
bool const left_is_higher = (ref_ptr->height_diff < 0);

if( go_left and right_is_higher or go_right and left_is_higher ){
lowest_newheight_absorber = ref_ptr;
}

p_ptr = &(go_left? ref_ptr->left : ref_ptr->right);
}

*p_ptr = new Node{ nullptr, nullptr, value, 0 };
update_height_differences_down_from(
lowest_newheight_absorber? lowest_newheight_absorber : root_,
value
);
}

static void
update_height_differences_down_from(
Node* const highest_node_with_change,
Value const& new_value
){
Node* node = highest_node_with_change;
while( node ){
bool const go_left = (new_value < node->value);
bool const is_leaf_node = not(node->left or node->right);
if( not is_leaf_node ){
node->height_diff += (go_left? -1 : +1);
}
node = (go_left? node->left : node->right);
}
}

My reaction is more of a gestalt than any particular item or
items. I just have a gut reaction that there is more code here
to read than the problem needs. So, rather than trying to
identify weaknesses, let me take a different tack and just write
code more along the lines of how I would naturally write it. We
are going to end up looking at several different versions, so if
it starts off a little rough please bear with me.

First cut:

void
add( Value const& value ){

typedef Node *Tree;
Tree p = root_, q, *qd = &root_;

while( *qd ){
q = *qd;
if( value == q->value ) return;
qd = value > q->value ? &q->right : &q->left;
int d = q->height_diff;
if( qd == &q->right ? d < 0 : d > 0 ) p = q;
}
*qd = new Node{ 0, 0, value, 0 };

if( p ) do {
p->height_diff += value > p->value ? 1 : -1;
p = value > p->value ? p->right : p->left;
} while( p->value != value );
}

This function does both the inserting and updating the height
information. Inside the first loop is a conditional return that
causes duplicate values to be ignored.

This code isn't very pretty. I can follow what it's doing but it
still is not as clean as I would like. As part of rewriting it,
two minor changes occur to me for the 'Node' type: one, have a
constructor that takes a value; and two, rename 'height_diff' to
'balance'. Also we can choose a more conventional expression for
the conditional while() loop at the end, albeit with a minor loss
of efficiency. Here is a second cut:

void
add( Value const& value ){

Node *p = root_, **qp = &root_, *q;

while( q = *qp ){
if( value == q->value ) return;

qp = value < q->value ? &q->left : &q->right;
if( qp == &q->left ? q->balance > 0 : q->balance < 0 ) p = q;
}
q = *qp = new Node{ value };

while( p && p != q ){
p->balance += value < p->value ? -1 : 1;
p = value < p->value ? p->left : p->right;
}
}

This is better, but still not not as clean as it could be. (Btw
I noticed the spacing convention you use for ?: and decided to
try it in this code.) The biggest offender is that complicated
if() in the first while() loop. How about if we push that
condition off to a subfunction? Third cut:

void
add( Value const& value ){

Node *p = root_, **qp = &root_, *q;

while( q = *qp ){
if( value == q->value ) return;

qp = value < q->value ? &q->left : &q->right;
if( q->height_would_not_increase_for( value ) ) p = q;
}
q = *qp = new Node{ value };

while( p && p != q ){
p->balance += value < p->value ? -1 : 1;
p = value < p->value ? p->left : p->right;
}
}

That is definitely better. Now we can see what's going on
without getting caught up in the details of the test.

At this point we might be content to stop, but let's try pushing
forward. The while() loop that walks the tree looks like it
could be made into a for() loop instead. Also maybe 'key' is a
nicer choice than 'value' for the parameter and Node data member.
A fairly mechanical change gives a fourth cut:

void
add( Value const& key ){
Node *p = root_, **q, *r;

for( q = &root_; r = *q; q = key < r->key ? &r->left : &r->right ){
if( key == r->key ) return;

if( r->height_would_not_increase_for( value ) ) p = r;
}
r = *q = new Node{ value };

while( p && p != r ){
p->balance += key < p->key ? -1 : 1;
p = key < p->key ? p->left : p->right;
}
}

That makes the loop body better, at the cost of a too-long for()
line. Our fix again is to push the calculation into a Node
sub-function. We make a similar change to the second while()
loop, and move the test for 'p' being null up before the loop
with a conditional return. Fifth cut:

void
add( Value const& key ){
Node *p = root_, **q, *r;

for( q = &root_; r = *q; q = r->downlink_address( key ) ){
if( key == r->key ) return;

if( r->height_would_not_increase_for( key ) ) p = r;
}
r = *q = new Node{ value };
if( !p ) return;

for( ; p != r; p = *p->downlink_address( key ) ){
p->balance += key < p->key ? -1 : 1;
}
}

That conditional return near the end is just ugly. We can fix
that by using the initialization portion of the for() loop.
Sixth cut:

void
add( Value const& key ){
Node *p = root_, **q, *r;

for( q = &root_; r = *q; q = r->downlink_address( key ) ){
if( key == r->key ) return;

if( r->height_would_not_increase_for( key ) ) p = r;
}
r = *q = new Node{ value };

for( p = p? p:r; p != r; p = *p->downlink_address( key ) ){
p->balance += key < p->key ? -1 : 1;
}
}

Okay, this one isn't too bad! One more change suggests itself -
make the balance update line into a Node subfunction. That gives
our seventh and final cut:

void
add( Value const& key ){
Node *p = root_, **q, *r;

for( q = &root_; r = *q; q = r->downlink_address( key ) ){
if( key == r->key ) return;

if( r->height_would_not_increase_for( key ) ) p = r;
}
r = *q = new Node{ value };

for( p = p? p:r; p != r; p = *p->downlink_address( key ) ){
p->adjust_balance_after_inserting( key );
}
}

I know this has been a long journey to get to a rather modest
result. Hopefully though it shows some of my thought processes
as well as explaining my earlier comment with the nebulous phrase
"composition style".

How did I do? :)

[Tim Rentsch]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> On 31.12.2016 22:12, Tim Rentsch wrote:
>> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
>> [snip]
>>
>> Incidentally, kind of a side comment, I find the code composition
>> style shown to be somewhat cumbersome. I don't know if you have
>> changed your normal style for tutorial reasons, and it's really
>> tangential to the main discussion anyway, but I thought it might
>> be good to mention it.
>
> Oh.
>
> You probably have some good points even though it seems clear that you
> have more of a C background than C++, and I'd love to hear them.

A short afterthought to my long posting - I hope it didn't
come across as preachy, I didn't mean it that way at all;
just an explanation of my previous comment.

Incidentally, I am ready with an explanation for how to do
threading if/when you would like to hear that. I didn't
want to get ahead of the rebalancing installment.