balanced trees

Introduction AVL Tree is a kind of binary search tree. Different from binary search tree is, it is self-balanced. The heights of two child subtress of node differ by at most one. Because of this, another name of AVL Tree is height-balanced. These are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has Theta(lg n) height and hence Theta(lg n) worst case lookup and insertion times. [Read More]