Formula Sheets: Trees

 Page 1


T r ees F orm ula Sheet
T ree Basics
• Definition : Hierarc hical structure with no des, ro ot, and edges, no cycles.
• T erminology : n no des, n-1 edges, heigh t h , depth d , degree k .
• Num b er of No des : n =
?
deg(v
i
)+1 , where deg(v
i
) is degree of no de i .
• Heigh t vs. Depth : Heigh t h = max( depth of lea v es) , depth of ro ot = 0.
• Memory Size : S
tree
= n·(S
data
+k·S
p oin ter
) , where k is max p oin ters p er no de.
Binary T ree
• Definition : Eac h no de has = 2 c hildren (left, righ t).
• T yp es :
– Strictly Binary: Eac h no de has 0 or 2 c hildren.
– F ull Binary: All non-leaf no des ha v e 2 c hildren, lea v es at same lev el.
– Complete Binary: All lev els except last filled, last lev el filled left to righ t.
• Max No des at Lev el i : 2
i
, i = 0 (ro ot) to h .
• T otal No des (Heigh t h ) : n = 2
h+1
-1 (full binary tree).
• Heigh t vs. No des : h = ?log
2
n? , h = n-1 (sk ew ed tree).
• Arra y Represen tation : F or no de at inde x i (0-based):
– Left Child: 2i+1 , Righ t Child: 2i+2 , P aren t: ?(i-1)/2? .
– Space: S
arra y
= (2
h+1
-1)·S
elemen t
, w astes space for sparse trees.
T ree T ra v ersals
• T yp es : Preorder (ro ot, left, righ t), Inorde r (left, ro ot, righ t), P ostorder (left, righ t, ro ot), Lev el-
order.
• Time Complexit y : O(n) for all tra v ersals, where n is n um b er of no des.
• Space Complexit y : O(h) (recursiv e stac k), O(n) (lev el-order with queue).
• Recurrence : T(n) = T(n
left
)+T(n
righ t
)+O(1) , solv es to O(n) .
Binary Searc h T ree (BST)
• Prop ert y : Left subtree < ro ot < righ t subtree.
• Op erations :
– Searc h/Insert/Delete: A v erage O(h) , W orst O(n) (sk ew ed tree).
– Heigh t: h ˜ logn (balanced), h = n-1 (sk ew ed).
• Time Complexit y :
– Searc h: T
a vg
˜ 1.39logn , T
w orst
= O(n) .
– Insert/Delete: Similar to searc h, plus O(1) p oin ter up dates.
• Space Complexit y : O(n) for n no des, O(h) for recursion stac k.
1
Page 2


T r ees F orm ula Sheet
T ree Basics
• Definition : Hierarc hical structure with no des, ro ot, and edges, no cycles.
• T erminology : n no des, n-1 edges, heigh t h , depth d , degree k .
• Num b er of No des : n =
?
deg(v
i
)+1 , where deg(v
i
) is degree of no de i .
• Heigh t vs. Depth : Heigh t h = max( depth of lea v es) , depth of ro ot = 0.
• Memory Size : S
tree
= n·(S
data
+k·S
p oin ter
) , where k is max p oin ters p er no de.
Binary T ree
• Definition : Eac h no de has = 2 c hildren (left, righ t).
• T yp es :
– Strictly Binary: Eac h no de has 0 or 2 c hildren.
– F ull Binary: All non-leaf no des ha v e 2 c hildren, lea v es at same lev el.
– Complete Binary: All lev els except last filled, last lev el filled left to righ t.
• Max No des at Lev el i : 2
i
, i = 0 (ro ot) to h .
• T otal No des (Heigh t h ) : n = 2
h+1
-1 (full binary tree).
• Heigh t vs. No des : h = ?log
2
n? , h = n-1 (sk ew ed tree).
• Arra y Represen tation : F or no de at inde x i (0-based):
– Left Child: 2i+1 , Righ t Child: 2i+2 , P aren t: ?(i-1)/2? .
– Space: S
arra y
= (2
h+1
-1)·S
elemen t
, w astes space for sparse trees.
T ree T ra v ersals
• T yp es : Preorder (ro ot, left, righ t), Inorde r (left, ro ot, righ t), P ostorder (left, righ t, ro ot), Lev el-
order.
• Time Complexit y : O(n) for all tra v ersals, where n is n um b er of no des.
• Space Complexit y : O(h) (recursiv e stac k), O(n) (lev el-order with queue).
• Recurrence : T(n) = T(n
left
)+T(n
righ t
)+O(1) , solv es to O(n) .
Binary Searc h T ree (BST)
• Prop ert y : Left subtree < ro ot < righ t subtree.
• Op erations :
– Searc h/Insert/Delete: A v erage O(h) , W orst O(n) (sk ew ed tree).
– Heigh t: h ˜ logn (balanced), h = n-1 (sk ew ed).
• Time Complexit y :
– Searc h: T
a vg
˜ 1.39logn , T
w orst
= O(n) .
– Insert/Delete: Similar to searc h, plus O(1) p oin ter up dates.
• Space Complexit y : O(n) for n no des, O(h) for recursion stac k.
1
A VL T ree
• Prop ert y : Balanced BST, | heigh t
left
- heigh t
righ t
| = 1 for all no des.
• Balance F actor : BF = h
left
-h
righ t
, BF ? {-1,0,1} .
• Op erations : Searc h/Insert/Delete, Time Complexit y O(logn) .
• Rotations : LL, RR, LR, RL, eac h O(1) time.
• Heigh t : h = 1.44logn , ensures balance.
• Recurrence : T(n) = T(n/2)+O(1) for searc h, solv es to O(logn) .
Red-Blac k T ree
• Prop erties : Self-balancing BST, no des colored red/blac k, ro ot blac k, no t w o red no des adjacen t,
equal blac k no des on paths to lea v es.
• Op erations : Searc h/Insert/Delete, Time Complexit y O(logn) .
• Heigh t : h = 2log(n+1) , ensures balance.
• Rotations and Recoloring : O(1) p er op eration, m ax 2 rotations for insert, 3 for delete.
• Space Complexit y : O(n) , plus O(1) bit p er no de for color.
B-T ree and B+ T ree
• B-T ree :
– Order m : Eac h no de has = m c hildren, ?m/2?-1 = k eys = m-1 (except ro ot).
– Heigh t: h = log
?m/2?
(
n+1
2
)
.
– Op erations: Searc h/Insert/Delete, Time Complexit y O(log
m
n) .
– Disk I/O: O(log
m
n) page accesses, optimized for large m .
• B+ T ree :
– All k eys in lea v es, in ternal no des store p oin ters, lea v es link ed.
– Heigh t: h = log
?m/2?
n .
– Range Queries: O(log
m
n+k) , where k is n um b er of k eys in range.
– Space: S
B+
˜ S
B
, but more k eys in lea v es.
Binary Heap
• Prop ert y : Complete binary tree, paren t = (min-heap) or = (max-heap) c hildren.
• Op erations :
– Insert: O(logn) , Heapify-Up.
– Extract-Min/Max: O(logn) , Heapify-Do wn.
– Build-Heap: O(n) .
• Heigh t : h = ?logn? .
• Heap Sort : Time Complexit y O(nlogn) , Space Complexit y O(1) (in-place).
• Arra y Represen tation : Same as c omplete binary tree, S
heap
= n·S
elemen t
.
2
Page 3


T r ees F orm ula Sheet
T ree Basics
• Definition : Hierarc hical structure with no des, ro ot, and edges, no cycles.
• T erminology : n no des, n-1 edges, heigh t h , depth d , degree k .
• Num b er of No des : n =
?
deg(v
i
)+1 , where deg(v
i
) is degree of no de i .
• Heigh t vs. Depth : Heigh t h = max( depth of lea v es) , depth of ro ot = 0.
• Memory Size : S
tree
= n·(S
data
+k·S
p oin ter
) , where k is max p oin ters p er no de.
Binary T ree
• Definition : Eac h no de has = 2 c hildren (left, righ t).
• T yp es :
– Strictly Binary: Eac h no de has 0 or 2 c hildren.
– F ull Binary: All non-leaf no des ha v e 2 c hildren, lea v es at same lev el.
– Complete Binary: All lev els except last filled, last lev el filled left to righ t.
• Max No des at Lev el i : 2
i
, i = 0 (ro ot) to h .
• T otal No des (Heigh t h ) : n = 2
h+1
-1 (full binary tree).
• Heigh t vs. No des : h = ?log
2
n? , h = n-1 (sk ew ed tree).
• Arra y Represen tation : F or no de at inde x i (0-based):
– Left Child: 2i+1 , Righ t Child: 2i+2 , P aren t: ?(i-1)/2? .
– Space: S
arra y
= (2
h+1
-1)·S
elemen t
, w astes space for sparse trees.
T ree T ra v ersals
• T yp es : Preorder (ro ot, left, righ t), Inorde r (left, ro ot, righ t), P ostorder (left, righ t, ro ot), Lev el-
order.
• Time Complexit y : O(n) for all tra v ersals, where n is n um b er of no des.
• Space Complexit y : O(h) (recursiv e stac k), O(n) (lev el-order with queue).
• Recurrence : T(n) = T(n
left
)+T(n
righ t
)+O(1) , solv es to O(n) .
Binary Searc h T ree (BST)
• Prop ert y : Left subtree < ro ot < righ t subtree.
• Op erations :
– Searc h/Insert/Delete: A v erage O(h) , W orst O(n) (sk ew ed tree).
– Heigh t: h ˜ logn (balanced), h = n-1 (sk ew ed).
• Time Complexit y :
– Searc h: T
a vg
˜ 1.39logn , T
w orst
= O(n) .
– Insert/Delete: Similar to searc h, plus O(1) p oin ter up dates.
• Space Complexit y : O(n) for n no des, O(h) for recursion stac k.
1
A VL T ree
• Prop ert y : Balanced BST, | heigh t
left
- heigh t
righ t
| = 1 for all no des.
• Balance F actor : BF = h
left
-h
righ t
, BF ? {-1,0,1} .
• Op erations : Searc h/Insert/Delete, Time Complexit y O(logn) .
• Rotations : LL, RR, LR, RL, eac h O(1) time.
• Heigh t : h = 1.44logn , ensures balance.
• Recurrence : T(n) = T(n/2)+O(1) for searc h, solv es to O(logn) .
Red-Blac k T ree
• Prop erties : Self-balancing BST, no des colored red/blac k, ro ot blac k, no t w o red no des adjacen t,
equal blac k no des on paths to lea v es.
• Op erations : Searc h/Insert/Delete, Time Complexit y O(logn) .
• Heigh t : h = 2log(n+1) , ensures balance.
• Rotations and Recoloring : O(1) p er op eration, m ax 2 rotations for insert, 3 for delete.
• Space Complexit y : O(n) , plus O(1) bit p er no de for color.
B-T ree and B+ T ree
• B-T ree :
– Order m : Eac h no de has = m c hildren, ?m/2?-1 = k eys = m-1 (except ro ot).
– Heigh t: h = log
?m/2?
(
n+1
2
)
.
– Op erations: Searc h/Insert/Delete, Time Complexit y O(log
m
n) .
– Disk I/O: O(log
m
n) page accesses, optimized for large m .
• B+ T ree :
– All k eys in lea v es, in ternal no des store p oin ters, lea v es link ed.
– Heigh t: h = log
?m/2?
n .
– Range Queries: O(log
m
n+k) , where k is n um b er of k eys in range.
– Space: S
B+
˜ S
B
, but more k eys in lea v es.
Binary Heap
• Prop ert y : Complete binary tree, paren t = (min-heap) or = (max-heap) c hildren.
• Op erations :
– Insert: O(logn) , Heapify-Up.
– Extract-Min/Max: O(logn) , Heapify-Do wn.
– Build-Heap: O(n) .
• Heigh t : h = ?logn? .
• Heap Sort : Time Complexit y O(nlogn) , Space Complexit y O(1) (in-place).
• Arra y Represen tation : Same as c omplete binary tree, S
heap
= n·S
elemen t
.
2
Expression T ree
• Construction : F rom p ostfix, Time Complexit y O(n) , Space Complexit y O(n) .
• Ev aluation : P ostorder tra v ersal, Time Complexit y O(n) .
• Heigh t : h = n , t ypically O(logn) for balanced expressions.
• No des : n
leaf
= k (op erands), n
in ternal
= k-1 (op erators), total n = 2k-1 .
Applications
• BST : Dictionary , database indexing, O(logn) op erations if balanced.
• A VL/Red-Blac k : STL set/map, guaran teed O(logn) .
• B/B+ T ree : File system s, databases, O(log
m
n) disk I/O.
• Heap : Priorit y queues, sc heduling, Dijkstra’s algorithm.
• Expression T ree : Compiler design, arithmetic ev aluation.
P e rformance Metrics
• Time Complexit y Comparison :
– BST: O(h) a v erage, O(n) w orst.
– A VL/Red-Blac k: O(logn) guaran teed.
– B/B+ T ree: O(log
m
n) , optimized for dis k.
– Heap: O(logn) insert/extract, O(n) build.
• Space Complexit y :
– Binary T ree: O(n) , 2·S
p o in ter
p er no de.
– B-T ree: O(n·m) , m·S
p oin ter
p er no de.
– Heap: O(n) , arra y-based.
• Heigh t E?iciency :
– Balanced (A VL, Red-Blac k): h ˜ logn .
– B-T ree: h ˜ log
m
n , minimizes disk I/O.
– Sk ew ed BST: h = n-1 , p o or p erformance.
• Cac he P erformance : Arra y-based (heap) b etter than p oin ter-based (BST, A VL).
3