[Home]
[Contents]
[Chapter]
[Previous Algorithm]
[Next Algorithm]


Height-balanced tree (AVL) insertion (Pascal version available)


int incrhei; tree insert( key, t ) typekey key; tree t; { if( t == NULL ) { t = NewNode( key, NULL, NULL ); t->bal = 0; incrhei = 1; } else if( t->k == key ) Error; /*** Key already in table ***/ else { if( t->k < key ) { t->right = insert( key, t->right ); t->bal += incrhei; } else { t->left = insert( key, t->left ); t->bal -= incrhei; } if( (incrhei != 0) && (t->bal != 0) ) { incrhei = 0; if( t->bal < -1 ) /*** left subtree too tall: right rotation needed ***/ if( t->left->bal < 0 ) t = rrot( t ); else { t->left = lrot( t->left ); t = rrot( t ); } else if( t->bal > 1 ) /*** right subtree too tall: left rotation needed ***/ if( t->right->bal > 0 ) t = lrot( t ); else { t->right = rrot( t->right ); t = lrot( t ); } else incrhei = 1; } else incrhei = 0; } return( t ); }

C source (3413.ins.c) Pascal source (3413.ins.p)



© Addison-Wesley Publishing Co. Inc.