"No one is harder on a talented person than the person themselves" - Linda Wilkinson ; "Trust your guts and don't follow the herd" ; "Validate direction not destination" ;

October 07, 2012

Algorithms Course Notes - Part II

Algorithms Course Notes from Coursera

Binary Search Trees
  • Binary Tree in Symmetric order (Nodes - Contain info, two links)
  • Each node has left and right tree, both can be null
  • Every Node Key Larger than keys in left sub tree
  • Every Node key smaller than keys in right sub tree
  • Inserts - Find a null link by search eligible position and insert it there
B Trees
  • General Model for external storage
  • Internal node key guide search
  • External node has client key
  • Insert at Bottom null node
  • If Nodes are full it will split to allow insert
  • Variants of BTree is used in DBs (B+ Tree, B* Tree)
RBT - Red Black Tree Tracks every simple path from a node to a descendant node with same number of black nodes
Red Black Trees
  • Internal Left Leaning links to glue 3 nodes
  • No Nodes have two red links connected
  • Every path from root to null link has same number of black links
  • Use a flag color to denote red or black link in implementation
Heap Sort
  • Largest of all keys is the root
Reposting Important Summary Slides

Happy Learning!!!

No comments: