Trees

Types of trees

• Binary Tree
  • Binary Search Tree
    • left child < node < right value
  • AVL Tree
    • self balanced BST
    • diff(height(leftChild), height(rightChild)) <= 1
  • Red-Black Tree
    • solves the same problem as AVL Tree but with less strict balance and thus less rotations
      • AVL Tree is suitable for frequent search, R/B tree is suitable for frequent insert & delete
    • each node has a color (R/B)
    • root is always black
    • no adjacent reds
    • leaves are black
    • for any nodes, all paths to leaf nodes contain the same number of black nodes
  • B- Tree
  • B+ Tree
  • Segment Tree
• Ternary Tree
• N-ary Tree