Вставка в Splay Tree

Опубликовано: 16 Февраля, 2023

Рекомендуется ссылаться на следующий пост как на предварительное условие этого поста.
Воспроизведение дерева | Набор 1 (Поиск)
Как обсуждалось в предыдущем посте, Splay-дерево — это самобалансирующаяся структура данных, в которой ключ, к которому последний раз обращались, всегда находится в корне. Операция вставки аналогична вставке двоичного дерева поиска с дополнительными шагами, чтобы убедиться, что вновь вставленный ключ становится новым корнем.
Ниже приведены различные случаи вставки ключа k в развернутое дерево.
1) Корень равен NULL: мы просто выделяем новый узел и возвращаем его как корень.
2) Нажмите данную клавишу k. Если k уже присутствует, то он становится новым корнем. Если нет, то последний доступный конечный узел становится новым корнем.
3) Если ключ нового корня такой же, как k, ничего не делайте, так как k уже присутствует.
4) В противном случае выделите память для нового узла и сравните корневой ключ с k.
……. 4.a) Если k меньше ключа root, сделать root правым дочерним элементом нового узла, скопировать левый дочерний элемент root в качестве левого дочернего элемента нового узла и сделать левый дочерний элемент root равным NULL.
……. 4.b) Если k больше ключа root, сделайте root левым дочерним элементом нового узла, скопируйте правый дочерний элемент root как правый дочерний элемент нового узла и сделайте правый дочерний элемент root равным NULL.
5) Вернуть новый узел как новый корень дерева.
Пример:

 
          100                  [20]                             25     
          /                                                  /  
        50   200                  50                          20   50 
       /          insert(25)     /          insert(25)           /    
      40          ======>      30   100      ========>           30  100    
     /          1. Splay(25)               2. insert 25             
    30                          40    200                         40   200   
   /                                                          
 [20]

Выход:

Preorder traversal of the modified Splay tree is
25 20 50 30 40 100 200

Эта статья составлена Абхай Ратхи . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.

РЕКОМЕНДУЕМЫЕ СТАТЬИ