作者maple205 (正取)
看板Grad-ProbAsk
标题[理工] AVL Tree Rotation次数
时间Mon Dec 24 16:46:22 2018
请问AVL做insert最多roatation到底是1还是2次。
两种说法都看过，弄得我好乱...
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.233.66.10
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1545641185.A.C77.html
1F：推 b0920075: rotate最多的是O型腿那种，应该两次吧12/24 16:57
2F：推 magic83v: 请问哪里有说是1或2次0.012/24 17:07
3F：推 sdfg014025xx: 演算法的定义是single 和 double 资结定义的话新增12/24 17:08
4F：→ sdfg014025xx: 是一种(RR or LR etc.)演算法的话就是2(最多一次dou12/24 17:08
5F：→ sdfg014025xx: ble) 但我不是很确定 有错还请别人补充12/24 17:08
6F：推 AliennC: double rotation 最多一次 (RL & LR)，但有些书把 doubl12/24 17:22
7F：→ AliennC: e rotation 视为两次旋转，因为 single rotation (LL &12/24 17:22
8F：→ AliennC: RR) 只需改变两个指标，而double rotation 会改变四个指12/24 17:22
9F：→ AliennC: 标，所以才有两种说法12/24 17:22
10F：→ maple205: 对 就是楼上说得那样，但考试要依哪种呢？12/24 17:36
※ 编辑: maple205 (118.233.66.10), 12/24/2018 19:52:53