Блог пользователя IlyaCk

Автор IlyaCk, 12 лет назад, По-русски

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

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

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

         5
     3         8
             7   9

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

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

        5
               8
             7   9

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

           8
     5         9
       7

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

          7
     5         8
                 9

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

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

.

»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

А вообще виды балансировок детерминированы в зависимости от балансов вершин. http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Как я понял, по указанному адресу всего лишь утверждается: "делать так — правильно". Но не_утверждается "против любого другого способа существует контрпример".

    Если я как препод буду заявлять студентам "раз ты при diff[a]=-2, diff[b]=0, diff[c]=0 использовал большой левый поворот вместо малого левого — ты категорически не прав, иди переделывай", то я буду прав или буду сам дурак?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Ну вроде бы все очевидно: можно говорить, что студент не прав, только в том случае, если после его поворота испортилось главное свойство АВЛ-дерева.

      А по поводу жесткости правил... Понятно, что они не являются таковыми. Например, в обозначениях, которые приняты по ссылке выше, если (diff[a] = -2, diff[b] = 0, diff[c] = 0), то мы можем применить как малое, так и большое левое вращение (это можно легко проверить, нарисовав высоты, и посмотрев, не нарушается ли основное правило по поводу разности поддеревьев).

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Как сказал однажды Капун: "Пиши так, чтобы работало на тестах"

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        можно говорить, что студент не прав, только в том случае, если после его поворота испортилось главное свойство АВЛ-дерева

        Точно ли?

        Утрируя в противоположную сторону, рассмотрим ситуацию: пусть задание было сформулировано "сократить дробь и объяснить процесс". Пусть был дан правильный ответ , а в качестве аргументации было сказано "зачеркнём шестёрки". По-Вашему, надо сказать, что решение правильно?

        И, да, вопрос о том, что делать, когда это всё проверяется не тестами, а руками.

»
6 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Up-ну эту старую тему, т.к. вопрос всё ещё интересует.