Changes

Uma árvore é chamada de árvore binária se todos os vértices na árvore tiverem no máximo dois filhos. Nesse capítulo, iremos utilizar árvores binárias ordenadas. A ordenação dos vértices é simplesmente a marcação dos filhos de um vértice como o filho a à esquerda ou o filho a à direita, onde o filho a à esquerda é considerado o filho que deve ser visitado primeiro, e o da direita, o que deve ser visitado em segundo.

Um benefício crucial em árvores binárias ordenadas é de que o tempo de buscar busca exigido to para encontrar um específico elemento da árvore é logarítmico no ao número de vértices da árvore. A maior desvantegem desvantagem é de que a inserção de um vértice é muito mais taxativa. Discutiremos estes aspectos em mais detalhe enquanto percorremos a própria impementação implementação de um algoritmo de inserção binária.

Requerimos marcações no vérticeOs vértices devem se marcados. No Maple podemos utilizar o nome do vértice como marcação já que ele pode ser tanto inteiro como string.

Um vértice tipico na árvore tipicamente tem dois descendentes (filhas). Devemos ser capazes de especificar quais qual desses dois vértices é o descendente da esquerda e qual é o da direita. Podemos indicar isso utilizando o peso do vértice. No Maple, cada vértice tem um peso padrão de 0, como demonstrado no simples exemplo:

Ela também facilita a mudança do critério de comparação em outro ponto posteriorcaso seja necessário mais tarde, refazendo sem ter que refazer totalmente o código do algoritmo inteiro.

Também precisaremos ser capazes de achar a raiz da árvore. O seguinte procedure calcula tal raiz e força a árvore a lembrar sua raiz, para que a sua computação não precise ser repetida.

O procedure para construir uma árvore binária ordenadapor ordenada por inserção é acontece como o exemplo seguinte. Para facilitar, utilizamos o nome do vértice como seu valor quando fazemos comparaçãoestivermos comparando.

3. Caso contrário, transforme a raiz da árvore na variável para o vértice atual cur_vertex, e compare v com cur_vertex. se Se v =cur_vertex, está feitoacabado.

4. se v <cur_vertex então procure o filho a à esquerda, caso contrário, procure o filho a à direita. Isso é feito mudando cur_vertex para ser o filho a à esquerda ou a à direita e comparando o novo cur_vertex com v.

As ordenações relativas dos descendentes e , x e cur_vertex determinam se x pode ser inserido como folha.

não há filhos, então adicione apenas um novo filhovértice.

Para todos os casos restantes adicione em x como um novo vértice

O procedure addvertex é usado aqui em de uma maneira que atualiza os pesos de cada vértice na medida que ele é criadoeles são criados. Isso serve para indicar se é o vértice é um descendente a à esquerda ou a à direita. Enquanto não usamos esses pesos, eles poderiam ser utilizados como uma medida alternativa para ordenação de descendentes de qualquer vértice particular.

Ao invés disso, para a ordenação, nós usamos os nomes dos vértices para indicar a ordenação relativa dos vértices. O fato de que qaiquer quaisquer dois vértices (e não apenas descendentes do mesmo vértice) podem ser comparados nos permite combinar o novo vértice, os descendentes, e o vértice atual tudo em uma lista ordenada a qual que é então inspecionada para determinar qual dos vários casos especiais é relevante durante a inserção de um novo vértice. Qualquer que seja o método de comparação de vértices que for utilizado, é importante que o procedure de comparação seja passado na rotina de ordenação como um argumento extra.

Árvores binárias existem para serem procuradasusadas como método de busca. O seguinte procedure BiSearch a seguir faz isso. Declarações do tipo Print foram adicionadas para ilustrar o caminho que o algoritmo usa enquanto faz a busca na árvore.