mid2 Flashcards
Push LL Complexity
O(1)
Pop LL Complexity
O(1)
Push AL Complexity
O(N)/*O(1)
Pop AL Complexity
O(N)/*O(1)
Enq LL Complexity
O(1)
Deq LL Complexity O(1)
O(1)
Enq AL Complexity
O(N)/*O(1)
Deq AL Complexity
O(N)
Enq AL Circular Complexity
O(N)/*O(1)
Deq AL Circular Complexity
O(N).*O(1)
RBT additional reqs
-Each Node is either red or black
-Root is always black
-Every path from root to all null leaves encouters the same # of black nodes
-No adjacent (parent/child) red nodes
Breadth-first order
Print in perfect horizontal order
Preorder
Head -> Left -> Right
Postorder
Left -> Right -> Head
In order
/\ Formation, Left -> Head -> Right
Left child location in AL
2 * i + 1
Right child location in AL
2 * i + 2
Parent location in AL
floor((i-1)/2)
AVL search insert delete complexity
O(logN)
Complete binary tree
Every node is as far left as possible, every level except possibly the last level is filled
Full Binary Tree
Every node has either 0 or 2 children
