Блог

Главная - Вопросы по программированию - Разные деревья AVL из одного бинарного дерева поиска?

Разные деревья AVL из одного бинарного дерева поиска?

#algorithm #data-structures #tree #binary-search-tree #avl-tree

#алгоритм #структуры данных #дерево #двоичное дерево поиска #avl-tree

Вопрос:

Я не уверен, можем ли мы сгенерировать более одного дерева AVL из заданного BST.

Я пытался это сделать, и я получаю ответ, но я не знаю, правильно это или неправильно.

Ответ №1:

Конечно. Рассмотрим следующий BST:

        [4]
       /
     [3]
     /
   [2]
   /
 [1]

Его можно реорганизовать как минимум в 2 разных дерева, которые являются правильными AVL:

 #1:             #2:
     [3]             [2]
    /              /   
 [1]     [4]     [1]     [4]
                        /
   [2]                 [3]

Комментарии:

1. Только 2? Разве мы не можем получить более 2 разных типов дерева AVL для одного BST?

2. @SmitkumarRathod Конечно, в целом количество потенциальных AVL не ограничено 2. Тем не менее, вы спросили, возможно ли сгенерировать более одного, поэтому я придумал простейший пример «более одного» =)