Search⌘ K
Home
Courses
Data Structures for Coding Interviews in JavaScript

AVL Deletion

Explore the process of deleting nodes in AVL trees and maintaining balance by performing rotations on unbalanced nodes. Understand the four rotation cases and how to traverse upwards to ensure the AVL tree remains balanced after deletions.

We'll cover the following...

Deletion in AVL Trees

Deletion is almost the same as the insertion operation in AVLs with just one exception. The deletion operation adds an extra step after the rotation and balancing of the first unbalanced node in the insertion method. After fixing the first unbalanced node through rotations, you would start moving up and fix the next unbalanced node. Keep fixing the unbalanced nodes until you reach the root.

Algorithm for Deletion

Here is a high-level description of the algorithm for deletion.

1. Delete the given node:

Delete the given node in the same way as in BST deletion. At this point, the tree will become unbalanced. To rebalance the tree, we would need to perform some kind of rotation either​ left or right. At first, we need to define the structure of the AVL Tree and some ...