Не могу понять, как работают раскачки

Question

Я не могу понять, как работает распутывание.
Часть, за которой я не могу следовать, - это то, как мы знаем, если: i) zig ii) zig-zag или iii) zig-zig необходимо сделать.
Если я правильно понимаю, это связано с текущим узлом пути.
Если это корневой корень, то в противном случае это либо (ii), либо (iii) в зависимости от того, являются ли родители текущего узла и текущего узла левыми (или правыми) дочерними. Хорошо, пока.
Теперь часть, которую я не получаю:
Поскольку мы перемещаемся вниз, это не процесс «удаления» промежуточных узлов в левое и правое поддеревья, так что у нас есть среднее дерево, которое в конечном итоге станет корнем элемента под поиском?
Тогда, если мы начнем с дерева, мы будем постоянно делать zig, и ничего больше, поскольку мы удаляем элементы и всегда находимся в корне.
Пример:

Если, например, я ищу 20 Я хотел бы начать с корнем и идите налево. Таким образом, текущий узел имеет корень как родительский, и я делаю зигзаг. Теперь что происходит? Я нахожусь в 26 и идите налево, но не 26 также корень? Так что я должен делать зигзаг?
Но из того, что я вижу в этом примере, выполняется зигзаг, и я не понимаю, почему.
Любая помощь здесь?

Answer 1

Под корень они означают корень всего дерева, а не корень поддерева, который вы раскладываете. Итак, в вашем примере 12 - корень всего дерева.

...

Если вы хотите пример, чтобы работать с, я закодирован вверх расширяющимся деревом в Java в последнее время. Вы можете найти код here.

Большая вещь с splay tree заключается в том, что они перемещают самый последний вставленный/запрошенный узел вверх (максимум) двух уровней в дереве. Вы должны выполнить зигзагообразный, зигзагообразный или зигзагообразный, основанный на его родительских и родительских узлах.

Когда доступ к узлу x, операция xplay выполняется на x, чтобы переместить его в корень. Чтобы выполнить операцию воспроизведения, мы выполняем последовательность шагов splay, каждая из которых перемещается x ближе к корню.

Три типа шагов расширяющихся является: (г = гранд родителя, р = родитель, и х = узел скошенного)

• Зига Шаг: Этот шаг выполняется, когда р является корнем. Дерево повернуто на краю между x и p.
• Zig-zig Step: Этот шаг выполняется, когда p не является корнем, а x и p являются либо обеими детьми, либо являются обоими левыми детьми. Дерево поворачивается по краю, соединяющему p с его родительским g, затем повернутым на кромке, соединяющей x с p.
• Zig-zag Шаг: этот шаг выполняется, когда p не является корнем, а x является правильным потомком , а p является левым ребенком или наоборот. Дерево поворачивается по краю между x и p, а затем поворачивается по краю между x и его новым родителем .

http://en.wikipedia.org/wiki/Splay_tree

Ниже splaying узла 3 в дереве.

Дерево перед тем splaying:

└── 0 
    └── (right) 9 
     └── (left) 7 
      ├── (left) 5 
      │ ├── (left) 1 
      │ │ └── (right) 2 
      │ │  └── (right) 4 
      │ │   └── (left) 3 
      │ └── (right) 6 
      └── (right) 8 

После того, как (право-> слева) зигзагообразный к узлу 3.

└── 0 
    └── (right) 9 
     └── (left) 7 
      ├── (left) 5 
      │ ├── (left) 1 
      │ │ └── (right) 3 
      │ │  ├── (left) 2 
      │ │  └── (right) 4 
      │ └── (right) 6 
      └── (right) 8 

После очередного (лево-> справа) зигзагообразный к узлу 3.

└── 0 
    └── (right) 9 
     └── (left) 7 
      ├── (left) 3 
      │ ├── (left) 1 
      │ │ └── (right) 2 
      │ └── (right) 5 
      │  ├── (left) 4 
      │  └── (right) 6 
      └── (right) 8 

После (лево-> слева) зиг-Zig к узлу 3.

└── 0 
    └── (right) 3 
     ├── (left) 1 
     │ └── (right) 2 
     └── (right) 7 
      ├── (left) 5 
      │ ├── (left) 4 
      │ └── (right) 6 
      └── (right) 9 
       └── (left) 8 

После (справа) Zig на узел 3. Теперь время остановки, так как 3 находится в корневой позиции.

└── 3 
    ├── (left) 0 
    │ └── (right) 1 
    │  └── (right) 2 
    └── (right) 7 
     ├── (left) 5 
     │ ├── (left) 4 
     │ └── (right) 6 
     └── (right) 9 
      └── (left) 8t) 6 
       └── (right) 9 
        └── (left) 8 

Если вы попробуете и узел доступа 3 раз в дереве, он не должен быть растопыренными, так как он уже находится в корневой позиции.