Я знаю концепцию дерева двоичного поиска и полного двоичного дерева. Есть ли способ написать алгоритм вставки для полного дерева двоичного поиска или я думаю о неправильной структуре данных?Вставка узла динамически в полное дерево двоичного поиска
Моя цель - каждый раз, когда мы вставляем узел, Дерево должно оставаться полным двоичным деревом поиска.
Конечно, вы можете. Но это будет O (N) алгоритм, просто перестройте дерево после каждой вставки или удаления.
Вы не можете сделать это быстрее, чем время O (N). Потому что:
1) Существует только 1 полное дерево с заданными клавишами.
2) Вы можете удалить или вставить минимальное значение, и вам нужно будет изменить все дерево (расходы на операции O (N)).
Вместо полного поиска бинарных деревьев используются сбалансированные двоичные деревья (например, RB, AVL, декартовы, Splay и т. Д.).
Я проверю AVL и сбалансированное двоичное дерево. Если вы не возражаете, можете ли вы предоставить алгоритм для моего вопроса? – javafan
В вашем определении, что представляет собой полное двоичное дерево поиска (в отличие от простого BST)? Я считаю, что вы действительно можете найти сбалансированное двоичное дерево. –
Обычно называется AVL или красно-черным деревом –