Trees

Definition of Tree

A tree is basically a finite set of one or more nodes
such that:

• There is a specially designated node called
  the root.
• The remaining nodes are partitioned into n>=0 disjoint sets T1, ., Tn, where each of these sets is a tree.
• We call T1, ., Tn the subtrees of the root

• A tree is a non-linear data structure that consists of a root node and potentially many levels of additional nodes that form a hierarchy
• Nodes that have no children are called leaf nodes
• Non-root and non-leaf nodes are called internal nodes

A Binary Search Tree is a binary tree with the following properties:

• All items in the left subtree are less than the root.
• All items in the right subtree are greater or equal to the root.
• Each subtree is itself a binary search tree.

AVL - Good but not Perfect Balance

• AVL trees are height-balanced binary search trees
• Balance factor of a node
  • height(left subtree) - height(right subtree)
• An AVL tree has balance factor calculated at every node
  • For every node, heights of left and right subtree can differ by no more than 1
  • Store current heights in each node

-----------------------------------