Explicando árvores para quem nunca estudou algoritmos e estrutura de dados · KitsuneSemCalda

Disclaimer

Desculpe pessoal, dessa vez o post foi dedicado a pessoas que não fizeram faculdade e nem estudaram algoritmos e estruturas de dados.

Você já parou para pensar em como bancos de dados, sistemas de árvores e outras estruturas lidam com dados de forma eficiente?

Isso acontece graças à ordenação (ou "sort", em inglês), que é essencial para organizar e buscar informações rapidamente. Existem diversos algoritmos para realizar essa tarefa, e cada um tem suas próprias características e aplicações. Vamos dar uma olhada em alguns deles:

Algoritmos de Ordenação

Os algoritmos de ordenação são como receitas que dizem ao computador a melhor forma de organizar uma lista de itens. Vamos ver alguns algoritmos populares:

Quick Sort: Utiliza a técnica de divisão e conquista para ordenar elementos rapidamente. É eficiente para a maioria dos casos, mas seu desempenho pode deteriorar em situações específicas.
Merge Sort: Também usa divisão e conquista, mas divide a lista em sub-listas menores, ordena essas sub-listas e depois as mescla. É estável e tem um desempenho previsível.
Heap Sort: Constrói uma estrutura de heap (uma árvore binária especial) e usa-a para ordenar os elementos. É eficiente, mas não é estável.

Heap é especial pois em uma das implementação é um array que pode ser trabalhado como uma árvore binária
Insertion Sort: Insere cada elemento na posição correta de uma lista ordenada. É simples e eficiente para listas pequenas ou quase ordenadas

Esses algoritmos são como receitas que dizem ao computador a melhor forma de organizar uma lista de coisas, como uma lista de compras ou uma fila de pessoas. No entanto, a maioria desses algoritmos (exceto o Insertion Sort e o Heap Sort) tem uma limitação importante: eles trabalham principalmente em arrays ou slices.

Estável vs. Não Estável

Algoritmo de Ordenação Estável: Mantém a ordem relativa dos elementos iguais na lista após a ordenação. Por exemplo, se dois elementos possuem o mesmo valor, eles manterão a ordem original entre si. O Merge Sort e o Insertion Sort são exemplos de algoritmos estáveis.
Algoritmo de Ordenação Não Estável: Não garante que a ordem relativa dos elementos iguais seja preservada. Por exemplo, a ordenação pode alterar a ordem original desses elementos iguais. O Quick Sort e o Heap Sort são exemplos de algoritmos não estáveis.

Comparação dos Algoritmos de Ordenação

Aqui está uma tabela comparativa simplificada para ajudar a visualizar as diferenças:

Algoritmo	Complexidade Média	Complexidade no Pior Caso	Estável	Uso Ideal
Quick Sort	O(n log n)	O(n^2)	Não	Listas grandes e não ordenadas
Merge Sort	O(n log n)	O(n log n)	Sim	Listas grandes e ordenadas
Heap Sort	O(n log n)	O(n log n)	Não	Ordenação em memória limitada
Insertion Sort	O(n^2)	O(n^2)	Sim	Listas pequenas ou quase ordenadas

Terminologia

Arrays: São estruturas de dados que armazenam uma coleção de elementos do mesmo tipo, acessíveis por um índice. Eles têm um tamanho fixo e são armazenados de forma contígua na memória.
Listas Ligadas: São compostas por elementos chamados de "nós". Cada nó contém um valor e um ponteiro para o próximo nó na sequência. Ao contrário dos arrays, as listas ligadas podem crescer e diminuir dinamicamente.
Nós: Em uma lista ligada, um nó é uma unidade que contém um valor e um ou mais ponteiros para conectar-se a outros nós.

Qual o problema em trabalhar com arrays e/ou slices.

Dependendo da linguagem e da forma trabalhada (vou com c++ porque é mais fácil de explicar e construir uma abordagem C like) os arrays/slices precisariam ter seu tamanho definido direto na inicialização.

E em caso de necessidade como adicionar um elemento ao meio ou ao inicio, você teria que "copiar" os elementos do array anterior ao novo array com tamanho incrementado.

Mas felizmente, você tem uma opção usar listas ligadas.

#pragma once

template <typename T>
class Node {
private:
	T value;
	Node* next;
public:
	Node(T new_value) {
		value = new_value;
		next = nullptr;
	}

	void InsertNewNode(T new_value) {
	    Node* temp = this;
	    while (temp->next != nullptr) {
	        temp = temp->next;
	    }
	    temp->next = new Node(new_value);
	}

}

A classe Node representa um nó da lista sendo encadeada pelo nó seguinte.

A cada nova inserção, a função percorre toda a lista e quando o ponteiro seguinte é nulo ele adiciona o novo valor naquele espaço.

Mas isso tem trade-offs claro. Primeiro que tu não pode usar uma entrada simples de valor como se fosse um array para acessar um elemento instantaneamente como:


int values[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int values[2] // 2

E tem um custo um pouco maior de memória já que estamos constantemente guardando novos elementos.

Mas infelizmente, apesar de podermos modificar qualquer elemento do meio, inicio ou fim da lista ligada sem overhead, precisamos percorrer todos os elementos da lista ligada para poder chegar a determinado valor.

Calma ainda estamos chegando em parte da arte toda:

OK, agora eu criei um sistema mais fácil de inserir mas, muito mais difícil de pesquisar. Lembra que eu falei que existia algoritmos de ordenação? pois bem também existe um algoritmo que serve para fazer buscas mais eficientes em arrays ordenados chamado busca binária.

template <typename T>
T binarySearch(T arr[], int size, T target) {
    int start = 0;
    int end = size - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] < target) {
            start = mid + 1;
        }

        else {
            end = mid - 1;
        }
    }

    return -1;
}

Veja que interessante, esse algoritmo segue a ideia de dividir para conquistar reduzindo ao máximo o número de interações no array.

Isso ocorre porque não precisamos correr a lista inteira se já temos a ideia inicial do valor que queremos.

Se for maior que a metade, cortamos fora a primeira metade da busca.
Se for menor que a metade, cortamos fora a segunda metade da busca.

E assim consecutivamente.

Mas, teria como fazer isso com lista ligadas? Curiosamente tem, mas primeiros temos que ir inserindo já ordenamente corretamente.


template <typename T>
class Node {
	T value;
	Node* next;
	Node* prev;

	Node(T new_value){
		this->value = new_value;
		this->next = nullptr;
		this->prev = nullptr; 
	}
};

template <typename T>
class BinarySearchTree {
    Node<T>* root;

    // Função recursiva para inserir um valor na árvore
    Node<T>* insert(Node<T>* node, T value) {
        if (node == nullptr) {
            return new TreeNode<T>(value);
        }

        if (value < node->value) {
		    node->left = insert(node->left, value);
		} else if (value > node->value) {
		    node->right = insert(node->right, value);
		}
		
        return node;
    }

    // Função recursiva para buscar um valor na árvore
    Node<T>* search(Node<T>* node, T value) const {
        if (node == nullptr || node->value == value) {
            return node;
        }

        if (value < node->value) {
            return search(node->left, value);
        } else {
            return search(node->right, value);
        }
    }

    // Função recursiva para imprimir a árvore em ordem
    void inorder(Node<T>* node) const {
        if (node != nullptr) {
            inorder(node->left);
            std::cout << node->value << " ";
            inorder(node->right);
        }
    }

    // Função recursiva para destruir a árvore
    void destroyTree(Node<T>* node) {
        if (node != nullptr) {
            destroyTree(node->left);
            destroyTree(node->right);
            delete node;
        }
    }
};

Aqui chegamos na estrutura de uma árvore de busca binária. A implementação mais rudimentar de uma árvore porque apesar de tu conseguir pesquisar como se fosse uma busca binária no melhor caso, no pior tu volta ao caso original de uma lista ligada.

Porém, existe uma forma de manter a lista constantemente ordenada que é adicionando recursos de balanceamento a árvore.

Não vou explicar agora porque envolve muitas pequenas regrinhas que a árvore precisa seguir para manter o balanceamento seja avl ou red-black tree mas, caso queiram ler um pouco existe esses links

A árvore que usamos em bancos de dados são derivação da B-Tree como B+ Tree e B* Tree pela sua capacidade de gerar sub-árvores as famosas indexações.

Linux Kernel RB-Tree: https://www.kernel.org/doc/Documentation/rbtree.txt
Linux Kernel try replace rb-tree from avl tree in cfs:https://lore.kernel.org/all/1208002923.7427.5.camel@twins/T/