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

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

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; 
}

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


c search algorithm data-structures tree
person rrz0    schedule 13.11.2018    source источник
comment
сделать карту ключа, ‹depth, leafnodepointer›. Когда вы добавляете что-то в дерево, проверьте, есть ли оно на карте. Обновите, если его глубина в три раза больше, чем значение карты. Тем не менее, не думайте, что вам нужны бинарные деревья для этой проблемы, это поможет более подробно объяснить ваши правила удаления бесполезных операций.   -  person juvian    schedule 13.11.2018

Ответы (2)


arrow_upward
1
arrow_downward

Я не понимаю, зачем вам для этого нужен 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);
}
person Bastien    schedule 13.11.2018

arrow_upward
0
arrow_downward

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

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

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

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

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

person Maciej Długoszek    schedule 13.11.2018