Динамическая вставка узла в полное дерево двоичного поиска

Question

Я знаю концепцию бинарного дерева поиска и полного бинарного дерева. Есть ли способ, которым мы можем написать алгоритм вставки для полного бинарного дерева поиска, или я имею в виду неправильную структуру данных?

Моя цель заключается в том, чтобы каждый раз, когда мы вставляли узел, дерево должно оставаться полным бинарным деревом поиска.

Answer 1

Конечно вы можете. Но это будет алгоритм O(N), просто перестраивать дерево после каждой вставки или удаления.

Вы не можете сделать это быстрее, чем за время (N). Так как:

1) Существует только 1 полное дерево с заданными ключами.

2) Вы можете удалить или вставить минимум, и вам придется изменить все дерево (стоит вам O(N) операций).

Вместо полного поиска бинарных деревьев используются сбалансированные бинарные деревья (такие как RB, AVL, декартово, Splay и т. Д.).