// Copyright 2013, University of Freiburg,
// Chair of Algorithms and Data Structures.
// Author: Hannah Bast .
// NOTE: this is a code design suggestion in pseudo-code. It is not supposed to
// be compilable in any language. You have to translate it to Java or C++
// yourself.
// A binary search tree of elements with integer keys and arbitrary values.
//
// Note 1: For simplicity, the keys of different elements in the tree are
// distinct; see also the insert method below.
//
// Note 2: For simplicity, the doubly linked list between the elements of the
// tree can be omitted.
//
// Note 3: *no* measures are taken to balance the tree. Depending on the
// sequence of element insertions and deletions, the tree may therefore be
// balanced or not.
public class BinarySearchTree {
// PUBLIC MEMBERS.
// Create an empty tree.
BinarySearchTree();
// Insert the given element. If an element with that key already exists,
// overwrite its value. Return the node with the (new or old) element.
BinarySearchTreeNode insert(int key, T value);
// Return element with given key. If no such element exists, return the
// element with the smallest key that is larger than the given key. If such an
// element does not exist either, return null.
BinarySearchTreeNode lookup(int key);
// Return the depth of the tree.
int getDepth();
// The tree as a string in human-readable form, for testing and debugging.
String toString();
// PRIVATE MEMBERS.
// Pointer / reference to the root of the tree. This is null, if and only if
// the tree is empty.
BinarySearchTreeNode root;
// The depth of the tree = the largest depth of a node in the tree.
// NOTE: Initialize in the constructor and properly maintain in the insert
// method above. That way, the getDepth method above can be implemented
// trivially and in constant time.
int depth;
};