Uma Árvore de Busca Binária (BST) é uma árvore em que todos os nós seguem abaixo mencionado propriedades
-
O valor da chave de esquerda sub-árvore é inferior ao valor do respectivo elemento principal (raiz) do nó de chave.
-
o valor da chave da sub-árvore direita é maior ou igual ao valor da chave do nó-mãe (raiz).,
Assim, BST divide todas as suas sub-árvores em dois segmentos; o esquerdo sub-árvore e o direito de sub-árvore pode ser definido como −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
Representação
BST é uma coleção de nós organizados de uma forma que eles mantêm BST propriedades. Cada nó tem uma chave e um valor associado. Ao pesquisar, a chave desejada é comparada com as chaves em BST e se for encontrada, o valor associado é obtido.,
A seguir está uma representação pictórica de BST −
observamos que a chave do nó raiz (27) tem todas as chaves menos valorizadas na sub-árvore esquerda e as chaves mais valorizadas na sub-árvore direita.
Operações Básicas
a seguir são as operações básicas de uma árvore −
-
pesquisa-procura um elemento numa árvore.
-
inserts an element in a tree.
-
pré-ordem atravessa uma árvore de uma forma pré-ordem.
-
em ordem atravessa uma árvore de uma forma ordenada.,
-
post-order Traversal-Traverses a tree in a post-order manner.
nó
Define um nó com alguns dados, referências aos seus nós-filhos esquerda e direita.
struct node { int data; struct node *leftChild; struct node *rightChild;};
Operação de pesquisa
sempre que um elemento deve ser pesquisado, comece a procurar a partir do nó raiz. Então se os dados são menores que o valor chave, procure pelo elemento na subárvore esquerda. Caso contrário, procure o elemento na subárvore direita. Siga o mesmo algoritmo para cada nó.,
algoritmo
inserir operação
sempre que um elemento estiver para ser inserido, localize primeiro a sua localização adequada. Inicie a pesquisa a partir do nó raiz, então se os dados são menores que o valor chave, procure a localização vazia na sub-árvore esquerda e insira os dados. Caso contrário, procure a localização vazia na sub-árvore direita e insira os dados.