Balanced Tree – AVL Tree in Java

In this tutorial, we’re gonna look at AVL Tree Data Structure. It is a balanced binary search tree – the heights of given node’s children trees don’t differ more than 1 (with height of node = max of its children node + 1).

balanced-tree-avl-tree-java-overview

AVL Rotations

Four types of unbalanced situations:
Left-Left: doubly left heavy situation => make a right rotation.
Right-Right: doubly right heavy situation => make a left rotation.
Left-Right: => make a left and a right rotation.
Right-Left: => make a right and left rotation.

Right Rotation

balanced-tree-avl-tree-java-right-rotation

To simplify the sample, we assume that C has no right node. In general, right node of C will not be changed.

Left Rotation

balanced-tree-avl-tree-java-left-rotation

To simplify the sample, we assume that A has no left node. In general, left node of A will not be changed.

Left-Right Rotation

balanced-tree-avl-tree-java-left-right-rotation

To simplify the sample, we assume that A has no left node and C has no right node. In general, left node of A or right node of C will not be changed.

Right-Left Rotation

balanced-tree-avl-tree-java-right-left-rotation

AVL Insertion

Inserting a node to an AVL Tree is just like inserting it to standard binary search tree. But at the last step, we must check if new AVL Tree is balanced and decide implementing rotations or not.
– Start from the root node.
– Compare data with node data.
+ If the data is less than node: search for the empty location in the left subtree and insert the data.
+ Otherwise: search for the empty location in the right subtree and insert the data.
– Set height for the node.
– Check balance and make rotations if necessary.

AVL Removal

One of solution is soft delete: not remove node from the tree, but mark that it has been removed.

To make a node disappear from the tree:
– First we have to look for the node that we wanna remove by comparing data with node data.
+ If data smaller than given node data: go to the left recursively.
+ If data greater than given node’s data: go to the right recursively.
+ Find the node, now we have 3 possible cases of that node:
1- a leaf node (has no child): remove it
2- has a single child node: remove it and update references
3- has 2 children node: we have 2 options to do:
—3.1 look for largest node in the left subtree (predecessor), replace the node with this predecessor.
—3.2 look for smallest node in the right subtree (successor), replace the node with successor.
– In the end, check balance and make rotations if necessary.

balanced-tree-avl-tree-java-predecessor-successor

AVL Traverse

Practice
Node

AVL Tree

App

Result



By grokonez | March 24, 2018.


Related Posts


Got Something To Say:

Your email address will not be published. Required fields are marked *

*