Skip to content

Data structures

Binary-Search Tree

a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

BST can be used for implementing a K→V dictionary API.

def insert(key, value, bst):
  if bst.key is None or bst.key == key: # empty tree
    bst.key = value
  elif bst.key < key:
    insert(key, value, bst.left)
    insert(key, value, bst.right)

Hash function

Hash function: uniformity.

Chaining is better than linear probing when the load factor increases. How to choose hash function for String.