AVL tree implementation by [e-mail] ver. 1.0 2001.12.10 Explanation of rotl and rotr struct node { data_t data; int w; /* height-of-right-sub-tree - height-of-left-sub-tree acceptable values: -1,0,1 */ struct node *left, *right; } rotr: rotate nodes clockwise Purpose: improve node balance if wB < -1 Idea: A B / \ / \ B h3 => h1 A / \ / \ h1 h2 h2 h3 Algorithm: t= &A; tp= t->left; /* tp points to B */ t->left= tp->right; /* h2 becomes left sub-tree of A */ tp->right= t; /* A becomes right sub-tree of B */ Weight change: Suppose that wA is A->w before rotation and that wB is B->w before rotation wA will be surely increased (because its left sub-tree becomes lower). If h1 was higher than h2 then wA will be increased by 2, otherwise it will be increased by 1. wB tells what was higher: wB= h2 - h1, thus if wB < 0 wA += 2 else wA += 1 wB will be surely increased (because its right sub-tree becomes higher). If h3 was higher than h2 then wB will be increased by 2, otherwise by 1. To find if h3 is higher than h2 we start with balance for A wA = h3 - ( max(h1,h2) + 1 ) We have to consider two cases: a) wB < 0 <=> max(h1,h2) = h1, h1 = h2-wB wA = h3 - h1 - 1 = h3 - h2 + wB -1 h3 = h2 + 1 + ( wA - wB ) so h3 > h1 if ( wA - wB ) >= 0 b) wB >= 0 <=> max(h1,h2) = h2 wA = h3 - h2 - 1 h3 = h2 + 1 + wA so h3 > h1 if wA >= 0 Summarizing: h3 > h1 if wB < 0 && ( wA - wB ) >= 0 || wB >= 0 && wA >= 0 thus if wB < 0 && ( wA - wB ) >= 0 || wB >= 0 && wA >= 0 wB += 2 else wB += 1