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

להלן הפסוודו-קוד המלא לעצי חיפוש בינריים:

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 < 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