Понимание этой техники вставки BST

Я думал, что понимаю BST. Так было до тех пор, пока не появился мой профессор.

Допустим, у меня есть BST:

   2
  / \
 1   3

Теперь, если бы я вставил 4, мое дерево выглядело бы так:

   2
  / \
 1   3
      \
       4

но дерево моего Профессора закончилось бы так:

   2
  / \
 1   4
    / \
   3   4

По сути, он находит, где должен быть размещен новый узел, и размещает его там. Затем он изменяет значение родителя нового узла на значение нового узла и делает левого дочернего элемента родителя таким, каким раньше был исходный родительский узел.

Я искал в Интернете, но не могу найти никого, кто это делает.

Что это за техника введения? Я что-то упускаю? Я не думаю, что это будет иметь значение, но это было специально для деревьев AVL.


insert avl-tree binary-search-tree
person aanrv    schedule 19.03.2015    source источник
comment
В BST left/right дочерние должны быть меньше, чем родительские. (например, дочерний элемент 3 должен быть ниже 4 с правой стороны) См. Вставка элемента в двоичном дереве   -  person David C. Rankin    schedule 20.03.2015
comment
@DavidC.Rankin Левый и правый дети должны быть меньше? Разве это не сделает максимальную кучу?   -  person aanrv    schedule 20.03.2015

Ответы (2)


arrow_upward
0
arrow_downward

Я думаю, что он пытается сохранить дерево строго бинарным, т. Е. Каждый узел имеет 0 или ровно 2 дочерних элемента.

Как я понимаю, в примере первая и вторая четверки добавляются на свои места. Вращение влево (необходимое для балансировки дерева avl) придает окончательную форму.

person sray    schedule 20.03.2015

arrow_upward
0
arrow_downward

Уверяю вас, что вы вставили ключ "4" в BST полностью правильно. Это ортодоксальный и самый простой способ вставки элементов в BST.

Я думаю, что вы неправильно поняли своего профессора, потому что ваша третья иллюстрация неверна хотя бы из-за того, что в BST не допускаются дубликаты, и у вас есть элемент "4", встречающийся дважды.

person Vladimir    schedule 20.03.2015