Please enable JavaScript.
Coggle requires JavaScript to display documents.
BINARY SEARCH TREE - Coggle Diagram
BINARY SEARCH TREE
-
Uma árvore (mais precisamente, uma árvore livre) é um grafo acíclico conectado. Um grafo que não tem ciclos, mas não é necessariamente conectado é chamado de floresta: cada um de seus componentes conectados é uma árvore.
-
Nas árvores enraizadas, para cada dois vértices em uma árvore, sempre existe exatamente um caminho simples de um desses
vértices para o outro.
Esta propriedade permite selecionar um vértice arbitrário
em uma árvore livre e considerá-la como a raiz da chamada árvore enraizada.
Uma árvore enraizada é geralmente representada colocando sua raiz no topo (nível 0 da árvore), os vértices adjacentes à raiz abaixo dela (nível 1), os vértices duas arestas além da raiz
ainda abaixo (nível 2), e assim por diante.
Para qualquer vértice v em uma árvore T , todos os vértices no caminho simples da raiz
a esse vértice são chamados de ancestrais de v. O próprio vértice é geralmente considerado seu
próprio ancestral.
o conjunto de ancestrais que exclui o próprio vértice é referido como o conjunto de ancestrais próprios.
Se (u, v) é a última aresta do caminho simples do
raiz ao vértice v (e u é diferente de v), u é dito ser o pai de v e v é chamado de filho de u;
-
-
Uma árvore binária pode ser definida como uma árvore ordenada na qual cada vértice tem não mais do que dois filhos e cada filho é designado como filho esquerdo ou filho filho direito de seu pai.
-
Como a própria definição divide uma árvore binária em duas estruturas menores de mesmo tipo, a subárvore esquerda e a subárvore direita, muitos problemas sobre árvores binárias podem ser resolvidos aplicando a técnica de dividir e conquistar.
-
Esses percursos são ilustrados na Figura 5.6. Seus pseudocódigos são bastante
simples, repetindo as descrições dadas acima. (Estas travessias também sãoum recurso padrão dos livros didáticos de estruturas de dados.)
Quanto à sua análise de eficiência,
é idêntico à análise acima do algoritmo Altura porque uma chamada recursiva é feito para cada nó de uma árvore binária estendida.
Finalmente, devemos notar que, obviamente, nem todas as questões sobre árvores binárias requerem travessias de ambas as subárvores esquerda e direita.
Por exemplo, a pesquisa e inserção
as operações para uma árvore de busca binária requerem o processamento de apenas uma das duas subárvores.
Assim, nós os consideramos na Seção 4.5 não como aplicações de dividir e conquistar, mas sim como exemplos da técnica de redução de tamanho variável.