Как удалить узел в бинарном дереве поиска с помощью рекурсии

Теперь я пытаюсь сформулировать функцию удаления для удаления узла внутри двоичного дерева поиска, учитывая, что узел содержит искомое содержимое. Я написал скелет для функции, которая ищет контент и возвращает true или false в зависимости от того, нашла он его или нет. Проблема в том, что я не могу понять, как реализовать фактическую часть удаления для моей функции. Если корневой узел содержит искомое значение, я не знаю, как назначить одному из дочерних элементов старого корня корневую позицию после удаления. Мне также трудно понять, как обнулить указатели дочерних элементов после удаления узла и повторного связывания частей дерева, которые потенциально могут быть разорваны, если я просто отключу узел, содержащий искомое значение.

Ниже приведена функция, которая у меня есть до сих пор:

bool BSTree::Remove(int content, BSTNode*& bst_node) const {
// makes sure the tree is not empty (function returns false if it is)  
if (bst_node != NULL) {
  // checks to see if nodes contents matches content param 
  if (bst_node->GetContents() == content) {
      // checks to see if the node has children
      if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) {

      } else if (bst_node->GetLeftChild() == NULL) {

      } else if (bst_node->GetRightChild() == NULL) {

      } else {

      }
      return true;
    // checks to see if the content of node is less/greater than content param
    } else if (content < bst_node->GetContents()) {
        if (bst_node->GetLeftChild() != NULL)
          return Remove(content, bst_node->GetLeftChild());
    } else if (content > bst_node->GetContents()) {
        if (bst_node->GetRightChild() != NULL)
          return Remove(content, bst_node->GetRightChild());
    }
  }
  return false;
}

Что я добавил:

bool BSTree::Remove(int content, BSTNode*& bst_node) {
  BSTNode* parent = bst_node;
  if (bst_node == NULL) {
    return false;
  } else {
    if (content == bst_node->GetContents()) {
      if (bst_node->GetLeftChild() == NULL && bst_node->GetRightChild() == NULL) {
        if (bst_node == root_) {
          Clear();
        } else {
          // code for deleting leaf
          bst_node->SetContents(0);
          bst_node = NULL;
          delete bst_node;
          size_--;
        }
      } else if (bst_node->GetLeftChild() == NULL) {
        // code for deleting node with only right child
        if (bst_node == root_) {
          parent = bst_node->GetRightChild();
          bst_node->SetContents(0);
          bst_node = NULL;
          delete bst_node;
          root_ = parent;
        } else {

        }
        size_--;
      } else if (bst_node->GetRightChild() == NULL) {
        // code for deleting node with only left child
        if (bst_node == root_) {
          parent = bst_node->GetLeftChild();
          bst_node->SetContents(0);
          bst_node = NULL;
          delete bst_node;
          root_ = parent;
        } else {

        }
        size_--;
      } else {
        // code for deleting node with two children
        size_--;
      }
    } else if (content < bst_node->GetContents()) {
      if (bst_node->GetLeftChild() == NULL) {
        return false;
      } else {
        return Remove(content, bst_node->GetLeftChild());
      }
    } else if (content > bst_node->GetContents()) {
      if (bst_node->GetRightChild() == NULL) {
        return false;
      } else {
        return Remove(content, bst_node->GetRightChild());
      }
    }
  }
  return true;
}

Вспомогательная функция для функции удаления:

int BSTree::FindMin(BSTNode* bst_node) const {
  if (bst_node != NULL) {
    if (bst_node->GetLeftChild() != NULL)
      return FindMin(bst_node->GetLeftChild());
    return bst_node->GetContents();
  }
  return 0;
}

c++ recursion recursive-datastructures binary-search-tree
person Carlos Escobedo    schedule 19.05.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Один из возможных способов удаления узла — заменить его его прямым преемником при удалении листа, чтобы не нарушать инвариант дерева.

Преемник узла является самым левым дочерним элементом его правого поддерева, поэтому, как только вы доберетесь до узла, который хотите удалить, найдите преемника и поменяйте местами узлы. Как только это будет сделано, найдите лист и удалите его. Поскольку вы взяли самого левого дочернего элемента, вы уверены, что у листа будет левый дочерний элемент NULL. У него есть правильный дочерний элемент, замените лист правильным дочерним элементом и все.

Обычная реализация, используемая для двоичного дерева поиска, состоит в том, чтобы заставить Remove возвращать узел, поэтому вы можете изменить форму дерева, просто возвращая узлы, и вам не нужно беспокоиться о случаях внуков.

person T. Claverie    schedule 19.05.2016
comment
Благодарю за ваш ответ! Я понимаю, как это должно быть удалено. моя проблема заключается в том, чтобы сохранить родительский узел узла, который я хочу удалить, чтобы повторно связать поддерево, оставшееся в процессе удаления узла с 1 или 2 дочерними элементами. - person Carlos Escobedo; 21.05.2016