Двоичные вращения деревьев

16

Сбалансированные двоичные деревья поиска необходимы для обеспечения O (log n) поиска (или аналогичных операций). В динамической среде, где множество ключей вставляются и / или удаляются случайным образом, деревья могут вырождаться в связанные списки, которые ужасны для поиска. Таким образом, существуют различные виды самобалансирующихся двоичных деревьев, которые противодействуют этому эффекту (например, деревья AVL или деревья расширения ). Эти деревья основаны на различных видах поворотов, которые перебалансируют дерево.

Повороты

В этой задаче мы рассмотрим только одиночные правые повороты, такой поворот (левый поворот будет симметричным) выглядит следующим образом:

    5            3
   / \          / \
  3   6   =>   1   5
 / \              / \
1   4            4   6

Если какой-либо из листьев 1, 4или 6имеет левое или правое поддеревья, вращение будет просто держать их там. Если это поддерево большего дерева, мы бы просто «обрезали его» в узле 5и «заново прикрепили» повернутое дерево (теперь узел 3) к этому узлу.

Вызов

При заданном бинарном дереве поиска 1 и ключе поверните дерево вправо на этом узле, как описано выше. Ключ, предоставленный в приведенном выше примере, будет 5.

Правила и ввод / вывод

  • Вы можете использовать любой тип для ключей, если существует разделение между ключами по вашему выбору и ключами тестовых случаев.
  • Вы можете выбрать любое представление для бинарных деревьев, если нет двусмысленности (например, [3,[]]двусмысленно, если не указано иное), и это естественно для вашего языка по вашему выбору
  • поскольку вход всегда будет бинарным деревом поиска, дублирующихся ключей нет
  • вы можете предположить, что ключ содержится в дереве
  • вы можете предположить, что узел, содержащий ключ, имеет левого потомка
  • Вы не можете принять правильное поддерево под предоставленным ключом
  • Вы не можете предполагать, что дерево не сбалансировано перед вращением
  • вы не можете предполагать, что дерево сбалансировано после поворота
  • Вы можете использовать любой метод ввода / вывода по умолчанию
  • ваша заявка может быть функцией, возвращающей дерево или полной программой печати решения

Контрольные примеры

Эти примеры представляют дерево следующим образом

  • если это лист: []
  • если это дерево с ключом xи оба поддерева являются листьями:[x]
  • если это дерево с ключом xи поддеревьями left right:[x,left,right]

Первый пример приведен в разделе « Повороты» . Если по какой - то причине вам нужно графическое представление о них, здесь 2 вы идете.

5 [5,[3,[1],[4]],[6]]  ->  [3,[1],[5,[4],[6]]]
5 [5,[3,[1],[4]],[]]  ->  [3,[1],[5,[4],[]]]
5 [5,[3,[],[4]],[6]]  ->  [3,[],[5,[4],[6]]]
5 [5,[3,[1],[]],[]]  ->  [3,[1],[5]]
4 [8,[4,[2,[1],[3]],[6,[5],[7]]],[12,[10,[9],[11]],[14,[13],[15]]]]  ->  [8,[2,[1],[4,[3],[6,[5],[7]]]],[12,[10,[9],[11]],[14,[13],[15]]]]
8 [10,[8,[6,[4,[2,[],[3]],[5]],[7]],[9]],[11]]  ->  [10,[6,[4,[2,[],[3]],[5]],[8,[7],[9]]],[11]]
10 [10,[8,[6,[4,[2,[],[3]],[5]],[7]],[9]],[11]]  ->  [8,[6,[4,[2,[],[3]],[5]],[7]],[10,[9],[11]]]
9 [6,[3,[2],[5]],[9,[8],[12,[11],[15,[14],[]]]]]  ->  [6,[3,[2],[5]],[8,[],[9,[],[12,[11],[15,[14],[]]]]]]
7 [7,[5,[3,[1],[4]],[6]],[8]]  ->  [5,[3,[1],[4]],[7,[6],[8]]]
15 [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]  ->  [17,[9,[5,[2,[0],[4]],[8]],[13,[11,[10],[12]],[15,[14],[16]]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]
21 [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[21,[19,[18],[20]],[24,[22],[25]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]  ->  [17,[9,[5,[2,[0],[4]],[8]],[15,[13,[11,[10],[12]],[14]],[16]]],[40,[27,[19,[18],[21,[20],[24,[22],[25]]]],[28]],[44,[42,[41],[]],[51,[47],[59,[55],[61]]]]]]

1: означает, что для любого узла все ключи в левом поддереве будут меньше, чем этот ключ, а все ключи в правом поддереве больше его

2: чтобы не допустить гниения ссылок, я вставил их как комментарий

code-golf graph-theory data-structures binary-tree ბიმო
источник

Ответы:

8

Haskell , 93 92 84 83 82 байта

data B=B[B]Int|L
k!B[l@(B[x,y]a),r]n|k<n=B[k!l,r]n|k>n=B[l,k!r]n|1>0=B[x,B[y,r]k]a

Спасибо @BMO, @alephalpha и @Laikoni за каждый байт и @nimi за восемь байт!

Попробуйте онлайн!

Angs
источник
Использование data B=B[B]Intпозволит сохранить еще несколько байтов.
Лайкони
@Laikoni только один байт, я думаю, но я возьму это
Angs
Вы можете сохранить 2 байта, сначала объединив два случая, k<n=B[k!l,r]nи k>n=B[l,k!r]n, в один:, k/=n=B[k!l,k!r]nа затем добавив, k!x=xчтобы сделать сопоставление с образцом исчерпывающим.
Радек
5

Vim , 25 байт

Берет ввод в буфер - разделенный пробелом ключ и дерево. Ожидается, что дерево будет представлено следующим образом:

  • лист: []
  • узел с ключом k, левой дочерней <left>и правой дочерней <right>:[ k <left><right>]

Не пробелы вокруг ключа, kкоторые важны, так что решение работает для произвольных деревьев.

"adw/ <C-r>a⏎3dw%l"apr[%xl%i]

Попробуйте онлайн!

объяснение

"adw                           " delete the key and trailing space, keep in register a
    / <C-r>a⏎                  " move cursor to the key surrounded with spaces
             3dw               " remove key and [ (move left node to top)
                %l             " move cursor to the right subtree
                  "ap          " insert key there
                     r[        " insert a [ (appending subtree to key)
                       %       " move to the end of new left subtree
                        x      " remove ] (fix parentheses)
                         l%    " move to the end of new right subtree
                           i]  " insert ] (fix parentheses)

предварительный просмотр

Вот предварительный просмотр первого контрольного примера, созданного с помощью этого сценария Линн :

                       Vim Предварительный просмотр

ბიმო
источник
3

Wolfram Language (Mathematica) , 30 байтов

#2/.a_~b_~c_~#~d_:>b[a,c~#~d]&

Попробуйте онлайн!

Дерево представлено следующим образом:

  • если это лист: $(вы можете заменить его любым значением, которое не является ключевым)
  • если это дерево с ключом xи поддеревьями left right:x[left,right]

Например, дерево в первом тестовом примере представлено как 5[3[1[$,$],4[$,$]],6[$,$]].

Объяснение:

#2                                the second input
  /.                              replace
    a_~b_~c_~#~d_                 #[b[a,c],d], where # is the first input
                 :>               by
                   b[a,c~#~d]     b[a,#[c,d]]
                             &    define a function
alephalpha
источник
3

Common Lisp, 146 байт

(defun r(k a)(cond((not a)a)((=(car a)k)`(,(caadr a),(cadadr a)(,(car a),(car(cddadr a)),(caddr a))))(t`(,(car a),(r k(cadr a)),(r k(caddr a))))))

Попробуйте онлайн или проверьте все тестовые случаи!

Дерево представляется следующим образом:

  • пустое дерево представляется как nil(или эквивалентно в Common Lisp как пустой список ())
  • непустое дерево представляется в виде списка из трех элементов (node left-subtree right-subtree) (таким образом, лист Lпредставляется как (L nil nil)).
Renzo
источник
2

JavaScript (Node.js) , 70 байт

n=>f=a=>n-a[0]?(a[i=n<a[0]?1:2]=f(a[i]),a):(i=a[1],a[1]=i[2],i[2]=a,i)

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Все узлы должны иметь левые и правые записи, но они могут указывать []на отсутствие поддерева на этой стороне. В качестве аббревиатуры набор тестов используется l(N)для указания того, что Nэто лист, и l(N,L)для указания того, что у Nнего есть левое поддерево, Lно нет правого поддерева как на входе, так и на выходе.

Нил
источник
1

Желе , 24 байта

ñ
Ḣ,1ịṪƊṭ@ṪṭḢð{Ḣ;ç€ɗ¹¡i?

Попробуйте онлайн!

Предупреждение: как правило, верхняя строка не должна существовать, а нижняя строка должна иметь, а ßнеç . Тем не менее, хитрые цепные трюки и ßне подходят друг другу, из-заßпеременная арность. Технически, я все еще мог бы опустить верхнюю строку, но тогда результатом должна была бы быть полная программа, так как в противном случае она должна была бы быть в состоянии включить ее как собственную строку в любую программу, что невозможно, если вы повезло. Это означает, что, к сожалению, выходные данные имели бы неоднозначное представление, потому что, когда вы отправляете полную программу, на самом деле учитывается то, что получено, а не то, что технически является результатом до закрытия программы. Поэтому, чтобы не путать рекурсию и правильное представление строки, я решил представить двухстрочную функцию, в которой задача верхней строки состоит в том, чтобы просто вызвать нижнюю. Следствие? Огромная трата 2 ценных и ценных байтов. В защиту Джелли (и Дениса, как и любого другого участника),

Эрик Outgolfer
источник