Найти максимальное поддерево в данном BST, чтобы оно не имело дубликатов - PullRequest
Новая
       12

Найти максимальное поддерево в данном BST, чтобы оно не имело дубликатов

1 голос
/ 31 мая 2019

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

Идея такова: (1) Проверить, отображается ли корневое значение в его правом поддереве (вставляя таким образом: left

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

<!-- language: lang-c -->

typedef struct vertex {
    int data;
    struct vertex *left;
    struct vertex *right;
} vertex, *pvertex;

// Utility functions

int Height(pvertex t){
    if (t == NULL)
        return 0;
    if (Height(t->left) > Height(t->right))
        return Height(t->left) + 1;
    else
        return Height(t->right) + 1;
}

int DoesItOccur(pvertex t, int k){
    if(!t)
        return 0;
    if(t->data==k)
        return 1;
    if(t->data<k){
        return DoesItOccur(t->left,k);     
    }
}

// My function
pvertex MaxSeeked(pvertex t){
    if(!t)
        return NULL;
    if(DoesItOccur(t->right,t->data)==0)
        return t;
    else if{
        if(t->left && t->right){
            if(Height(MaxSeeked(t->left))>Height(MaxSeeked(t->right)))
                return t->left;
            else 
                return t->right;
        }
    }
    else if{
    ......
    } 
}

1 Ответ

0 голосов
/ 31 мая 2019

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

Во-первых, обратите внимание, что вам нужно только отслеживать все поддеревья максимальной высоты, обнаруженной до сих пор. Или, может быть, вы можете ограничить это одним, если это все, что вам нужно открыть. Для эффективности вы также должны отслеживать, какова эта максимальная высота на самом деле.

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

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

struct nondupe_subtree {
    struct vertex *root;
    int height;
    struct nondupe_subtree *next;
};

Затем вы можете, скажем, выполнить выборочный обход вашего дерева в первом порядке по ширине, перенеся связанный список struct nondupe_subtree узлов:

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

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

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

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

...