week1 AVL Trees, Splay Trees and Amoritized Analysis
AVL Trees
Insert
RR LL LR RL
Delete
no child
only left/right child
left and right children: find smallest node in right child, swap and delete
Splay Trees
Find
每查询一次都将其旋转到根节点。
Delete
Find X —> Remove X —> FindMax(LTree) —> 将右子树作为左子树的右孩子
Amoritized Analysis
Aggregate analysis
Accounting method
Potential method
Week2 Red-Black Trees and B+ Trees
Red-Black Trees
Definition
A red-black tree with N internal nodes has height at most 2ln(N +1).
Insert
3 cases
Delete
delete a leaf node
delete a degree 1 node
delete a degree 2 node
关键是调整颜色：4 cases
B+ Trees
Definition
Insert
Delete
Week3 Inverted File Index
Some definition
Index
Inverted file
Key points
Word Stemming
Stop Words
Accessing a term: Search trees(B-trees,B+ trees, Tries,..) or Hashing?
Distributed indexing: Term-partitioned index and Document-partitioned index
Measures for a search engine: 1-How fast does it index? 2-How fast does it search? 3-Expressiveness of query language
Relevance measurement: Precise Recall
Week4 Leftist Heaps and Skew Heaps
Leftist Heaps
Definition
null path length
A leftist tree with r nodes on the right path must have at least \(b^2-1\) nodes.
Merge
recursive version and iterative version
DeleteMin
delete the root and merge the two subtrees
Skew Heaps
Definition
a simple version of the leftest heaps
Merge
Amortized Analysis for Skew Heaps
Week5 Binomial Queue
Definition
FindMin
Merge
DeleteMin
Implementation
left child and right next sibling
Performing N Inserts on an initially empty binomial queue will take O(N) worst-case time. Hence the average time is constant.