DSA - 问题集第六章

没有浮木大学物理，让我们学大学物理是要干什么。
有幸选中炸雷老师，口音奇特听不明白，仔细研读 ppt + 完成所有课本习题，喜提期末 3 道大题看不明白在说什么。期末周做题区 u1.4 了。
毛病考试考的学的十万八千里考场上效仿法兰西

还要复习够使的数据结构和 OOP。

每个节点设置计数器，插入重复元素 count++，，删除–，只有 count==0 且在删除时才真正移除节点。

节点的拓扑结构。有一个子树和没有子树都是 O (depth)+O (1)，有两个子树是 O (depth)+O (succ)

一棵二叉搜索树可能对应多个插入序列

$S (T)=(^{N-1}_{L}) S (L_T) S (L_R)$ 除去根节点，剩下 N-1 个节点中挑 L 个给左边，相当于根节点选的是从小到大第 L + 1 个。

平衡的话系数最大，且在每一层递归中这样最大的系数都在发生。

$S (n)=\sum {S (k-1)*S (n-k)}$，选一个节点做根，小的分到左子树大的分到右子树。

单调：退化成链表

局部：某个子树规模特别大其他特别小

周期：由于内部还是那么几条单调链，最后还是几条链表

对一棵树，只要当前节点有左孩子就右旋，直到没有左孩子，转向右孩子。这样一来一棵树就变成了一条右侧链，且旋转不超过 n-1 次。而 zig / zag 互为逆操作，于是可以把 T1 转成链，T2 转成链，T2 转链路径取逆接在 T1 路径后面。最坏不超过 2n-2=O (n) 次。NP 难问题。

$S (h)=1 + S (h-1)+S (h-c-1)$,特征方程 $x^{c+1}-xc-1=0,1/log_2{r_c}$

18：因为新接入的节点是作为叶子；父亲原先一只手是空的，说明另一边只可能有 1 个或者没有元素，接入后不会失衡；原先父亲是叶子节点，而且其他所有祖先的平衡因子都是 ±1, 说明插入路径上的树结构是一棵斐波那契树且向 x 倾斜；不一定。如果中间的祖先原来左右子树是平衡的，新加入节点不会使得自己失衡，但是依然传递增加了的高度。

19：因为删掉的也是叶子，不影响非祖先的子树情况。假设 P 原先处于临界，一边 h 一边 h-1, 删掉一个之后一边变成了 h-2, 但是这个失衡节点的高度不变所以在旋转之前不会向上传递。父亲原本就临界了。

21：

除非有红色块块否则高度 - 1。因为转了之后高度可能会变。如果局部子树的高度不变，从最后旋转处到根节点的所有祖先的高度都不会再 - 1，也就保证了原来平衡的现在依然平衡。

平衡因子 = 0：有红块 =》平衡因子≠0=》不需要上溯

插入引发的旋转操作只有 1 次，无论单双。

a)，删除右藤蔓的最后一个节点。该节点处在 h 的高度处，且删除导致祖先路径上所有节点都将失衡，而且都是 LL 单旋。

b），构造交替出现平衡因子 + 1,-1 的斐波那契树。相当于隔一层把原先向一边倾斜的斐波那契树左右子树调换。删除最浅的叶子节点。