Вопрос 9: Дерево двоичного поиска: алгоритмы вставки и удаления

Дерево двоичного поиска (ДДП) — это способ хранения множества в форме расширяемого упорядоченного списка с сохранением упорядоченности при вставке новых элементов без перемещения уже имеющихся.

ДДП — это дерево с нагруженными узлами, вес в любом узле которого больше любого веса в левом его поддереве и не больше любого веса в правом поддереве. Количество шагов алгоритма поиска элемента множества в таком дереве не превышает его высоты, т. е. имеет сложность $O(\log n)$. Такую же сложность имеют операции вставки нового элемента в дерево и удаления элемента.

ДДП можно получить из упорядоченной последовательности ключей, если двоичное дерево соответствующей мощности разметить внутренним (симметричным) способом, а затем заменить номера узлов соответствующими элементами последовательности.

Алгоритм вставки (без информации о родителе)

Node* insert(Node* root, int z)        // корень поддерева, вставляемый ключ
{
   if (root == nullptr)
      return new Node(z);              // подвесим Node с key = z

   if (z < root->key)
      root->left = insert(root->left, z);
   else
      root->right = insert(root->right, z);

   return root;
}

Алгоритм удаления (без информации о родителе)

Node* minimum(Node* root)              // поиск узла с минимальным ключом в поддереве с корнем root
{
    return (root->left ? minimum(root->left) : root);
}

Node* deleteNode(Node* root, int z)    // корень поддерева, удаляемый ключ
{
  if (root == nullptr)
    return root;

  if (z < root->key)
    root->left = deleteNode(root->left, z);

  else if (z > root->key)
    root->right = deleteNode(root->right, z);

  else {
    if (root->left == nullptr) {
      Node* temp = root->right;
      delete root;

      return temp;
    }

    else if (root->right == nullptr) {
      Node* temp = root->left;
      delete root;

      return temp;
    }

    Node* temp = minimum(root->right);
    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }

  return root;
}