AVL Rotation — какой узел вращать

Я прочитал много источников о деревьях AVL, но не нашел никого, кто занимался бы этой проблемой: когда дерево AVL становится несбалансированным, какой узел следует вращать первым?

Предполагая, что у меня есть дерево:

    10
   /  \
   5   25
       / 
      20

и я пытаюсь добавить 15, и корень, и его дочерний 25 будут несбалансированы.

    10
   /  \
   5   25
       / 
      20
      /
     15

Я мог бы сделать вращение RR (или одно вращение) 25, в результате чего получилось бы следующее дерево:

     10
    /  \
   5    20
        /\
      15  25

или поворот RL (двойной поворот) вокруг корня, создавая следующее дерево:

    20
   /  \
  10   25
 /  \     
5   15   

Я запутался, какое вращение является наиболее подходящим здесь и в подобных случаях.


person DR29    schedule 08.10.2016    source источник


Ответы (1)


Вращение RR здесь правильное. Ротация должна быть сделана, как только правило будет нарушено. Который здесь за 25.

Более высокие вращения, во-первых, не обязательно нарушают правило, а во-вторых, станут слишком сложными, хотя на первый взгляд здесь так не кажется.

person Zbynek Vyskovsky - kvr000    schedule 08.10.2016