TREES + BST + HEAPS MASTER DECK

Tree definition

Nonlinear hierarchical data structure

Root definition

Topmost node in a tree

Leaf definition

Node with no children

Internal node definition

Node with at least one child

Tree height definition

Longest root-to-leaf path

Full binary tree

Each node has 0 or 2 children

Complete binary tree

All levels filled left to right

Perfect binary tree

Every level is full

Preorder traversal

Root, left, right

Inorder traversal

Left, root, right

Postorder traversal

Left, right, root

Level order traversal

Uses a queue

BST property

Left child < root < right child

BST search average complexity

O(log n)

BST search worst-case

O(n)

BST insert complexity

O(log n) average, O(n) worst

BST inorder output

Sorted values

Why BST becomes skewed

Data inserted in sorted order

Heap property (min heap)

Parent node smaller than children

Heap completeness requirement

Always a complete binary tree

Heap storage format

Array

Heap insert complexity

O(log n)

Heap pop/remove-min complexity

O(log n)

Heap peek-min complexity

O(1)

Heap build from array complexity

O(n) (heapify)

Index formula left child

2*i + 1

Index formula right child

2*i + 2

Index formula parent

(i - 1) / 2

Difference BST vs Heap

BST ordered by in-order property, heap ordered by parent-child only

Difference heap vs priority queue

Priority queue is the ADT, heap is the implementation

Priority queue main operations

insert, getMin, removeMin