Transcript Slides for Exam 2 review

Review for Exam 2
• Topics covered (since exam 1):
–
–
–
–
–
Splay Tree
K-D Trees
RB Tree
Priority Queue and Binary Heap
B-Tree
• For each of these data structures
–
–
–
–
–
Basic idea of data structure and operations
Be able to work out small example problems
Prove related theorems
Asymptotic time performance
Advantages and limitations, comparisons
Review for Exam 2
• Splay tree
– Definition (a special BST: balanced in some sense)
– Rationale for splaying: amortized performance
– Splay operation (bottom up)
• Rotation
• without grandparent
• with grandparent: zig-zag and zig-zig
– When to splay (after each operation)
– What to splay with find/insert/delete operations
– Amortized time performance analysis: what does
O(m log n) mean?
Review for Exam 2
• K-D Trees
– What K-D trees are used for
• Multiple keys
• Range queries
– How K-D trees differ from the ordinary BST
• levels
– Be able to do insert and range query/print
– Limitations
• Hard to do deletion
• Difficult to balance
Review for Exam 2
• RB tree
– Definition: a BST satisfying 5 conditions
• Every node is either red or black.
• Root is black
• Each NULL pointer is considered to be a black node
• If a node is red, then both of its children are black.
• Every path from a node to a NULL contains the same
number of black nodes.
– Theorems leading to O(log n) worst case time performance
• Black height
• min and max # of nodes a RB tree with bh=k can have
– Bottom-up insertion and deletion
• When and what to rotate and recolor
Review for Exam 2
• PQ and binary heap
– Binary heap
• Definition: CBT with a partial order (heap order)
• Why it is good for PQ
– Heap operations (implemented with array)
•
•
•
•
findMin, deleteMin, insert
percolateUp (for insertion), percolateDown (for deletion)
Heap construction (heapify starting from the middle),
Heap sort
– Time performance of these operations
– Leftist tree and leftist heap
• Why we need this?
• Definition (npl: null path length)
• Meld operations and applications
– insert, deletMin, heap construction
Review for Exam 2
B-Trees
– What is a B-tree
• Special M-way search tree (what is a M-way tree)
• Internal and external nodes
• M and L (half full principle), especial requirement for root
– Why need B-tree
• Useful/advantageous only when external storage accesses
required and why?
• Height O(logM N), performances for find/insert/remove
– B-tree operations
• search
• insert (only insert to nonempty leaf, split, split propagation)
• Remove (borrow, merge, merge propagation, update ancestors’
keys )
– B-tree design
• determining M and L based on the size of key, data element,
and disk block