Справка: Меня попросили ответить на этот вопрос в интервью @MS SDE, в третьем раунде. И это не проблема домашней работы. Я также подумал и упомянул о моем подходе ниже.
Вопрос: Измените BST так, чтобы он стал как можно более сбалансированным. Разумеется, вы должны сделать это максимально эффективно.
Подсказка:
Интервьюер сказал, что это логичный вопрос, если вы думаете по-другому, вы получите ответ. Не было сложного кодирования.
→ Сказав это, я не думаю, что он ожидал, что я укажу на деревья AVL/RB.
Мое решение: Я предложил, чтобы я сделал обход дерева, взял средний элемент в качестве корня нового дерева (давайте назовем его новым корнем). Затем перейдите в левую часть среднего элемента, возьмите его средний элемент как корень из левого поддерева корневого дерева с корнем. Точно так же для правой части. Выполнение этого рекурсивно даст оптимальный баланс BST.
Почему я размещаю его здесь: Но он не был доволен ответом: (Итак, есть ли способ сделать это без участия стратегии весов/RB-раскраски, или он просто обманывал меня? Пожалуйста, внесите свои мысли.
Duplicate? Нет! Я знаю, что это question, но предлагаемое реквестером решение слишком сложное, а другое говорит о деревьях AVL.