[理工] AVL Tree Rotation次数 maple205 PTT批踢踢实业坊

楼主: maple205 (è‰¾ç‘žå…‹) 2018-12-24 16:46:22

请问AVL做insert最多roatation到底是1还是2次。
两种说法都看过，弄得我好乱...

作者: b0920075 (Void) 2018-12-24 16:57:00

rotate最多的是O型腿那种，应该两次吧

作者: magic83v (R7) 2018-12-24 17:07:00

请问哪里有说是1或2次0.0

作者: sdfg014025xx (随便就好) 2018-12-24 17:08:00

算法的定义是single 和 double 资结定义的话新增是一种(RR or LR etc.)算法的话就是2(最多一次double) 但我不是很确定有错还请别人补充

作者: AliennC 2018-12-24 17:22:00

double rotation 最多一次 (RL & LR)，但有些书把 double rotation 视为两次旋转，因为 single rotation (LL &RR) 只需改变两个指标，而double rotation 会改变四个指标，所以才有两种说法

楼主: maple205 (è‰¾ç‘žå…‹) 2018-12-24 17:36:00

对就是楼上说得那样，但考试要依哪种呢？

继续阅读