Informa se uma árvore é uma sub-árvore de outro
https://stackoverflow.com/questions/1017821
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Há duas árvores binárias T1 e T2 qual personagem armazenamento de dados, duplicatas permitidos.
Como posso descobrir se T2 é uma sub-árvore de T1? .
T1 tem milhões de nós e T2 tem centenas de nós.
Solução
Traverse T1. Se o nó actual é igual ao nó de raiz de T2, atravessar tanto das árvores (T2 e a sub-árvore corrente de T1) ao mesmo tempo. Compare o nó atual. Se eles são sempre iguais, T2 é uma sub-árvore de T1.
Outras dicas
Eu sugiro um algoritmo, que usos pré-processamento:
1) Pré-processar a árvore T1, mantendo a lista de todas as raízes subárvore possíveis (a lista de cache terá um milhões de entradas);
2) Ordenar a lista em cache de raízes pela ordem decrescente de dados, mantido na raiz. Você pode escolher a função de classificação mais elegante, por exemplo, analisar uma árvore personagem em string.
3) Use binário busca para localizar o sub-árvore necessário. Você pode rapidamente rejeitar sub-árvores, com o número de nós, não é igual ao número T2 de nós (ou com a profundidade diferente).
Note que os passos 1) e 2) deve ser feito apenas uma vez, então você pode testar muitos candidatos sub-árvores, usando o mesmo resultado pré-processado.
Se suas árvores não são classificadas de qualquer forma, eu não vejo outra maneira de fazer um brute-force procurar: caminhada através T1 árvore e verificar para ver se você chegar a um nó que coincide com o primeiro nó de T2 árvore. Se não, continue percorrendo T1. Se assim for, verifique se os próximos nós corresponder, até encontrar o final de T2, caso em que você tem um hit:. Seu T2 árvore é realmente uma sub de T1
Se você sabe a profundidade de cada nó de T1 (de folha em nó), você poderia ignorar todos os nós que não são tão profundos como a sub-árvore que você está procurando. Isso poderia ajudar a eliminar um monte de comparações desnecessárias. Dizer que T1 e T2 são bem equilibrado, então T1 árvore terá uma profundidade total de 20 (2**20> 1,000,000) e T2 árvore terá uma profundidade de 7 (2**7> 100). Você só vai ter que andar os 13 primeiros camadas de T1 (8192 nós - ou é que 14 camadas e 16384 nós?) E será capaz de saltar cerca de 90% dos T1 ...
No entanto, se por sub quer dizer que nós folha de T2 também são nós folha de T1, então você poderia fazer uma primeira travessia do T1 e calcular a profundidade de cada nó (distância de folha em nó) e, em seguida, verificar apenas as sub-árvores que têm a mesma profundidade que T2.
Se você é memória / armazenamento ligado (ou seja, não pode pré-manipular e armazenar as árvores em formas alternativas), você provavelmente não será capaz de fazer qualquer coisa melhor do que a busca por força bruta sugerido por algumas outras respostas (travessia P1 procurando raiz correspondente da P2, atravessar tanto para determinar se o nó está no fato da raiz de uma sub-árvore correspondente, continue com percurso original, se ele não é um jogo). Esta pesquisa opera em O (N * m), onde n é o tamanho de P1 e m é o tamanho de P2. Com verificações de profundidade e outras otimizações possíveis, dependendo dos dados da árvore que você tem disponível, este homem ser otimizado um pouco, mas ainda é geralmente O (n * m). Dependendo de suas circunstâncias específicas, esta pode ser a única abordagem razoável.
Se você não tiver memória / armazenamento ligada e não se importa um pouco de complexidade, acredito que este poderia ser melhorado para O (n + m), reduzindo a um problema maior substring comum com a ajuda de um generalizada árvore sufixo. Alguma discussão sobre isso por um problema semelhante pode ser encontrada aqui . Talvez quando eu tiver mais tempo, eu vou voltar e editar com mais detalhes sobre uma implementação.
Se lhe for dada a raiz de ambas as árvores, e dado que os nós são do mesmo tipo, por que então apenas verificar que a raiz do T2 está em T1 não é suficiente?
Estou assumindo que "dada uma árvore T" meios dado um ponteiro para a raiz de T eo tipo de dados do nó.
Cumprimentos.
Eu não tenho certeza, se a minha idéia é correta. No entanto, para o seu persual.
- Realizar uma caminhada postorder na árvore 1 & árvore 2, chamá-lo de P1 e P2.
- Compare P1 e P2. Se eles são diferentes. A árvore não é subárvore. Sair.
- Se eles são iguais, ou P1 contido em P2. Você pode decidir qual é o sub árvore.
Eu acho que precisamos de ir pela força bruta, mas por que você precisa para coincidir com as árvores depois de encontrar a sua raiz de T2 em T1. A sua não é mesmo que quando não é suposto para descobrir se a árvore são idênticos. (Só então precisamos comparar a árvore inteira)
Você é dado árvores T1 e T2, ponteiros, não os valores.
Se Nó T2 (que é um indicador), está presente em T1 árvore.
Em seguida, a árvore T2 é subárvore de T1.
Editar:
Só se seu dito que T2 é realmente uma árvore diferente por objeto sábio, e precisamos descobrir o que se houver um Subtree em T1, que é idêntico ao T2.
Então este não vai funcionar.
E não temos outra opção a não ser ir para as soluções já discutidas aqui.
Vamos dizer que temos T1 como árvore pai e T2 como uma árvore que pode ser uma sub-árvore de T1. Faça o seguinte. Suposição feita é T1 e T2 são árvore binária sem qualquer fator de equilíbrio.
1) Procurar a raiz de T2 em T1. Se não for encontrado T2 não é uma sub-árvore. Procurando o elemento em BT vai levar tempo O (n).
2) Se o elemento é encontrado, fazer pré-ordem de passagem de T1 desde o elemento de nó de raiz de T2 é encontrado. Isso levará o (n). Fazer pré-encomenda travessia do T2 também. Vai levar tempo O (n). O resultado de travessia pré-fim pode ser armazenado numa pilha. Inserção na pilha terá apenas O (1).
3) Se o tamanho de duas pilhas não é igual, T2 não é uma sub-árvore.
4) Pop um elemento de cada pilha e verificar se há igualdade. Se ocorrer incompatibilidade, T2 não é uma sub-árvore.
5) Se todos os elments combinados T2 é uma sub-árvore.
Eu assumo que sua árvore são árvores imutáveis ?? para que você nunca alterar qualquer sub-árvore (você não faz set-car! no Esquema jargão), mas apenas você está construindo novas árvores de folhas ou de árvores existentes.
Então, eu aconselharia a manter em cada nó (ou sub-árvore) um código hash desse nó. Em C linguagem, declarar a árvore-S para ser
struct tree_st {
const unsigned hash;
const bool isleaf;
union {
const char*leafstring; // when isleaf is true
struct { // when isleaf is false
const struct tree_st* left;
const struct tree_st* right;
};
};
};
, em seguida, calcular o hash no momento da construção, e quando se comparam os nós para a igualdade primeiro comparar o seu hash para a igualdade; na maioria das vezes o código hash seria diferente (e você não vai incomodar o conteúdo da comparação).
Aqui está uma possível função construção folha:
struct tree_st* make_leaf (const char*string) {
assert (string != NULL);
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
t->hash = hash_of_string(string);
t->isleaf = true;
t->leafstring = string;
return t;
}
A função de computar um código de hash é
unsigned tree_hash(const struct tree_st *t) {
return (t==NULL)?0:t->hash;
}
A função para a construção de um nó a partir de dois sub-árvores sleft & sright é
struct tree_st*make_node (const struct tree_st* sleft,
const struct tree_st* sright) {
struct tree_st* t = malloc(sizeof(struct tree_st));
if (!t) { perror("malloc"); exit(EXIT_FAILURE); };
/// some hashing composition, e.g.
unsigned h = (tree_hash(sleft)*313) ^ (tree_hash(sright)*617);
t->hash = h;
t->left = sleft;
t->right = sright;
return t;
}
A função de comparação (de duas árvores tx & ty) tiram proveito que se os hashcodes são diferentes os comparands são diferentes
bool equal_tree (const struct tree_st* tx, const struct tree_st* ty) {
if (tx==ty) return true;
if (tree_hash(tx) != tree_hash(ty)) return false;
if (!tx || !ty) return false;
if (tx->isleaf != ty->isleaf) return false;
if (tx->isleaf) return !strcmp(tx->leafstring, ty->leafstring);
else return equal_tree(tx->left, ty->left)
&& equal_tree(tx->right, ty->right);
}
Na maioria das vezes o teste tree_hash(tx) != tree_hash(ty) teria sucesso e você não terá que recurse.
Leia sobre de hash consing .
Depois de ter tal função equal_tree baseado em hash eficiente, você pode usar as técnicas mencionadas em outras respostas (ou em manuais).
Uma das maneira simples é escrever método is_equal () para árvore e fazer o seguinte,
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
return is_equal(other) || (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
Note que is_equal () pode ser otimizado usando hashcode para a árvore. Isso pode ser feito de forma simples, tomando altura da árvore ou o número de crianças ou intervalo de valores como hashcode.
bool is_equal(TNode*other) {
if(x != other->x) return false;
if(height != other->height) return false;
if(nchildren != other->nchildren) return false;
if(hashcode() != other->hashcode()) return false;
// do other checking for example check if the children are equal ..
}
Quando a árvore é semelhante a uma lista ligada, vai demorar tempo O (n). Nós também pode usar alguns heurística ao escolher as crianças para comparar.
bool contains_subtree(TNode*other) {
// optimization
if(nchildren < other->nchildren) return false;
if(height < other->height) return false;
// go for real check
if(is_equal(other)) return true;
if(left == NULL || right == NULL) {
return (left != NULL && left->contains_subtree(other)) || (right != NULL && right->contains_subtree(other));
}
if(left->nchildren < right->nchildren) { // find in smaller child tree first
return (left->contains_subtree(other)) || right->contains_subtree(other);
} else {
return (right->contains_subtree(other)) || left->contains_subtree(other);
}
}
Outra maneira é serializar tanto árvore como cordas e descobrir se o segundo string (serializado de T2) é sub-string do primeiro string (serializado de T1).
O código a seguir serializa em pré-encomenda.
void serialize(ostream&strm) {
strm << x << '(';
if(left)
left->serialize(strm);
strm << ',';
if(right)
right->serialize(strm);
strm << ')';
}
E podemos usar algum algoritmo otimizado, por exemplo, Knuth-Morris-Pratt algoritmo de encontrar (possivelmente em o (n)) a existência do sub-string e, eventualmente, encontrar se uma árvore é uma sub-árvore da outra.
Mais uma vez a corda pode ser comprimida de forma eficiente com Burrows-Wheeler_transform. E é possível bzgrep para procurar sub-string nos dados comprimidos.
Outra maneira é para classificar as sub-árvores na árvore pela altura e número de filhos.
bool compare(TNode*other) {
if(height != other->height)
return height < other->height;
return nchildren < other->nchildren;
}
Note-se que haverá O (n ^ 2) sub-árvores. Para reduzir o número de nós pode usar alguma variedade com base na altura. Por exemplo, só podemos estar interessado sobre as sub-árvores de altura 1000 a 1500.
Quando os dados ordenado é gerado é possível fazer busca binária nele e descobrir se ele é subconjunto em O (lg n) tempo (considerando que não há duplicado em dados classificados).
