[高级数据结构] Week 1 Note

《数据结构与算法分析》

《Algorithm Design》

Grading Policies

• Homework 10
• Discussions 10
• Research Project(20) + Presatation(6) + Peer review(4) 30
• MidTerm 10
• Final 40

7 topics，at most 4 groups will be chosen，随机一个人展示。第一个小组12分钟，之后的小组不讲重复内容。bonus 是Project 的十分之一。

AVL Adelson-Velskii-Landis(AVL) Trees

定义 Define

1.左子树与右子树是高度平衡的。

2.左子树与右子树的高度差小于等于1。

BF(node) = H_L – H_R，在AVL树中，BF = -1,0或1

*当出现BF不合法时，对AVL树进行调整。

平均访问：O(logN)

调整

Insert Node -> Update BF(Node) 更新插入路径上的节点的信息

Trouble Maker：插入后产生不平衡的节点

Trouble Finder：BF信息不合法的节点

RR（两个右子树） Rotation 左旋：

TM在TF右子树右节点插入导致失衡。

LL（两个左子树）Rotation 右旋：

TM在TF左子树左节点插入导致失衡。

左旋和右旋使用局部调整，高度一致，不需要向上检查平衡因子信息。

LR（TroubleFinder左子树的右子树）先左旋后右旋：

先左旋左子树的右节点，再右旋该节点。

RL（TroubleFinder右子树的左子树）先左旋后右旋：

先右旋右子树的左节点，再左旋该节点。

如何保证Tp = O(H)？

1. 给定高度最少的节点数
2. 给定节点数最大的高度

Splay Trees

M个连续的Splay tree操作，操作代价O(MlogN)。

局部性原则（计算机哲学？）

Delete 删除

1.找到X，将X移到root

2.删除X。

3.FindMax(T_L)，把它翻转到root上。

4.把T_R作为T_L的右子树。

Amortized Analysis 均摊分析

Amortized time bound：Any M consecutive operations take at most O(M log N) time.

Aggregate analysis

聚合分析：表明对于所有n个操作，n个操作的序列总共占用最坏情况时间T（n）。在最坏的情况下，每项操作的平均成本或摊余成本为T（n）/n。

Accounting method

Potential method