algorithms/ads/1

[giscus[bot]]

algorithms/ads/1

NoughtQ的笔记本

https://note.noughtq.top/algorithms/ads/1

[au12321ua]

splay tree的挪还分析不使用树高作为势能函数，更多是出于树高不一定是O(log N)的考虑吧。
另外如果用所有节点的树高和作为势能函数，高度变化的节点好像也是至多有3个（你貌似把深度和高度混淆了🤔）。

[NoughtQ]

这里可能是我表述有些问题（毕竟当时是第一次学）。我这边的意思是将树的根节点的高度作为势能函数，而不是所有节点的树高。按照我的意思，在访问某个节点后，该节点就会通过一系列的旋转上升至根节点，但整棵树的高度没有特别大的变化，因而这样的势能函数无法体现伸展树的结构特征，表现不是很好

[yifanjiang00]

你好，似乎“LL 用左旋，RR 用右旋”的说法反了，应该是“LL用右旋，RR用左旋”🤔

[NoughtQ]

其实到期末复习的时候，我就不去记左右旋了（可参看“我的记忆法”），感觉“旋转”的说法不太形象，所以我不想管这个烂摊子了（逃x）

[RanderDouble]

LR过程演示图中 后[左旋]的文字解释似乎有错误"然后，通过左旋交换原来的孙子节点（现在是子节点）与 trouble maker（红色）的位置" 一句中的 trouble maker应为trouble finder

[NoughtQ]

雀食笔误了，感谢指正🙏