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.





1. Binary Search Trees

2. The Tree Structure of Heaps

3. Height Balanced Trees : AVL Trees