Как найти самый глубокий УНИКАЛЬНЫЙ узел двоичного дерева в C

Question

Я читаю команды из текстового файла. Пример ввода:

Create Key 2
Create Key 1
Create Key 3
Update Key 1
Delete Key 2 

Я хочу сократить количество операций, выполняемых моей программой. Например, создавать Key2 бесполезно, только удалять его после.

Чтобы минимизировать количество операций, я решил сохранить их в бинарном дереве поиска. В книге Кормена, Лизерсона, Ривеста и Стейна «Введение в алгоритмы», третье издание, двоичное дерево поиска (BST) явно определено как разрешающее дубликаты. Буква после ключа обозначает «Создать», «Обновить» или «Удалить». Простой пример будет следующим:

       K2(C)
      /    \
     /      \
  K1(C)     K3(C)      <-- The deepest Key3 appears here.
     \       /   
    K1(U)   K2(D)      <-- The deepest Key1 and Key2 appear here.

Как уже отмечалось, я хотел бы иметь возможность извлекать все уникальные ключи в их самой глубокой позиции, чтобы минимизировать количество операций. Я не мог найти ссылку на это в CLRS, возможно, я искал не ту вещь ...

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

struct node* search(struct node* root, int key) 
{ 
    // Base Cases: root is null or key is present at root 
    if (root == NULL || root->key == key) 
       return root; 

    // Key is greater than root's key 
    if (root->key < key) 
       return search(root->right, key); 

    // Key is smaller than root's key 
    return search(root->left, key); 

Как обрабатывать дубликаты в бинарном дереве поиска? описывает, как обрабатывать вставку дубликатов, а не как извлекать дубликаты, которые появляются последними.

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

struct node * maxValueNode(struct node* node) 
{ 
    struct node* current = node; 

    /* loop down to find the rightmost leaf */
    while (current->right != NULL) 
        current = current->right; 

    return current; 
} 

Я что-то здесь упускаю? Как я могу найти самый глубокий УНИКАЛЬНЫЙ узел двоичного дерева?

Answer 1

Я не понимаю, зачем вам нужен BST для этого, но в любом случае вы можете выполнить поиск, который не останавливается при первом появлении и отслеживает самый глубокий узел, найденный с помощью указателей.Это должно сработать:

void deepest_search(struct node * root, int key, int currentDepth, int * maxDepth, struct node * deepestNode)
{
  // Do nothing if root is null
  if (root != NULL)
  {
        // Update deepest node if needed
        if(root->key == key && currentDepth > *maxDepth)
        {
            *maxDepth = currentDepth;
            *deepestNode = *root;
        }

        // Might need to search both sides because of duplicates
        // Can make this an if/else if duplicates are always in left/right subtree
        if(root->key <= key)
            deepest_search(root->right, key, currentDepth + 1, maxDepth, deepestNode);
        if(root->key >= key)
            deepest_search(root->left, key, currentDepth + 1, maxDepth, deepestNode);
    }
}

Я проверил его на вашем (маленьком) примере, и, похоже, он работает нормально:

struct node
{
    int key;
    int val;
    struct node *left, *right;
};

void main(void)
{
    int key = 1;
    int currentDepth = 1;

    struct node n5 = {2, 5, NULL, NULL};
    struct node n4 = {1, 4, NULL, NULL};
    struct node n3 = {3, 3, &n5, NULL};
    struct node n2 = {1, 2, NULL, &n4};
    struct node n1 = {2, 1, &n2, &n3};

    struct node * deepestNode = (struct node *) malloc(sizeof(struct node));
    int maxDepth = 0;

    deepest_search(&n1, key, currentDepth, &maxDepth, deepestNode);
    printf("%d\n", maxDepth);
    printf("%d\n", deepestNode->val);
}

Answer 2

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

1. Перемещение дубликатов в правое или левое поддерево (некрасивое решение)

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

2. Подсчет значений (лучше)

Согласно этому методу, каждый узел содержит счетчик, который сообщает, сколько раз было получено данное значение. Если вы хотите удалить один экземпляр этого значения, то, если counter> 1, вы просто уменьшаете счетчик. В противном случае, если counter == 1, вы удаляете узел, как если бы вы делали это в обычном BST.