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
    • self-balanced n-ary search tree
    • record points exist on all nodes
  • B+ Tree
    • a modified version of B-Tree, where record pointers only exist in leaf nodes
  • Segment Tree
• Ternary Tree
• N-ary Tree