IlyaCk's blog

By IlyaCk, 12 years ago, In Russian

Вопрос вряд ли имеет прямую практическую ценность, но всё же...

Мне довольно долго казалось, что в АВЛ-деревьях правила выполнения поворотов совершенно жёсткие и не допускают разночтений (когда какой поворот выполнять).

Только что обнаружил, что в случае с удалениями это не всегда так. Пусть есть дерево:

         5
     3         8
             7   9

(у корня 5 слева — лист 3, справа — поддерево с тремя вершинами).

Удаляя вершину 3, получаем ситуацию

        5
               8
             7   9

к которой возможно применять хоть левый поворот, получая

           8
     5         9
       7

хоть право-левый, получая

          7
     5         8
                 9

1) Правда ли это?

2) Есть ли ещё какие-то случаи, когда правила работы с АВЛ-деревьями допускают неоднозначность? (кроме только что упомянутого и кроме того, что при удалении можно брать либо наименьший элемент правого поддерева, либо наибольший элемент левого)

  • Vote: I like it
  • +8
  • Vote: I do not like it