javascript-algorithms
Árvore de Pesquisa Binária (Binary Search Tree)
Na ciência da computação binary search trees (BST), algumas vezes chamadas de árvores binárias ordenadas (ordered or sorted binary trees), é um tipo particular de container: estruturas de dados que armazenam “itens” (como números, nomes, etc.) na memória. Permite pesquisa rápida, adição e remoção de itens além de poder ser utilizado para implementar tanto conjuntos dinâmicos de itens ou, consultar tabelas que permitem encontrar um item por seu valor chave. E.g. encontrar o número de telefone de uma pessoa pelo seu nome.
Árvore de Pesquisa Binária mantem seus valores chaves ordenados, para que uma pesquisa e outras operações possam usar o princípio da pesquisa binária: quando pesquisando por um valor chave na árvore (ou um lugar para inserir uma nova chave), eles atravessam a árvore da raiz para a folha, fazendo comparações com chaves armazenadas nos nós da árvore e decidindo então, com base nas comparações, continuar pesquisando nas sub-árvores a direita ou a esquerda. Em média isto significa que cara comparação permite as operações pular metade da árvore, para que então, cada pesquisa, inserção ou remoção consuma tempo proporcional ao logaritmo do número de itens armazenados na árvore. Isto é muito melhor do que um tempo linear necessário para encontrar itens por seu valor chave em um array (desorndenado - unsorted), mas muito mais lento do que operações similares em tableas de hash (hash tables).
Uma pesquisa de árvore binária de tamanho 9 e profundidade 3, com valor 8 na raíz. As folhas não foram desenhadas.
Pseudocódigo para Operações Básicas
Inserção
insert(value)
Pre: value has passed custom type checks for type T
Post: value has been placed in the correct location in the tree
if root = ø
root ← node(value)
else
insertNode(root, value)
end if
end insert
insertNode(current, value)
Pre: current is the node to start from
Post: value has been placed in the correct location in the tree
if value < current.value
if current.left = ø
current.left ← node(value)
else
InsertNode(current.left, value)
end if
else
if current.right = ø
current.right ← node(value)
else
InsertNode(current.right, value)
end if
end if
end insertNode
Pesquisa
contains(root, value)
Pre: root is the root node of the tree, value is what we would like to locate
Post: value is either located or not
if root = ø
return false
end if
if root.value = value
return true
else if value < root.value
return contains(root.left, value)
else
return contains(root.right, value)
end if
end contains
Remoção
remove(value)
Pre: value is the value of the node to remove, root is the node of the BST
count is the number of items in the BST
Post: node with value is removed if found in which case yields true, otherwise false
nodeToRemove ← findNode(value)
if nodeToRemove = ø
return false
end if
parent ← findParent(value)
if count = 1
root ← ø
else if nodeToRemove.left = ø and nodeToRemove.right = ø
if nodeToRemove.value < parent.value
parent.left ← nodeToRemove.right
else
parent.right ← nodeToRemove.right
end if
else if nodeToRemove.left != ø and nodeToRemove.right != ø
next ← nodeToRemove.right
while next.left != ø
next ← next.left
end while
if next != nodeToRemove.right
remove(next.value)
nodeToRemove.value ← next.value
else
nodeToRemove.value ← next.value
nodeToRemove.right ← nodeToRemove.right.right
end if
else
if nodeToRemove.left = ø
next ← nodeToRemove.right
else
next ← nodeToRemove.left
end if
if root = nodeToRemove
root = next
else if parent.left = nodeToRemove
parent.left = next
else if parent.right = nodeToRemove
parent.right = next
end if
end if
count ← count - 1
return true
end remove
Encontrar o Nó Pai
findParent(value, root)
Pre: value is the value of the node we want to find the parent of
root is the root node of the BST and is != ø
Post: a reference to the prent node of value if found; otherwise ø
if value = root.value
return ø
end if
if value < root.value
if root.left = ø
return ø
else if root.left.value = value
return root
else
return findParent(value, root.left)
end if
else
if root.right = ø
return ø
else if root.right.value = value
return root
else
return findParent(value, root.right)
end if
end if
end findParent
Encontrar um Nó
findNode(root, value)
Pre: value is the value of the node we want to find the parent of
root is the root node of the BST
Post: a reference to the node of value if found; otherwise ø
if root = ø
return ø
end if
if root.value = value
return root
else if value < root.value
return findNode(root.left, value)
else
return findNode(root.right, value)
end if
end findNode
Encontrar Mínimo
findMin(root)
Pre: root is the root node of the BST
root = ø
Post: the smallest value in the BST is located
if root.left = ø
return root.value
end if
findMin(root.left)
end findMin
Encontrar Máximo
findMax(root)
Pre: root is the root node of the BST
root = ø
Post: the largest value in the BST is located
if root.right = ø
return root.value
end if
findMax(root.right)
end findMax
Traversal
Na Ordem Traversal (InOrder Traversal)
inorder(root)
Pre: root is the root node of the BST
Post: the nodes in the BST have been visited in inorder
if root = ø
inorder(root.left)
yield root.value
inorder(root.right)
end if
end inorder
Pré Ordem Traversal (PreOrder Traversal)
preorder(root)
Pre: root is the root node of the BST
Post: the nodes in the BST have been visited in preorder
if root = ø
yield root.value
preorder(root.left)
preorder(root.right)
end if
end preorder
Pós Ordem Traversal (PostOrder Traversal)
postorder(root)
Pre: root is the root node of the BST
Post: the nodes in the BST have been visited in postorder
if root = ø
postorder(root.left)
postorder(root.right)
yield root.value
end if
end postorder
Complexidades
Complexidade de Tempo
| Access | Search | Insertion | Deletion |
|---|---|---|---|
| O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
Complexidade de Espaço
O(n)