Операции с двоичным деревом поиска: вставка
Вставка начинается так же, как начинается поиск; если ключ не равен ключу корня, мы ищем левое или правое поддерево, как и раньше. В конце концов, мы достигнем внешнего узла и добавим новую пару ключ-значение (здесь закодированную как запись 'newNode') в качестве его правого или левого потомка, в зависимости от ключа узла. Другими словами, мы проверяем корень и рекурсивно вставляем новый узел в левое поддерево, если его ключ меньше ключа корня, или правое поддерево, если его ключ больше или равен корню.
Вот как типичная вставка двоичного дерева поиска может выполняться в двоичном дереве в C++:
void insert(Node*& root, int key, int value) {
if (!root)
root = new Node(key, value);
else if (key == root->key)
root->value = value;
else if (key < root->key)
insert(root->left, key, value);
else // key > root->key
insert(root->right, key, value);
}
В качестве альтернативы, нерекурсивная версия может быть реализована следующим образом. Использование указателя на указатель для отслеживания того, откуда мы пришли, позволяет коду избежать явной проверки и обработки случая, когда требуется вставить узел в корень дерева:
void insert(Node** root, int key, int value) {
Node **walk = root;
while (*walk) {
int curkey = (*walk)->key;
if (curkey == key) {
(*walk)->value = value;
return;
}
if (key > curkey)
walk = &(*walk)->right;
else
walk = &(*walk)->left;
}
*walk = new Node(key, value);
}
Вышеуказанный деструктивный процедурный вариант модифицирует дерево на месте. Он использует только постоянное пространство кучи (и итерационная версия также использует постоянное пространство стека), но предыдущая версия дерева теряется. В качестве альтернативы, как в следующем примере Python, мы можем восстановить всех предков вставленного узла; любая ссылка на исходный корень дерева остается действительной, что делает дерево постоянной структурой данных:
def binary_tree_insert(node, key, value):
if node is None:
return NodeTree(None, key, value, None)
if key == node.key:
return NodeTree(node.left, key, value, node.right)
if key < node.key:
return NodeTree(binary_tree_insert(node.left, key, value), node.key, node.value, node.right)
return NodeTree(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))
Перестраиваемая часть использует O(log n) пространства в среднем случае и O(n) в худшем случае.
В любой версии для этой операции требуется время, пропорциональное высоте дерева в худшем случае, которое составляет O(log n) в среднем случае по всем деревьям, но O(n) время в худшем случае.
Другой способ объяснить вставку состоит в том, что для вставки нового узла в дерево его ключ сначала сравнивается с ключом корня. Если его ключ меньше, чем у корня, он сравнивается с ключом левого потомка корня. Если его ключ больше, его сравнивают с правым потомком корня. Этот процесс продолжается до тех пор, пока новый узел не будет сравнен с листовым узлом, а затем он будет добавлен как правый или левый дочерний узел этого узла, в зависимости от его ключа: если ключ меньше, чем ключ листа, он вставляется как дочерний левого листа, иначе как дочерний правого листа.
Существуют и другие способы вставки узлов в двоичное дерево, но это единственный способ вставки узлов на листьях и в то же время сохранение структуры BST.
Читайте также:
Комментарии
Отправить комментарий