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!!!