Removes a node from the AVL-tree.
- Pointer to the node.
|pRoot ||Pointer to the AVL-tree root structure. |
|Key ||Key value of the node which is to be removed. Find the node which is to be removed: LOOP until not found BEGIN Add node pointer pointer to the AVL-stack. IF the keys matches THEN break! IF remove key < node key THEN left ELSE right END IF found THEN BEGIN IF left node not empty THEN BEGIN Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack: Start at left node. LOOP until right node is empty BEGIN Add to stack. go right. END Link out the found node. Replace the node which is to be removed with the found node. Correct the stack entry for the pointer to the left tree. END ELSE BEGIN Move up right node. Remove last stack entry. END Balance tree using stack. END return pointer to the removed node (if found). |