Binary Search Tree
- 3 min read
- Data Structure
- Binary Search Tree
3 years ago
- A BST relies on the property that a node's left child has a lesser value than itself, and subsequently, it's right child has a value that is greater than itself.
- An inorder traversal of a BST returns the elements in sorted order.
- Inserting and getting a node is pretty simple.
- Deleting a node with no children or one child is also pretty easy but annoying due to multiple if-statements.
- Deleting a node with two children is tricky- what we need to do is replace the node to be deleted with it's successor.
- A successor of a node in a BST is guaranteed to have no more than one child.
- For a node with two childen, it's successor is the leftmost node on it's right subtree.
- Remember: The smallest value in a BST will always be the left-most node
- In a balanced binary tree (i.e. roughly same number of nodes in left and right subtree), performance of
putisO(log n), wherenis the number of nodes in tree. - If keys are inserted in sorted order, tree won't be balanced, it will have height
n, and time complexity forputdegrades toO(n)
class Node:
def __init__(self, key, val, left=None, right=None, parent=None):
self.key = key
self.val = val
self.left = left
self.right = right
self.parent = parent
def is_left_child(self):
return self.parent and self.parent.left == self
def is_right_child(self):
return self.parent and self.parent.right == self
def is_root(self):
return not self.parent
def is_leaf(self):
return not self.left and not self.right
def has_one_child(self):
return (self.left or self.right) and not (self.right and self.left)
def __str__(self):
return f"{self.key}: {self.val}"
def __iter__(self):
if self:
if self.left:
for elem in self.left:
yield elem
yield self.key
if self.right:
for elem in self.right:
yield elem
class BST:
def __init__(self):
self.root = None
self.size = 0
def __len__(self):
return self.length
def __iter__(self):
return self.root.__iter__()
def _put(self, key, val, current_node):
if key < current_node.key:
if current_node.left:
self._put(key, val, current_node.left)
else:
current_node.left = Node(key, val, parent=current_node)
else:
if current_node.right:
self._put(key, val, current_node.right)
else:
current_node.right = Node(key, val, parent=current_node)
def put(self, key, val):
if self.root is None:
self.root = Node(key, val)
else:
self._put(key, val, self.root)
def __setitem__(self, k, v):
self.put(k, v)
self.size += 1
def get(self, key, current_node):
if current_node is None:
return None
if key == current_node.key:
return current_node
elif key > current_node.key:
return self.get(key, current_node.right)
else:
return self.get(key, current_node.left)
def __getitem__(self, k):
return self.get(k, self.root)
def __contains__(self, k):
if self.get(k):
return True
return False
def get_successor(self, node):
current = node.right
while current.left:
current = current.left
return current
def _delete(self, node):
if node.is_leaf():
if node.is_left_child():
node.parent.left = None
else:
node.parent.right = None
elif node.has_one_child():
if node.is_left_child():
if node.left:
node.left.parent = node.parent
node.parent.left = node.left
else:
node.right.parent = node.parent
node.parent.left = node.right
elif node.is_right_child():
if node.left:
node.left.parent = node.parent
node.parent.right = node.left
else:
node.right.parent = node.parent
node.parent.right = node.right
elif node.is_root():
if node.left:
node.left.parent = None
self.root = node.left
else:
node.right.parent = None
self.root = node.right
else:
successor = self.get_successor(node)
self._delete(successor)
successor.left = node.left
successor.right = node.right
if node == self.root:
successor.parent = None
self.root = successor
elif node.is_left_child():
node.parent.left = successor
else:
node.parent.right = successor
def delete(self, k):
if self.size == 0:
return KeyError('Key not in tree!')
elif self.size == 1:
self.root = None
self.size -= 1
else:
node_to_remove = self.get(k, self.root)
if node_to_remove is None:
return KeyError('Key not in tree!')
else:
self._delete(node_to_remove)
self.size -= 1
def __delitem__(self, k):
self.delete(k)