arvores binaria

766 palavras 4 páginas
Árvore Binária
Definição
Em ciência da computação, a árvore de busca binária ou árvore de pesquisa binária é uma árvore binária onde todos os nós são valores, todo nó a esquerda contêm uma sub-árvore com os valores menores ao nó raiz da sub-árvore e todos os nós da sub-árvore a direita contêm somente valores maiores ao nó raiz. (Esta é a forma padrão, podendo ser invertida as sub-árvores dependendo da aplicação). Os valores são relevantes na árvore de busca binária. O objetivo desta árvore é estruturar os dados de forma flexível permitindo pesquisa binária

Termos de árvore:
Nó: são todos os ítens guardados na árvore.
Raiz é o item do topo da árvore (neste caso o número 50).
Filho são os itens logo abaixo da raiz, 30 e 90 e assim sequencialmente, por exemplo, o 20 é filho do 30.
Parente são os nós do mesmo nível, por exemplo, o 90 é parente do 100.
Folha é um nó que não tem filho, é o último item da árvore, por exemplo, 20, 40 e 100.
Busca
Para a busca em uma árvore binária por um valor específico começamos examinando a raiz. Se o valor for igual a raiz, o valor existe na árvore. Se o valor for menor do que a raiz, então deve buscar na sub-árvore da esquerda, e assim recursivamente em todos os nós da sub-árvore.
Similarmente, se o valor for maior do que a raiz, então deve buscar na sub-árvore da direita. Até alcançar o nó folha da árvore, encontrando ou não o valor requerido.
Inserção
A inserção começa com uma busca; procurando pelo valor, mas se não for encontrado, procuraremos as sub-árvores da esquerda ou direita como na busca. Eventualmente, alcançaremos a folha, e então inserimos o valor nesta posição. Ou seja nós examinamos a raiz e introduzimos um nó novo na sub-árvore da esquerda se o valor novo é menor do que a raiz, ou na sub-árvore da direita se o valor novo for maior do que a raiz.
Uma outra maneira de explicar a inserção é que a fim de introduzir um nó novo na árvore, seu valor é primeiro comparado com o valor da raiz. Se seu

Relacionados

  • Arvores binarias
    983 palavras | 4 páginas
  • Árvores Binárias
    1499 palavras | 6 páginas
  • Arvores binarias
    364 palavras | 2 páginas
  • Arvores binárias
    1191 palavras | 5 páginas
  • arvores binarias
    2352 palavras | 10 páginas
  • Árvores Binárias
    775 palavras | 4 páginas
  • arvores binarias
    1170 palavras | 5 páginas
  • Árvores Binárias
    3722 palavras | 15 páginas
  • Arvores binárias
    4463 palavras | 18 páginas
  • árvores binárias
    415 palavras | 2 páginas