Trees, Heaps, Graphs

• Trees

  • Binary Tree

  • Binary Search Tree

  • AVL Trees

  • Splay Trees

  • Red Black Trees

• Heaps

  • Max Heap

  • Min Heap

• Graphs

  • Depth First Search - stack

  • Breadth First Search - queue

Trees

Terminology

• Depth of a node – number of ancestors (exclude itself) / number of edge to the root

• Height of a tree – maximum depth of any node

• Traversal

  • Preorder: a node is visited before its descendants

  • Postorder: a node is visited after its descendants

 function Node(val, children) {
    this.val = val;
    this.children = children;
 };

Binary Tree

• Each internal node has at most two children

• Children of a node are an ordered pair

• Proper Binary Tree

  • if each node has 0 or 2 children

• Traversal

  • Inorder: left -> root -> right

  • Preorder: root -> left -> right

  • Postorder: left -> right -> root

 function TreeNode(val) {
     this.val = val;
     this.left = this.right = null;
 }

Binary Search Tree

• Left < Root < Right

• Search: cut sub-tree in half, determine which half the key would be in

• Insertion: expand an internal node / update value

• Deletion: replace with its left right-most node value, delete left right-most node

• Performance

  • Find, insert, remove – O(n) worst case (all node in one side)

  • Find, insert, remove – O(log n) best case (balanced tree)

AVL Tree

• First balanced binary search tree

• Heights of siblings can differ by at most 1

• Minimize single look up time, not exceed O(log n)

• Useful in multithreaded environments

Splay Tree

• Self-balancing BST

• 3 Types of Splay Steps

  • Zig-Zig

  • Zig-Zag

  • Zig

• Preferred for lots search, less insertion and deletion (cause rotations)

• Minimize total lookup time.

• Easier to implement, compare to AVL tree.

Red Black Tree

• Self-balancing BST

  • Each node has colour either red or black

  • No two adjacent red nodes

  • Every path from a node to any its descendant Null node has same number of black nodes

• Preferred for lots insertions and deletions

Heaps

• Binary tree with additional rules

• Complete binary tree – last node of the heap is the rightmost node of depth h

• Build Heap: Botton up heap construction – O(n)

• Insertion: upheap – O(log n)

• Deletion: downheap – O(log n)

Max Heap

• Parent node values are greater than their children

Min Heap / Priority Queue

• Parent node values are less than their children

Graphs

Depth First Search

• Traversing down through one branch to the leaf, then back to "trunk".

• Use Stack – O(n)

Breadth First Search

• Search through a tree one level at a time

• Use Queue – O(n)