Баланс BST дерево вручную - PullRequest
       32

Баланс BST дерево вручную

1 голос
/ 06 декабря 2010

Я выполнил балансировку дерева (bst> avl), запрошенного вручную, и мне интересно, что это было действительно легко, поэтому я не уверен, правильно ли я это сделал.

a
       / \
      b  e3
     / \
    e1 e2

начальное состояние: «a» является родителем «b» (слева) и «e3» (справа), «b» является родителем «e1» (слева) и «e2» (справа).

применение правого поворота дает нам:

b
       / \
     e1   a
         / \
       e2   e3

'b' вместо 'a' с дочерним элементом 'e1' слева и 'a' дочерним элементом справа, 'a'получает 'e2' от 'b' слева.

Итак, вопросы:

  1. Если e1 само по себе является поддеревом или узлом, содержащим другие элементы, могу ли я сделать это вращение?
  2. 2.Если e2 и e3 отсутствуют, могу ли я сделать это вращение?

пример 11;12; 16

16
     /
   13
  /
10

начальное состояние: 16 является родителем 13 и 13 является родителем 10. Могу ли я сделать из этого: 13 является родителем 10 (слева) и 16 (справа)

Я знаю, что это упрощенно, но теория часто не покрывает эти вещи, предполагая, что это понятно, ну, не для всех.Спасибо за помощь,

1 Ответ

0 голосов
/ 06 декабря 2010

Да всем, правда. Подумайте о свойстве порядка: левые потомки <узел, а узел <правые потомки. Обратите внимание, как вращение сохраняет это; сравните a и b с e1, e2 и e3 до вращения и проверьте порядок и отношения потомков после вращения. Я позволю вам подумать, прежде чем отдать его. </p>

...