Binary Search Tree

Data Structures

avgO(log n)worstO(n)spaceO(n)

A BST with 7 keys, rooted at 50

1 / 38

Code

class Node {  left: Node | null = null;  right: Node | null = null;  constructor(public key: number) {}}class BST {  root: Node | null = null;  insert(key: number) {    if (!this.root) return void (this.root = new Node(key));    let cur = this.root;    while (key !== cur.key) {      const side = key < cur.key ? "left" : "right";      if (!cur[side]) return void (cur[side] = new Node(key));      cur = cur[side]!;    }  }  search(key: number) {    let cur = this.root;    while (cur && cur.key !== key) {      cur = key < cur.key ? cur.left : cur.right;    }    return cur;  }  delete(key: number) {    this.root = this.remove(this.root, key);  }  private remove(node: Node | null, key: number): Node | null {    if (!node) return null;    if (key < node.key) node.left = this.remove(node.left, key);    else if (key > node.key) node.right = this.remove(node.right, key);    else {      if (!node.left) return node.right;      if (!node.right) return node.left;      let succ = node.right;      while (succ.left) succ = succ.left;      node.key = succ.key;      node.right = this.remove(node.right, succ.key);    }    return node;  }}

structure Node(key)  left ← null  right ← null  keyend structurestructure BST  root ← null  procedure insert(key)    if root = null then root ← Node(key); return    cur ← root    while key ≠ cur.key do      side ← left if key < cur.key else right      if cur.side = null then cur.side ← Node(key); return      cur ← cur.side    end while  end procedure  procedure search(key)    cur ← root    while cur ≠ null and cur.key ≠ key do      cur ← cur.left if key < cur.key else cur.right    end while    return cur  end procedure  procedure delete(key)    root ← remove(root, key)  end procedure  function remove(node, key)    if node = null then return null    if key < node.key then node.left ← remove(node.left, key)    else if key > node.key then node.right ← remove(node.right, key)    else      if node.left = null then return node.right      if node.right = null then return node.left      succ ← node.right    ▷ in-order successor:      while succ.left ≠ null do succ ← succ.left    ▷ leftmost of the right subtree      node.key ← succ.key      node.right ← remove(node.right, succ.key)    end if    return node  end functionend structure

Variables

n=7

Counters

comparisons: 0

Starting contents7 values

Operations7 / 40

1. insert(35)
2. insert(65)
3. search(60)
4. delete(20)
5. delete(70)
6. delete(30)
7. search(45)

How it works

Every key in a node's left subtree is smaller and every key in its right subtree is larger, so search, insert and delete each follow one root-to-leaf path. Deleting a node with two children swaps in its in-order successor. It is fast when balanced, but inserting keys in sorted order turns it into a linked list.

Complexity

Best: O(log n)
Average: O(log n)
Worst: O(n)
Space: O(n)

Binary Search Tree

How it works

Complexity

Search algorithms