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.
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 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 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 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 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 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 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 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 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 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 | Access | Search | Insertion | Deletion |
|---|---|---|---|
| O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
O(n)
