Computer Science‎ > ‎

### Trees

Tree Data Structures: Like hierarchical trees with a set of linked nodes.
From a mathematical perspective, an acyclic graph where each node has only one parent but any number of children ( including zero ). The root of course has no parent.

Binary Search Trees (BST) :  The left child is always smaller than the parent; right child is always greater than the parent. Each node has at most two children .Both the left and
right subtrees are also binary subtrees. Ideally ( and in the average case ) , if the tree is balanced - search, insertion and deletion take O(log n) time. However if the tree is
not balanced properly, these operations could take O(n) time in the worst case.

Heaps: Each element is lesser than its parent. Also, heaps are "filled up" and don't have blank or null nodes in the middle of the tree - ( these could be present in binary trees ).

Height Balanced Trees: Unbalanced trees increase the time complexity of search, insert, delete operations and they tend towards O(n) Linear time rather than O(log n) - logarithmic
time. So, we associate balance indicators with the nodes and try to make rotations which will keep the tree balanced without distorting its Binary Search Tree properties.

### 3. Height Balanced Trees : AVL Trees

ċ
TreeVisualizations.jar
(29k)
Prashant Bhattacharji,
Aug 1, 2011, 5:12 AM