Árvore (a,b)
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Novembro de 2020) |
Em ciência da computação, um árvore (a,b) é uma generalização da árvore B e um tipo de árvore de busca balanceada.
-baum.svg)
Uma árvore (a,b) tem todas as suas folhas na mesma profundidade, e todos os nós internos, exceto a raiz, possuem uma quantidade entre a e b de filhos, onde a e b são números inteiros, tais que 2 ≤ a ≤ (b+1)/2. A raiz tem, se não for uma folha, entre 2 e b filhos.
Definição
editarDefina a, b como números inteiros positivos tal que 2 ≤ a ≤ (b+1)/2. Em seguida, uma árvore T é uma árvore (a,b) quando:
- Cada nó interior, exceto a raiz tem pelo menos a e no máximo b filhos.
- A raiz tem, no máximo, b filhos.
- Todos os caminhos da raiz até as folhas são do mesmo comprimento.
Ver também
editarReferências
editar- Black, Paul E. "(a,b)-tree." Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology.