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
  • Radix Tree
  • LSM (Log Strutured Merge) Tree
    • https://www.youtube.com/watch?v=I6jB0nM9SKU
    • data are stored in memory(memtable) as buffer
    • when buffer is full, it is flushed to disk as a SSTable (sorted)
    • SSTables are immutable, updates and deletes are added as new entries in later SSTables
    • Searching is slow, because it requires an iteration throught Memtable and all SSTables
    • As number of SSTables grows, causing lots of outdated data entries, a background compressing and merging process run periodically to "clean" the SSTables
• Ternary Tree
• N-ary Tree