Операции с двоичным деревом поиска: вставка

Вставка начинается так же, как начинается поиск; если ключ не равен ключу корня, мы ищем левое или правое поддерево, как и раньше. В конце концов, мы достигнем внешнего узла и добавим новую пару ключ-значение (здесь закодированную как запись '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.

---

Читайте также:

• Структуры данных: двоичное дерево поиска
• Структуры данных: B-дерево (B-tree)
• Операции с двоичным деревом поиска: поиск