Исправление указателей в функции удаления двоичного дерева (узел с 2 дочерними элементами) - PullRequest
Новая
       5

Исправление указателей в функции удаления двоичного дерева (узел с 2 дочерними элементами)

2 голосов
/ 18 февраля 2010

У меня возникли небольшие проблемы с размышлениями, как, черт возьми, я исправляю соответствующие указатели при попытке удалить узел из двоичного дерева, где у этого узла есть 2 дочерних элемента.

Я понимаю основную концепцию, и у меня просто проблемы с исправлением указателей ...

Итак, в основном, моя функция удаления в основном выполнена, и каждый кейс уже работает (что касается моего обширного тестирования, все работало нормально), я пропускаю только узел кейс с 2 дочерними элементами. Допустим, мы находимся внутри else if, который имеет дело с этим случаем:

У меня там будет 2 указателя, currPtr, который содержит удаляемый узел, prevPtr, который содержит родительский узел. У меня также есть переменная с именем fromLeft, которая определяет, исходит ли родительский элемент currPtr от левого или правого указателя на prevPtr. Затем у меня есть вызов другой функции с именем extractMin(Tree *t), которая извлекает самое низкое значение в дереве. Если я вызову эту функцию с currPtr->right в качестве аргумента, преемник currPtr будет извлечен из дерева (функция удалит его из дерева, исправит указатели и вернет указатель узла). Указатель-преемник будет сохранен на tempPtr.

Вот структура моего дерева: 

typedef int TreeElement;

typedef struct sTree {
   TreeElement item;

   struct sTree *left;
   struct sTree *right;
} Tree;

И код для функции извлечения: 

Tree *extractMin(Tree *tree) {
    Tree *prevPtr = NULL;
    Tree *currPtr = tree;

    while(currPtr->left) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
    }

    if(prevPtr) prevPtr->left = currPtr->right;

    // inorder successor
    return currPtr;
}

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

Итак, как мне исправить необходимые указатели на else if для удаления узла? Также помните, что указатели left и right на узлах дерева всегда будут указывать куда-то или будут NULL.

Кстати, я хочу сделать эту итерацию.

Ответы [ 3 ]

3 голосов
/ 18 февраля 2010

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

Предположим, дерево ниже упорядочено. Порядок узлов: 

H < D < I < B < J < E < K < A < F < M < C < N < G < O

Вы хотите удалить узел (A), у которого есть два дочерних элемента. Вы вытаскиваете либо его предшественника по порядку (K), либо наследника (F) дочернего узла вместо оригинала. Давайте выберем преемника. Вот как вы находите это: вы пересекаете левых детей C, пока не найдете того, у которого нет левого ребенка; это прямой наследник А. 

       A
   B       C
 D   E   F   G
H I J K   M N O

Итак, F подтянут, а левое поддерево A не затронуто. Тем не менее, теперь М тоже нужно подтянуть, чтобы стать левым потомком С (это сделано в вашем extractMin()).

После всех перестановок вы получите 

       F
   B       C
 D   E   M   G
H I J K     N O

В коде это моё решение. Я добавил проверку NULL в extractMin(), чтобы упростить код вызывающего абонента, поэтому мне не нужно else if.

Обновлен extractMin() для случая, когда у tree нет детей. 

Tree *extractMin(Tree *parent, Tree *tree) {
    if (!tree) return NULL;

    Tree *prevPtr = NULL;
    Tree *currPtr = tree;

    while(currPtr->left) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
    }

    if (prevPtr) {
        prevPtr->left = currPtr->right;
    } else if (parent) {
        parent->right = currPtr->right;
    }

    // inorder successor
    return currPtr;
}

// prevPtr is the parent, currPtr is the node to be deleted
Tree *successor = extractMin(currPtr, currPtr->right);
successor->left = currPtr->left;
successor->right = currPtr->right;
if (fromLeft) {
    prevPtr->left = successor;
} else {
    prevPtr->right = successor;
}
// Now currPtr can be destroyed

Обратите внимание, что этот код не тестировался, поэтому я ничего не гарантирую: -)

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

1 голос
/ 19 февраля 2010

Ответ из учебника - заменить рассматриваемый узел на крайний левый правый потомок. 

                6
         3             8
     2      4      7      9
   1          5             10

Если мы хотим удалить 3, мы можем заменить его на 4, а затем потянуть 5 в отверстие, куда ушло 4. Мы всегда можем сделать это, и это сохранит порядок обхода.

OK. глядя на ваш код, это то, что вы хотите: 

//in your function
    else if (/*has 2 nodes*/) {
        currPtr->item = extractMin(currPtr->right, &(currPtr->right))->item;
    }

Tree *extractMin(Tree *tree, Tree ** back) {
    Tree *currPtr = tree;

    while(currPtr->left) {
        back    = &(currPtr->left);
        currPtr = currPtr->left;
    }

    *back = currPtr->right;

    // inorder successor
    return currPtr;
}

Аргумент ** позволяет нам обрабатывать случай, когда мы используем удаленные узлы непосредственно справа child: 

     3   <--deleting this node
   /   \   <--back points to this edge.
  2     4   <--extractMin is called on this node and returns this node,
         \
          5   <-- (*back) now points to this node.

Подумайте о новом ExtractMin в 2 случаях.

  1. В первом случае мы проходим цикл хотя бы один раз. Если бы мы оставили в коде prevPtr, мы бы увидели, что после цикла back == &(prevPtr->left); (например, изменение * back приведет к изменению prevPtr-> left). Так что это так же, как ваш код выше.
  2. Во втором случае мы не проходим цикл. В этом случае back указывает на ссылку, которую мы не могли получить каким-либо другим способом (если мы не изменили extractMin, чтобы начать на один уровень выше).

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

0 голосов
/ 19 февраля 2010

Если вы серьезно относитесь к этому, взгляните на деревья AVL:

http://en.wikipedia.org/wiki/AVL_tree

Их может быть сложно реализовать, но они останутся сбалансированными из-за вращений, которые вы выполняете при вставках и удалениях.

...