Реконструкция BST в AVL

Как вы можете восстановить данный BST в AVL, который содержит точно такие же клавиши? Время работы алгоритма должно быть O (n), и его разрешено использовать O (n) дополнительное пространство. Есть идеи? Весь псевдокод не нужен, любая идея или предложение будут оценены! Спасибо!Реконструкция BST в AVL

источник

2013-08-27 dvainrub

просит вас, как превратить POTEN неравновесное двоичное дерево в сбалансированное дерево (AVL)? Проводили ли вы какие-либо исследования по этому поводу? –

Найдите каждый неуравновешенный узел и сбалансируйте его. Я. это самый простой способ. Начинайте с листьев, а затем поднимайтесь вверх. – anon

Экстракт все ключи к отсортированного массива (О (п) пространство) с подходящим способом обхода (О (п) времени)
Построить идеально сбалансированное дерево из отсортированного массива (O (N) время) (одновременно заполняя AVL факторов баланса для всех узлов)

Я в опустило детали для ваших собственных исследований

источник

2013-08-28 05:09:53 MBo

Реконструкция BST в AVL

ответ

Смежные вопросы