www.delorie.com/gnu/docs/avl/libavl_159.html

search

	Buy GNU books!

GNU libavl 2.0.1

9.4.3 Symmetric Case

Here is the corresponding code for the case where insertion occurs in the right subtree of y.

struct tavl_node *x = y->tavl_link[1]; if (x->tavl_balance == +1) { <@xref{\NODE\, , Rebalance for +.> balance factor in TAVL insertion in right subtree,309} } else { <@xref{\NODE\, , Rebalance for -.> balance factor in TAVL insertion in right subtree,310} }

This code is included in @refalso{304

w = x; if (x->tavl_tag[0] == TAVL_THREAD) { x->tavl_tag[0] = TAVL_CHILD; y->tavl_tag[1] = TAVL_THREAD; y->tavl_link[1] = x; } else y->tavl_link[1] = x->tavl_link[0]; x->tavl_link[0] = y; x->tavl_balance = y->tavl_balance = 0;

This code is included in @refalso{308

<@xref{\NODE\, , Rotate right at x.> then left at y in AVL tree; avl => tavl,159} if (w->tavl_tag[0] == TAVL_THREAD) { y->tavl_tag[1] = TAVL_THREAD; y->tavl_link[1] = w; w->tavl_tag[0] = TAVL_CHILD; } if (w->tavl_tag[1] == TAVL_THREAD) { x->tavl_tag[0] = TAVL_THREAD; x->tavl_link[0] = w; w->tavl_tag[1] = TAVL_CHILD; }

This code is included in @refalso{308