Balanced Binary Search Tree Archives

Binary Search Tree data structures explained

A Binary Search Tree is a Binary tree in which all the nodes have following properties.

Left subtree of a node contains all the nodes having values lesser than the node.
Right subtree of a node contains all the nodes having values higher than the node.
Both the left and right subtree is also a Binary Search Tree.

As the name suggests, this data structure is mainly used for faster searching. In order to do that, restrictions are applied while inserting/deleting an element into the tree. As a result of these restrictions, worst case search time complexity remains at O(log n).

Below are some examples of Binary Search Trees.

(more…)

AVL Tree Self Balancing Rotations – Left Right Rotation explained

by admin

An AVL (Adelson-Velskii and Landis) Tree is a self balancing Binary Search Tree which has the following properties.

For any node “A”, the height of the left subtree of “A” and height of the right subtree of “A” differ by 1 at max.

In case of Binary search Trees worst case search complexity is O(n) in cases when the Binary Search Tree is skewed. In AVL tree, since heights of left and right subtree are balanced, hence search complexity improves to O(log n). Before going ahead have a look into AVL Tree Basics.

(more…)

Program To Check Whether A Binary Search Tree Is AVL Tree

by admin

An AVL (Adelson-Velskii and Landis) Tree is a self balancing Binary Search Tree which has the following properties.

For any node “A”, the height of the left subtree of “A” and height of the right subtree of “A” differ by 1 at max.

In case of Binary search Trees worst case search complexity is O(n) in cases when the Binary Search Tree is skewed. In AVL tree, since heights of left and right subtree are balanced, hence search complexity improves to O(log n). Before going ahead have a look into Binary Search Tree basics, Binary Search Tree Insert, Binary Search Tree Delete, Binary Search Tree Search operations.

(more…)

AVL Tree Explanation With Simple Examples

by admin

An AVL (Adelson-Velskii and Landis) Tree is a self balancing Binary Search Tree which has the following properties.

For any node “A”, the height of the left subtree of “A” and height of the right subtree of “A” differ by 1 at max.

In case of Binary search Trees worst case search complexity is O(n) in cases when the Binary Search Tree is skewed. In AVL tree, since heights of left and right subtree are balanced, hence search complexity improves to O(log n).

(more…)