javascript-algorithms
Binary Search Tree
Read this in other languages: Português
In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store “items” (such as numbers, names etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by name).
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, on the basis of the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.
A binary search tree of size 9 and depth 3, with 8 at the root. The leaves are not drawn.
Pseudocode for Basic Operations
Insertion
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
Searching
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
Deletion
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
Find Parent of Node
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
Find Node
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
Find Minimum
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
Find Maximum
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
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
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
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
Complexities
Time Complexity
| Access | Search | Insertion | Deletion |
|---|---|---|---|
| O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |
Space Complexity
O(n)