Prelúdio
Este artigo é sobre árvores de busca binária. Recentemente escrevi um artigo sobre Lá eu realmente não prestei atenção às árvores binárias, porque os métodos de pesquisa, inserção e exclusão não eram relevantes. Agora decidi escrever um artigo sobre árvores. Talvez possamos começar.
Uma árvore é uma estrutura de dados que consiste em nós conectados por arestas. Podemos dizer que uma árvore é um caso especial de grafo. Aqui está um exemplo de árvore:
Esta não é uma árvore de busca binária! Tudo está sob o corte!
Vocabulário
raiz
Raiz da árvore é o nó mais alto. No exemplo, este é o nó A. Na árvore, apenas um caminho pode levar da raiz a qualquer outro nó! De fato, qualquer nó pode ser considerado como a raiz da subárvore correspondente a esse nó.
Pais/filhos
Todos os nós, exceto a raiz, têm exatamente uma aresta que leva a outro nó. O nó acima do nó atual é chamado pai este nó. Um nó localizado abaixo do atual e conectado a ele é chamado descendente este nó. Vamos dar um exemplo. Pegue 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 é chamado de folha da árvore. No exemplo, os nós D, E, F, G, I, J, K serão folhas.
Esta é a terminologia básica. Outros conceitos serão discutidos posteriormente. Assim, uma árvore binária é uma árvore em que cada nó não terá mais do que dois filhos. Como você adivinhou, a árvore do exemplo não será binária, porque os nós B e H têm mais de dois filhos. Aqui está um exemplo de uma árvore binária:
Os nós da árvore podem conter qualquer informação. Uma árvore binária de pesquisa é uma árvore binária que possui as seguintes propriedades:
- As subárvores esquerda e direita são árvores de pesquisa binária.
- Todos os nós da subárvore esquerda de um nó arbitrário X têm valores de chave de dados menores que o valor de chave de dados do próprio nó X.
- Todos os nós da subárvore direita de um nó arbitrário X possuem valores de chave de dados maiores ou iguais ao valor da chave de dados do próprio nó X.
Ключ - alguma característica do nó (por exemplo, um número). A chave é necessária para poder encontrar o elemento da árvore ao qual esta chave corresponde. Exemplo de árvore de pesquisa binária:
visualização em árvore
À medida que for avançando, incluirei alguns trechos de código (talvez incompletos) para melhorar sua compreensão. O código completo estará no final do artigo.
A árvore é composta de nós. Estrutura do 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;
}
//...остальные методы узла
}
Cada nó tem dois filhos (é bem possível que os filhos leftChild e/ou rightChild sejam nulos). Você provavelmente entendeu que, neste caso, os dados numéricos são os dados armazenados no nó; chave - chave do nó.
Descobrimos o nó, agora vamos falar sobre os problemas prementes das árvores. Daqui em diante, a palavra "árvore" significará o conceito de uma árvore de busca binária. Estrutura da árvore binária:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Como um campo de classe, precisamos apenas da raiz da árvore, pois a partir da raiz, usando os métodos getLeftChild() e getRightChild(), você pode chegar a qualquer nó da árvore.
Algoritmos de árvore
Pesquisa
Digamos que você tenha uma árvore construída. Como encontrar elemento com chave chave? Você precisa se mover sequencialmente da raiz para baixo na árvore e comparar o valor da chave com a chave do próximo nó: se a chave for menor que a chave do próximo nó, vá para o descendente esquerdo do nó, se for maior - à direita, se as chaves forem iguais - o nó desejado foi encontrado! Código relevante:
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 tornar nulo, a iteração atingiu o fim da árvore (em um nível conceitual, você está em um lugar inexistente na árvore - um filho de uma folha).
Considere a eficiência do algoritmo de busca em uma árvore balanceada (uma árvore na qual os nós são distribuídos de forma mais ou menos uniforme). Então a eficiência de busca será O(log(n)), e o logaritmo de base 2. Veja: se houver n elementos em uma árvore balanceada, isso significa que haverá log(n) níveis de base 2 da árvore. E na busca, por uma etapa do ciclo, você desce um nível.
inserir
Se você captou a essência da busca, não será difícil para você entender a inserção. Você só precisa descer até a folha da árvore (de acordo com as regras de descida descritas na busca) e se tornar seu descendente - esquerdo ou direito, 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;
}
}
}
}
}
Nesse caso, além do nó atual, é necessário armazenar informações sobre o pai do nó atual. Quando current se tornar nulo, a variável pai conterá a planilha de que precisamos.
A eficiência de inserção obviamente será a mesma da busca - O(log(n)).
Remoção
A exclusão é a operação mais complexa que precisará ser feita com uma árvore. É claro que primeiro será necessário encontrar o elemento que vamos remover. Mas e daí? Se simplesmente definirmos sua referência como nula, perderemos informações sobre a subárvore cuja raiz é esse nó. Os métodos de remoção de árvores são divididos em três casos.
Primeiro caso. O nó a ser removido não tem filhos.
Se o nó a ser excluído não tiver filhos, significa que é uma folha. Portanto, você pode simplesmente definir os campos leftChild ou rightChild de seu pai como nulo.
Segundo caso. O nó a ser removido tem um filho
Este caso também não é muito difícil. Voltemos ao nosso exemplo. Suponha que precisamos excluir um elemento com chave 14. Concorde que, como é o filho certo do nó com chave 10, qualquer um de seus descendentes (neste caso, o correto) terá uma chave maior que 10, então você pode facilmente "cortá-lo" da árvore e conectar o pai diretamente ao filho do nó que está sendo excluído, ou seja, conecte o nó com a chave 10 ao nó 13. A situação seria semelhante se tivéssemos que excluir um nó que é o filho esquerdo de seu pai. Pense nisso por si mesmo - uma analogia exata.
Terceiro caso. O nó tem dois filhos
O caso mais difícil. Vamos dar uma olhada em um novo exemplo.
Procure um sucessor
Digamos que precisamos remover o nó com a chave 25. Quem devemos colocar em seu lugar? Um de seus seguidores (descendentes ou descendentes de descendentes) deve se tornar sucessor(aquele que ocupará o lugar do nó removido).
Como você sabe quem deve ser o sucessor? Intuitivamente, este é o nó na árvore cuja chave é a próxima maior do nó que está sendo removido. O algoritmo é o seguinte. Você precisa ir até seu filho direito (sempre para o filho certo, pois já foi dito que a chave do sucessor é maior que a chave do nó que está sendo deletado), e então percorrer a cadeia de filhos esquerdos deste direito criança. No exemplo, devemos ir até o nó com a chave 35 e depois descer a cadeia de seus filhos esquerdos até a folha - neste caso, essa cadeia consiste apenas no nó com a chave 30. A rigor, estamos procurando o menor nó no conjunto de nós maior que o nó desejado.
Código do método de pesquisa sucessor:
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;
}
O código completo do método delete:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или 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;
}
A complexidade pode ser aproximada para O(log(n)).
Encontrando o máximo/mínimo em uma árvore
Obviamente, como encontrar o valor mínimo / máximo na árvore - você precisa percorrer sequencialmente a cadeia de elementos esquerdo / direito da árvore, respectivamente; quando você chegar à folha, será o elemento mínimo/máximo.
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;
}
Complexidade - O(log(n))
Desvio simétrico
Traversal é uma visita a cada nó da árvore para fazer algo com ele.
Algoritmo de travessia simétrica recursiva:
- Faça uma ação no filho esquerdo
- Faça uma ação com você mesmo
- Faça uma ação na criança certa
Código:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Conclusão
Finalmente! Se eu não expliquei algo ou tenho algum comentário, estou esperando nos comentários. Como prometido, aqui está o código completo.
Nó.java:
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 void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> 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());
}
}
}
PS
Degeneração para O(n)
Muitos de vocês devem ter notado: e se você desequilibrar a árvore? Por exemplo, coloque nós na árvore com chaves crescentes: 1,2,3,4,5,6... Então a árvore será um pouco reminiscente de uma lista encadeada. E sim, a árvore perderá sua estrutura de árvore e, portanto, a eficiência do acesso aos dados. A complexidade das operações de pesquisa, inserção e exclusão será a mesma de uma lista encadeada: O(n). Esta é uma das desvantagens mais importantes, na minha opinião, das árvores binárias.
Apenas usuários registrados podem participar da pesquisa. por favor
Há muito tempo que não entro no Habré e gostaria de saber quais artigos sobre quais tópicos você gostaria de ver mais?
-
Estruturas de dados
-
Algoritmos (DP, recursão, compressão de dados, etc.)
-
Aplicação de estruturas de dados e algoritmos na vida real
-
Programando aplicativos Android em Java
-
Programação de aplicativos Web Java
2 usuários votaram. 1 usuário se absteve.
Fonte: www.habr.com