Estruturas de Dados com Golang - Parte 2

27/04/20268 min de leitura

Lucas Lemos

Introdução

No artigo anterior cobrimos Listas e suas variações mais comuns. Hoje vamos continuar com Árvores, que são estruturas hierárquicas não lineares usadas em todo lugar: sistemas de arquivos, bancos de dados, parsers, tabelas de roteamento e até na forma como alguns compiladores representam código.

Vamos manter a mesma interface Container do primeiro artigo para que todas as implementações fiquem consistentes:

type Container interface {
  Empty() bool
  Size() int
  Clear()
  Values() []interface{}
  String() string
}

Árvores

Uma Árvore é uma estrutura de dados hierárquica formada por nós conectados por arestas. Diferente das Listas, onde cada elemento tem no máximo um sucessor, em uma Árvore cada nó pode ter múltiplos filhos. Existe um nó especial chamado raiz no topo da estrutura e a partir dele o restante da árvore se ramifica.

Visualmente uma árvore se parece com isso:

Nesse diagrama A é a raiz, B e C são seus filhos, e D, E, F são folhas (nós sem filhos).

Terminologia

Antes de entrar nas variações, vale alinhar alguns termos:

Nó: cada elemento da árvore, guarda um valor e referências para seus filhos.
Raiz: o nó mais acima da árvore.
Pai / Filho: um nó conectado diretamente acima (pai) ou abaixo (filho).
Folha: um nó sem filhos.
Profundidade: distância da raiz até o nó.
Altura: distância do nó até sua folha descendente mais profunda.
Subárvore: qualquer nó junto com todos os seus descendentes.

Travessias

Existem algumas formas comuns de visitar todos os nós de uma árvore. Usando a árvore de exemplo acima:

As quatro travessias principais produzem essas ordens:

Pré-ordem (Raiz → Esquerda → Direita): A, B, D, E, C, F
Em ordem (Esquerda → Raiz → Direita): D, B, E, A, C, F
Pós-ordem (Esquerda → Direita → Raiz): D, E, B, F, C, A
Em nível / BFS (de cima para baixo, da esquerda para a direita): A, B, C, D, E, F

Pré/em/pós-ordem são geralmente implementadas com recursão, enquanto a travessia em nível usa uma fila.

Binary Trees

Uma Binary Tree é uma árvore em que todo nó tem no máximo dois filhos, geralmente chamados Left e Right. É a variação mais comum e a base de muitas outras.

Uma implementação básica de nó e árvore em Go:

type BinaryTreeNode[V any] struct {
  Value V
  Left  *BinaryTreeNode[V]
  Right *BinaryTreeNode[V]
}

type BinaryTree struct {
  root *BinaryTreeNode[interface{}]
  size int
}

func (t *BinaryTree) Empty() bool {
  return t.size == 0
}

func (t *BinaryTree) Size() int {
  return t.size
}

func (t *BinaryTree) Clear() {
  t.root = nil
  t.size = 0
}

func (t *BinaryTree) Values() []interface{} {
  values := make([]interface{}, 0, t.size)
  inOrder(t.root, &values)
  return values
}

func (t *BinaryTree) String() string {
  return fmt.Sprintf("%v", t.Values())
}

func inOrder(n *BinaryTreeNode[interface{}], out *[]interface{}) {
  if n == nil {
    return
  }
  inOrder(n.Left, out)
  *out = append(*out, n.Value)
  inOrder(n.Right, out)
}

Uma Binary Tree pura não impõe ordenação dos valores, então ela é mais útil como base para outras estruturas ou quando o que importa é a hierarquia em si.

Binary Search Trees

Uma Binary Search Tree (BST) é uma Binary Tree com uma regra extra: para todo nó, todos os valores na subárvore da esquerda são menores e todos os valores na subárvore da direita são maiores.

Esse invariante torna busca, inserção e remoção O(log n) em média, porque a cada passo dividimos o espaço de busca pela metade. No pior caso (uma árvore totalmente desbalanceada) a complexidade cai para O(n), que é exatamente o problema que as AVL Trees resolvem.

Uma implementação simples de BST em Go, reutilizando BinaryTreeNode[int] como tipo de nó já que a estrutura por baixo é a mesma:

type BinarySearchTree struct {
  root *BinaryTreeNode[int]
  size int
}

func (t *BinarySearchTree) Insert(value int) {
  newRoot, inserted := insertBST(t.root, value)
  t.root = newRoot
  if inserted {
    t.size++
  }
}

func (t *BinarySearchTree) Contains(value int) bool {
  return searchBST(t.root, value) != nil
}

func (t *BinarySearchTree) Empty() bool {
  return t.size == 0
}

func (t *BinarySearchTree) Size() int {
  return t.size
}

func (t *BinarySearchTree) Clear() {
  t.root = nil
  t.size = 0
}

func (t *BinarySearchTree) Values() []interface{} {
  values := make([]interface{}, 0, t.size)
  bstInOrder(t.root, &values)
  return values
}

func (t *BinarySearchTree) String() string {
  return fmt.Sprintf("%v", t.Values())
}

func insertBST(n *BinaryTreeNode[int], value int) (*BinaryTreeNode[int], bool) {
  if n == nil {
    return &BinaryTreeNode[int]{Value: value}, true
  }
  if value < n.Value {
    newLeft, inserted := insertBST(n.Left, value)
    n.Left = newLeft
    return n, inserted
  }
  if value > n.Value {
    newRight, inserted := insertBST(n.Right, value)
    n.Right = newRight
    return n, inserted
  }
  return n, false
}

func searchBST(n *BinaryTreeNode[int], value int) *BinaryTreeNode[int] {
  if n == nil || n.Value == value {
    return n
  }
  if value < n.Value {
    return searchBST(n.Left, value)
  }
  return searchBST(n.Right, value)
}

func bstInOrder(n *BinaryTreeNode[int], out *[]interface{}) {
  if n == nil {
    return
  }
  bstInOrder(n.Left, out)
  *out = append(*out, n.Value)
  bstInOrder(n.Right, out)
}

O método Insert retorna se o valor foi de fato inserido, o que mantém o size correto quando duplicados são ignorados.

O método Values() retorna os elementos já ordenados de graça, já que uma travessia em ordem em uma BST sempre produz uma sequência ordenada.

AVL Trees

O grande problema de uma BST simples é o balanceamento: se você inserir dados ordenados, ela degenera em uma lista encadeada e as buscas viram O(n). AVL Trees resolvem isso mantendo a árvore balanceada após cada inserção ou remoção.

Uma AVL Tree é uma BST onde, para todo nó, as alturas das subárvores esquerda e direita diferem em no máximo um. Quando esse invariante quebra, a árvore se conserta sozinha usando rotações.

Uma rotação à direita se parece com isso:

        y                   x
       / \                 / \
      x   T3      =>      T1  y
     / \                     / \
    T1  T2                  T2  T3

Uma implementação básica de AVL em Go:

type AVLNode struct {
  Value  int
  Height int
  Left   *AVLNode
  Right  *AVLNode
}

type AVLTree struct {
  root *AVLNode
  size int
}

func (t *AVLTree) Insert(value int) {
  newRoot, inserted := insertAVL(t.root, value)
  t.root = newRoot
  if inserted {
    t.size++
  }
}

func (t *AVLTree) Empty() bool {
  return t.size == 0
}

func (t *AVLTree) Size() int {
  return t.size
}

func (t *AVLTree) Clear() {
  t.root = nil
  t.size = 0
}

func (t *AVLTree) Values() []interface{} {
  values := make([]interface{}, 0, t.size)
  avlInOrder(t.root, &values)
  return values
}

func (t *AVLTree) String() string {
  return fmt.Sprintf("%v", t.Values())
}

func avlHeight(n *AVLNode) int {
  if n == nil {
    return 0
  }
  return n.Height
}

func avlBalance(n *AVLNode) int {
  if n == nil {
    return 0
  }
  return avlHeight(n.Left) - avlHeight(n.Right)
}

func rotateRight(y *AVLNode) *AVLNode {
  x := y.Left
  t2 := x.Right
  x.Right = y
  y.Left = t2
  y.Height = 1 + max(avlHeight(y.Left), avlHeight(y.Right))
  x.Height = 1 + max(avlHeight(x.Left), avlHeight(x.Right))
  return x
}

func rotateLeft(x *AVLNode) *AVLNode {
  y := x.Right
  t2 := y.Left
  y.Left = x
  x.Right = t2
  x.Height = 1 + max(avlHeight(x.Left), avlHeight(x.Right))
  y.Height = 1 + max(avlHeight(y.Left), avlHeight(y.Right))
  return y
}

func insertAVL(node *AVLNode, value int) (*AVLNode, bool) {
  if node == nil {
    return &AVLNode{Value: value, Height: 1}, true
  }

  var inserted bool
  if value < node.Value {
    node.Left, inserted = insertAVL(node.Left, value)
  } else if value > node.Value {
    node.Right, inserted = insertAVL(node.Right, value)
  } else {
    return node, false
  }

  if !inserted {
    return node, false
  }

  node.Height = 1 + max(avlHeight(node.Left), avlHeight(node.Right))
  bf := avlBalance(node)

  if bf > 1 && value < node.Left.Value {
    return rotateRight(node), true
  }
  if bf < -1 && value > node.Right.Value {
    return rotateLeft(node), true
  }
  if bf > 1 && value > node.Left.Value {
    node.Left = rotateLeft(node.Left)
    return rotateRight(node), true
  }
  if bf < -1 && value < node.Right.Value {
    node.Right = rotateRight(node.Right)
    return rotateLeft(node), true
  }

  return node, true
}

func avlInOrder(n *AVLNode, out *[]interface{}) {
  if n == nil {
    return
  }
  avlInOrder(n.Left, out)
  *out = append(*out, n.Value)
  avlInOrder(n.Right, out)
}

A árvore lida com os quatro casos clássicos de desbalanceamento (LL, RR, LR, RL) e garante operações O(log n) mesmo no pior caso.

Qual delas você deve usar?

Não existe a melhor árvore universal, a escolha certa depende do problema:

Binary Tree: útil como estrutura base genérica ou quando você precisa de uma hierarquia sem regras de ordenação.
Binary Search Tree: boa quando os dados tendem a chegar em ordem aleatória e operações O(log n) na média já são suficientes.
AVL Tree: melhor quando você precisa de buscas O(log n) garantidas e os dados podem chegar ordenados ou em padrões adversariais.

Outras variações como Red-Black Trees, B-Trees, Tries e Heaps resolvem problemas mais específicos, mas todas se constroem em cima das ideias mostradas aqui.

Conclusão

Hoje cobrimos Árvores de ponta a ponta: a terminologia básica, as quatro travessias mais comuns e três variações importantes (Binary Trees, Binary Search Trees e AVL Trees) com implementações seguindo a mesma interface Container do artigo anterior.

No próximo artigo vamos entrar em outra categoria de estrutura de dados e manter a mesma abordagem mostrada aqui.