find()
bool find(v)
node p, c = find'(v, &psuedo-root, pseudo-root.right)
return c != null
node, node find'(value v, node p, node c)
if c == null or c.v == v
return p, c
if c.v < v
return find'(v, c, c.right)
else
return find'(v, c, c.left)
add()
void add(value v)
node parent, child = find'(v, &pseudo-root, pseudo-root.left)
if (child == null)
if (parent == &pseudo-root) or (parent.v > v)
parent.left = new node(v)
else
parent.right = new node(v)
remove()
void remove(value v)
node parent, child = find(v, &pseudo-root, pseudo-root.left)
if (child != null)
remove_child(parent, child)
void remove_child(node parent, node child)
if (parent->left == child)
parent->left = remove_root(child)
else
parent->right = remove_root(child)
node remove_root(node root)
if root.left != null
root.v = find_max(root, root.left)
else if root.right != null
root.v = find_min(root, root.right)
else
delete root
root = null
return root
value get_max(node p, node c)
assert p != null and (p.left == c or p.right == c)
assert c != null
if c.right != null
return get_max(c, c.right)
else
v = c.v
remove_child(p, c)
return v
value get_min(node * p, node * c)
assert p != null and (p.left == c or p.right == c)
assert c != null
if c.left != null
return get_min(c, c.left)
else
v = c.v
remove_child(p, c)
return v
See the complete code.
This page last modified on 9 December 2003.