Binary Search trees

• The property that makes a binary tree into a binary search tree is that for every node, X, in the tree, the values of all the items in its left subtree are smaller than the item in X, and the values of all the items in its right subtree are larger than the item in X
• Because the average depth of a binary search tree turns out to be O(log N), we generally do not need to worry about running out of stack space.
• The binary search tree requires that all the items can be ordered.
• To write a generic class, we need to provide an interface type that represents this property. This interface is Comparable
• The comparable interface tells us that two items in the tree can always be compared using a compareTo method.
• we do not use the equals method. Instead, two items are equal if and only if the compareTo method returns 0
• contains method


  This operation requires returning true if there is a node in tree T that has item X, or false if there is no such node.
• contains method

  If T is empty, then we can just return false. Otherwise, if the item stored at T is X, we can return true. Otherwise, we make a recursive call on a subtree of T, either left or right, depending on the relationship of X to the item stored in T.
• contains method

  It is crucial that the test for an empty tree be performed first, since otherwise, we would generate a NullPointerException attempting to access a data field through a null reference.
• findMin and findMax

  These private routines return a reference to the node containing the smallest and largest elements in the tree, respectively.
• findMin


  start at the root and go left as long as there is a left child. The stopping point is the smallest element.
• findMax


  start at the root and go right as long as there is a right child. The stopping point is the largest element.
• insert 


  proceed down the tree as you would with a contains. If X is found, do nothing (or “update” something). Otherwise, insert X at the last spot on the path traversed
• As is common with many data structures, the hardest operation is .

  deletion
• If the node is a leaf, it can be deleted immediately.
• If the node has one child, the node can be deleted after its parent adjusts a link to bypass the node.
• The complicated case for removals deals with a node with two children. The general strategy is to replace the data of this node with the smallest data of the right subtree and recursively delete that node. Because the smallest node in the right subtree cannot have a left child, the second remove is an easy one.
• If the number of deletions is expected to be small, then a popular strategy to use is lazy deletion: When an element is to be deleted, it is left in the tree and merely marked
• The sum of the depths of all nodes in a tree is known as the internal path length.