by Maradona Morais
Implementações em C++ de estruturas de dados organizadas em árvore e seus algoritmos.
- Binary Tree & Binary Search Tree
- Parte do código foi reproduzida do livro "Jumping into C++" do @alexallain
- Heap Max
- Heap Min (TO DO)
Parte do arquivo Big-O Cheat Sheet
Árvore binária
Operação | Melhor caso | Pior caso |
---|---|---|
Buscar | O(log(n)) | O(n) |
Inserir | O(log(n)) | O(n) |
Deletar | O(h) | O(n) |
Em que n é a quantidade de elementos na árvore e h é a altura da mesma. Todos os casos médios foram O(log(n))
Heap Max
Operação | Complexidade |
---|---|
Construir | O(n) |
Descer | O(log(n)) |
Deletar | O(log(n)) |
Subir | O(log(n)) |
Inserir | O(log(n)) |
Heap sort | O(nlog(n)) |
Inserção: Insere no final e sobe.
Deleção: Substitui o último com o primeiro e desce o primeiro.
procedimento heapsort
arranjar(n) // O (n)
m <- n
enquanto (m > 1) faça // O (n)
troca(1, m)
m <- m - 1
descer(1, m) // O(log n)