Prelúdio
Este artigo é dedicado a árvores binárias de busca. Recentemente fiz um artigo sobre Lá, eu não prestei muita atenção nas árvores binárias, pois os métodos de busca, inserção e deleção não eram relevantes. Agora decidi escrever um artigo especificamente sobre árvores. Vamos começar.
Uma árvore é uma estrutura de dados composta por nós conectados por arestas. Pode-se dizer que uma árvore é um caso especial de grafo. Aqui está um exemplo de árvore:
Esta não é uma árvore binária de busca! Tudo abaixo!
Terminologia
Raiz
A raiz da árvore é o nó mais alto. No exemplo, é o nó A. Em uma árvore, do nó raiz para qualquer outro nó pode haver apenas um caminho! Na verdade, qualquer nó pode ser visto como a raiz do respectivo subárvore.
Pais/filhos
Todos os nós, exceto a raiz, têm exatamente uma aresta que vai para cima em direção a outro nó. O nó que está acima do atual é chamado de pai deste nó. O nó que está abaixo do atual e conectado a ele é chamado de filho deste nó. Vamos usar um exemplo. Pegamos o nó B, então seu pai será o nó A, e seus filhos serão os nós D, E e F.
Folha
Um nó que não tem filhos será chamado de folha da árvore. No exemplo, as folhas serão os nós D, E, F, G, I, J, K.
Esta é a terminologia básica. Outros conceitos serão abordados a seguir. Então, uma árvore binária é uma árvore em que cada nó terá no máximo dois filhos. Como você deve ter adivinhado, a árvore do exemplo não é binária, pois os nós B e H têm mais de dois filhos. Aqui está um exemplo de árvore binária:
Nos nós da árvore pode haver qualquer informação. Uma árvore binária de busca é uma árvore binária, para a qual as seguintes propriedades se aplicam:
- Ambas as subárvores — a esquerda e a direita — são árvores binárias de busca.
- Todos os nós da subárvore esquerda de um nó X têm valores de chave de dados menores do que o valor da chave de dados do próprio nó X.
- Todos os nós da subárvore direita de um nó X têm valores de chave de dados maiores ou iguais ao valor da chave de dados do próprio nó X.
Chave é uma característica de um nó (por exemplo, um número). A chave é necessária para que seja possível encontrar o elemento da árvore que corresponde a essa chave. Exemplo de árvore binária de busca:
Representação da árvore
À medida que avançamos, apresentarei alguns (possivelmente incompletos) trechos de código para melhorar sua compreensão. O código completo estará no final do artigo.
Uma árvore é composta por nós. A estrutura de um nó:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
// ... outros métodos do nó
}
Cada nó tem dois filhos (é bem possível que os filhos leftChild e/ou rightChild contenham o valor null). Você deve ter entendido que, neste caso, data é os dados armazenados no nó; key é a chave do nó.
Compreendido o nó, agora vamos falar sobre problemas práticos relacionados a árvores. Daqui em diante, quando eu mencionar ‘árvore’, estarei me referindo a uma árvore binária de busca. A estrutura de uma árvore binária:
public class BinaryTree<T> {
private Node<T> root;
// métodos da árvore
}
Como campo da classe, precisamos apenas da raiz da árvore, pois, a partir da raiz, utilizando os métodos getLeftChild() e getRightChild(), é possível acessar qualquer nó da árvore.
Algoritmos na árvore
A busca
Suponha que você tenha uma árvore construída. Como encontrar o elemento com a chave key? É necessário percorrer a árvore a partir da raiz, comparando o valor key com a chave de cada nó: se key for menor que a chave do nó atual, vá para o filho esquerdo; se for maior, vá para o direito; se as chaves forem iguais, o nó buscado foi encontrado! O código correspondente:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
Se current se torna igual a null, significa que a busca alcançou o final da árvore (em termos conceituais, você está em um lugar inexistente da árvore — o filho de uma folha).
Vamos considerar a eficiência do algoritmo de busca em uma árvore balanceada (uma árvore onde os nós estão distribuídos mais ou menos uniformemente). Nesse caso, a eficiência da busca será O(log(n)), sendo o logaritmo de base 2. Veja: se em uma árvore balanceada há n elementos, isso significa que haverá log(n) de base 2 níveis na árvore. E, em cada iteração de busca, você desce um nível.
Inserção
Se você entendeu a essência da busca, entender a inserção não será difícil. Você só precisa descer até a folha da árvore (de acordo com as regras de descida descritas na busca) e se tornar seu descendente — à esquerda ou à direita, dependendo da chave. Implementação:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
Neste caso, é necessário armazenar, além do nó atual, informações sobre o pai do nó atual. Quando current se tornar igual a null, a variável parent conterá a folha que precisamos.
A eficiência da inserção será, evidentemente, a mesma que a da busca — O(log(n)).
Remoção
A remoção é a operação mais complexa que teremos que realizar com a árvore. É evidente que, primeiro, precisamos encontrar o elemento que vamos remover. Mas e depois? Se simplesmente atribuímos o valor null à sua referência, perderemos a informação sobre a subárvore cujas raízes são esse nó. Os métodos de remoção da árvore são divididos em três casos.
Primeiro caso. O nó removido não tem filhos.
Se o nó removido não tem filhos, isso significa que ele é uma folha. Portanto, podemos simplesmente atribuir o valor null aos campos leftChild ou rightChild do seu pai.
Segundo caso. O nó removido tem um filho.
Este caso também não é muito complicado. Vamos voltar ao nosso exemplo. Suponha que precisemos remover o elemento com a chave 14. Concordem que, como ele é o filho direito do nó com a chave 10, qualquer um de seus filhos (neste caso, o direito) terá uma chave maior que 10, portanto podemos facilmente 'cortar' isso da árvore e conectar o pai diretamente ao filho do nó removido, ou seja, o nó com a chave 10 se conecta ao nó 13. A situação seria análoga se precisássemos remover um nó que é o filho esquerdo de seu pai. Pensem a respeito — é uma analogia exata.
Terceiro caso. O nó tem dois filhos.
O caso mais complexo. Vamos analisar com um novo exemplo.
Busca do sucessor.
Suponha que precisamos remover o nó com a chave 25. Quem colocaremos em seu lugar? Alguém de seus sucessores (descendentes ou descendentes de descendentes) deve se tornar o sucessor(aquele que ocupará o lugar do nó removido).
Como entender quem deve se tornar o sucessor? É intuitivamente claro que é um nó na árvore cuja chave é o próximo maior em relação ao nó removido. O algoritmo consiste no seguinte. Devemos ir para o seu filho direito (sempre para a direita, pois já foi mencionado que a chave do sucessor é maior que a chave do nó removido), e então percorrer a cadeia de filhos esquerdos desse filho direito. No exemplo, devemos ir para o nó com a chave 35 e depois descer até a folha ao longo da cadeia de seus filhos esquerdos — neste caso, essa cadeia consiste apenas no nó com a chave 30. Estritamente falando, estamos buscando o menor nó em um conjunto de nós que são maiores que o nó procurado.
Código do método para encontrar o sucessor:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode; // pai do sucessor
Node<T> successor = deleteNode; // sucessor
Node<T> current = successor.getRightChild(); // nó 'caminhante'
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
// ao sair do loop temos o sucessor e o pai do sucessor
if (successor != deleteNode.getRightChild()) { // se o sucessor não for igual ao filho direito do nó removido
parentSuccessor.setLeftChild(successor.getRightChild()); // então seu pai assume o filho do sucessor para não perdê-lo
successor.setRightChild(deleteNode.getRightChild()); // conectamos o sucessor ao filho direito do nó removido
}
return successor;
}
Código completo do método delete:
public boolean delete(int deleteKey) {
Node current = root;
Node parent = current;
boolean isLeftChild = false; // Dependendo se o nó a ser removido é um filho esquerdo ou direito de seu pai, a variável booleana isLeftChild será true ou false, respectivamente.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) { // primeiro caso
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) { // segundo caso
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else { // terceiro caso
Node successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
A complexidade pode ser aproximada a O(log(n)).
Busca pelo máximo/mínimo na árvore
É evidente como encontrar o valor mínimo/máximo na árvore — deve-se passar sequencialmente pela cadeia de elementos à esquerda/direita da árvore, respectivamente; ao chegar a uma folha, ela será o elemento mínimo/máximo.
public Node getMinimum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node getMaximum(Node startPoint) {
Node current = startPoint;
Node parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
A complexidade é O(log(n))
Percurso simétrico
O percurso é a visita a cada nó da árvore com o objetivo de realizar alguma ação com ele.
Algoritmo de percurso simétrico recursivo:
- Realizar ação com o filho esquerdo
- Realizar ação com si mesmo
- Realizar ação com o filho direito
Código:
public void inOrder(Node current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Aqui pode haver qualquer coisa
inOrder(current.getRightChild());
}
}
Conclusão
Finalmente! Se eu deixei algo sem explicação ou se há alguma observação, fico aguardando nos comentários. Como prometido, trago o código completo.
Node.java:
public class Node {
private T data;
private int key;
private Node leftChild;
private Node rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node newNode) {
leftChild = newNode;
}
public void setRightChild(Node newNode) {
rightChild = newNode;
}
public Node getLeftChild() {
return leftChild;
}
public Node getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
P.S.
Degeneração para O(n)
Muitos de vocês podem ter notado: e se fizermos com que a árvore se tornasse desbalanceada? Por exemplo, ao inserir nós com chaves crescentes: 1,2,3,4,5,6... A árvore acabaria se parecendo com uma lista encadeada. E sim, a árvore perderá sua estrutura arbórea, e, portanto, a eficiência no acesso aos dados. A complexidade das operações de busca, inserção e exclusão se tornará a mesma que a de uma lista encadeada: O(n). Essa é uma das principais desvantagens das árvores binárias, na minha opinião.
Apenas usuários registrados podem participar da pesquisa. , por favor.
Eu não estou no Habr há tanto tempo, e gostaria de saber sobre quais temas vocês gostariam de ver mais artigos?
Estruturas de dados
Algoritmos (DP, recursão, compressão de dados, etc.)
Aplicações de estruturas de dados e algoritmos na vida real
Programação de aplicativos Android em Java
Programação de aplicativos web em Java
Votaram 2 usuários. 1 usuário se absteve.
Fonte: habr.com
