מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים - פסוודו-קוד

Node
	# The key this node holds.
1	key
 
	# Parent.
2	parent
 
	# Left child.
3	l-child
	# Right child.
4	r-child
 
 
# Makes a node with a given key (k)
Make-Node(k)
1	nd = Node()
 
2	nd.key = k
 
3	nd.parent = nd.l-child = nd.r-child = Nil
 
4	return nd
 
 
Binary-Search-Tree
	# The root (shoresh).
1		root
	# Number of nodes.
2		size
 
 
# Makes an empty BST.	
Make-Binary-Search-Tree()
1	t = Binary-Search-Tree()
 
2	t.root = Nil
3	t.size = 0
 
4	return t
 
 
# Searches a tree (t) for a key (k).
# Returns a (pointer to a) node containing an equivalent key to k
#	if t has one; Nil otherwise.
Find(t, k)
1	nd = t.root
 
2	while nd != Nil
3		if k  nd.key
4			nd = nd.r-child
5		else
6			return nd
 
7	return Nil
 
 
# Takes a (pointer to a) node (nd). 
# Retuns (a pointer to) the minimum node in the subtree of nd.
Min(nd)
1	while nd.l-child != Nil
2		nd = nd.l-child
 
3	return nd
 
 
# Takes a (pointer to a) node (nd). 
# Retuns (a pointer to) the maximum node in the subtree of nd.
Max(nd)
1	while nd.r-child != Nil
2		nd = nd.r-child
 
3	return nd
 
 
# Takes a (pointer to a) node (nd). 
# Retuns (a pointer to) the "next" node.
Successor(nd)
1	if nd.r-child != Nil
2		return Min(nd.r_child)
 
3	parent = nd.parent
 
4	while parent != Nil and nd == parent.r-child
5		nd = parent
6		parent = parent.parent
 
7	return parent
 
 
# Takes a (pointer to a) node (nd). 
# Retuns (a pointer to) the "previous" node.
Predecessor(nd)
1	if nd.l-child != Nil
2		return Max(nd.l_child)
 
3	parent = nd.parent
 
4	while parent != Nil and nd == parent.l-child
5		nd = parent
6		parent = parent.parent
 
7	return parent
 
 
# Inserts a key (k) to a tree (t).
Insert(t, k)
1	++t.size
 
2	parent = Nil
3	nd = t.root
 
4	while nd != Nil
5		parent = nd
 
6		nd = k k < nd.key ? nd.l-child : nd.r-child
 
7	new-nd = Make-Node(k)
 
8	if parent == Nil
9		t.root = New_nd
10	else 
11		if k < parent.key
12			parent.l-child = new-nd
13		else
14			parent.r-child = new-nd
 
15		new-nd.parent = parent
 
 
# Splices (removes) a node (nd) from a tree (t).
# The node (nd) must not have two children.
Splice(t, nd)
1	child = nd.l_child == Nil ? nd.r-child : nd.l-child
 
2	parent = nd.parent
 
3	if child != Nil
4		child.parent = parent
 
5	if parent == Nil
6		t.root = child
7		return
 
8	if nd.key < parent.key
9		parent.l-child = child
10	else 
11		parent.r-child = child	
 
 
# Erases a node (nd) from a tree (t).
Erase(t, nd)
1	--t.size	
 
2	if nd.l-child == Nil or nd.r-child == Nil
3		Splice(t, nd)
4		return
 
5	spliced = Min(nd.r-child)
 
6	Splice(t, spliced)
 
7	nd.key = spliced.key