מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים - פסוודו-קוד
להלן הפסוודו-קוד המלא לעצי חיפוש בינריים:
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