CSE 373 Lecture Notes - Lecture 6: Linked List, Binary Heap, Priority Queue
17 May 2018
School
Department
Course
Professor
CSE 373 Lecture 6
Maximize disk access effort by having a tree with M children (rather than 2)
- Pick a size M that fills an entire page of disk data
- If balanced, height: logm(n)
- Worst case get() runtime:
o Log2(m) – to pick a child
o Logm(n) * log2(m) to find a node
- What if we store keys in branch nodes, and values in leaf nodes
B Tree
- L = number of items in leaf nodes (KV pairs)
- M = number of pointers to children (number if children root can have
- N = number of elements in tree
- If n <= L, root is a leaf node
o Otherwise, it’s a branch
- 3 requirements (invariants)
o Two types of nodes – internal nodes + leaf nodes
▪ Internal node
• Contains M pointers to children
• M – 1 sorted keys
▪ Leaf node
• Contains L key-value pairs, sorted by key
o Order invariant - Must have an organized set of keys + pointers at each internal
node
o Structure invariant - Must start with a leaf node
▪ As more nodes are added, they must stay at least half full
▪ When n > L, root node must be an internal node containing 2 to M
children
▪ Internal nodes – must have M/2 to M children
▪ Leaf nodes – must have L/2 to L children
▪ All nodes must be at least half full
• Only exception: root, which can have as few as 2 children
▪ This helps maintain balance + prevents degenerate linked list trees
Document Summary
Maximize disk access effort by having a tree with m children (rather than 2) Pick a size m that fills an entire page of disk data. Worst case get() runtime: log2(m) to pick a child, logm(n) * log2(m) to find a node. What if we store keys in branch nodes, and values in leaf nodes. L = number of items in leaf nodes (kv pairs) M = number of pointers to children (number if children root can have. N = number of elements in tree. If n <= l, root is a leaf node: other(cid:449)ise, it"s a (cid:271)ra(cid:374)(cid:272)h. 3 requirements (invariants: two types of nodes internal nodes + leaf nodes. Max priority queue adt same as min, but largest priority. Avlpriorityqueue removemin() traverse through tree all the way to left, remove node, rebalance if needed. Binary heap type of tree w new set of invariants. Binary tree: every node has a t most 2 children.
