Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. When inserting or searching for an element in a binary search tree, the key of each visited node has to be compared with the key of the element to be inserted or found.Wikipedia
Binary Tree: A tree that starts at a single root and branches down, all nodes have a minimum of 0 children (leaves) and a maximum of 2 children.
Complete Binary Tree: All levels are full except at the bottom level, all levels are filled left to right.
Full Binary Tree: All nodes have 2 children or 0 children (leaf).
Binary Search Tree: A binary tree with the Search Tree Property.
Search Tree Property: For any node x, all nodes in it’s left subtree are less than x and all nodes in its right subtree are greater than or equal to x.
Binary Search Tree Algorithms
def search(key, node): if node is None or node.key == key: return node if key < node.key: return search(key, node.left) else: return search(key, node.right)
def insertion: - Search and insert where we fell off tree
def find_min(node): if node.left is None: return node else: return find_min(node.left)
def find_max(node): if node.right is None: return node else: return find_max(node. right)
def successor(node): if node.right: return find_min(node.right) else: Go up until you find a node with it's parent on the right, return parent
def delete(node): if node is leaf: delete node if node has one child: connect node parent to node child delete node if node has 2 children: swap node with successor(node) delete (node)
Find Min: O(h)
Find Max: O(h)
h can range from
O( log (n) ) – Best Case, Balanced BST
O(n) – Worst Case, Linked List BST