Binary Search Tree

Tags: comp-sci

Is a data structure wrapping around a binary-tree where every node \( x \) satisfies the binary search-tree property, that is if another node \( y \) is:

In the left sub-tree of \( x \) then \( y.\text{key} \leq x.\text{key} \).
In the right sub-tree of \( x \) then \( y.\text{key} \geq x.\text{key} \).
Searching a binary search tree is a \( \mathcal{O}(n) \) time operation, but for a [see page 11, well-balanced] tree the worst-case is \( \mathcal{O}(\log n) = \mathcal{O}(h) \).

Procedures

def search(x, k):
    if not x or x.key == k:
	return x
    if k < x.key:
	return search(x.left, key)
    return search(x.right, key)

Code Snippet 1: Search for a value in a Binary Search Tree.

def successor(x):
    if x.right is not None:
	return minimum(x.right)
    y = x.parent
    while y != nil and x == y.right:
	x = y
	y = y.parent
    return y

Code Snippet 2: Find the next value in a Binary Search Tree (See see page 12, [here]).

See [see page 13, insert], [see page 14, delete].

Links to this note

AVL Trees