标题写的是TreeSet，但是在此之前我先需要实现一个红黑树。
为此，这里写一些篇幅实现搜索树。包括二叉搜索树、AVL、红黑树。
每个树都实现增加删除等功能。
这篇先讲二叉搜索树。
二叉搜索树的基本结构就是一颗二叉树。它的特点就是对于一个节点s，它的左子树的所有节点的key都小于s节点的key值，它的右子树的所有节点的key值都大于s的key值。
注意：s节点是任意的，也就是说，对于任意一个节点s都需要满足这个条件。
在实现二叉树中，删除操作是最难的。我也是去网上看了一些人的解释才弄明白一点。我理解到的要点就是：删除一个节点，该节点有以下三种情况：
1）无孩子，是一个叶子节点； 2）只有一个孩子； 3）有两个孩子。
（这里的孩子说的是直接后代，也就是说这个孩子是什么情况不讨论）
然后对于情况1）直接删除就行，需要处理它的父节点；情况2）将它的父节点指向它的孩子；情况3）从他的所有子代中找一个前驱或者后继节点进行替换，然后删除前驱（这个可能会比较难理解）
前驱和后继的概念就是将这颗二叉树用前序遍历进行输出，前驱就是这个节点的直接前面节点，后继就是这个节点的直接后面的节点。（我这里是找他的前驱节点，也就是右子树中最小值）
前驱（右子树（保证比他大）最小值（直接前驱））
后继（左子树（保证比他小）最大值（直接后继））
将该节点指向它的前驱，然后在它的右子树中删除树中最小值。维持二叉搜索树的特点
代码：
public class HBSTree<K extends Comparable<K>, V> {private TreeNode root;private final class TreeNode{private K key;private V val;private TreeNode lChild;private TreeNode rChild;TreeNode(K key, V val){this.key = key;this.val = val;lChild = null;rChild = null;}}HBSTree(){root = null;}public void insert(K key, V val){if(key == null) return ;if(val == null) return ;root = insert(root, key, val);}private TreeNode insert(TreeNode treeNode, K key, V val){if(treeNode == null)treeNode = new TreeNode(key, val);int cmp = key.compareTo(treeNode.key);if (cmp < 0) treeNode.lChild = insert(treeNode.lChild, key, val);else if (cmp > 0) treeNode.rChild = insert(treeNode.rChild, key, val);else treeNode.val = val;return treeNode;}public boolean contains(K key){if(key == null) return false;return get(root, key) != null;}public V get(K key){TreeNode treeNode = get(root, key);if(treeNode == null) return null;return treeNode.val;}private TreeNode get(TreeNode treeNode, K key){if(treeNode == null) return null;int cmp = key.compareTo(treeNode.key);if (cmp < 0) return get(treeNode.lChild, key);else if (cmp > 0) return get(treeNode.rChild, key);else return treeNode;}public K minKey(){if(root == null) return null;return minKey(root).key;}/*** recursive way to implement minKey* private TreeNode minKey(TreeNode treeNode){* if(treeNode.lChild == null) return treeNode;* return minKey(treeNode.lChild);* }*/private TreeNode minKey(TreeNode treeNode){if(treeNode == null) return null;while (treeNode.lChild != null) treeNode = treeNode.lChild;return treeNode;}public K maxKey(){if(root == null) return null;return maxKey(root).key;}/*** recursive to implement maxKey* private TreeNode maxKey(TreeNode treeNode){* if(treeNode.rChild == null) return treeNode;* return maxKey(treeNode.rChild);* }*/private TreeNode maxKey(TreeNode treeNode){if(treeNode == null) return null;while (treeNode.rChild != null) treeNode = treeNode.rChild;return treeNode;}public void deleteMin(){if(root == null) return ;root = deleteMin(root);}private TreeNode deleteMin(TreeNode treeNode){if(treeNode.lChild == null) return treeNode.rChild;treeNode.lChild = deleteMin(treeNode.lChild);return treeNode;}public void deleteMax(){if(root == null) return ;root = deleteMax(root);}private TreeNode deleteMax(TreeNode treeNode){if(treeNode.rChild == null) return treeNode.lChild;treeNode.rChild = deleteMax(treeNode.rChild);return treeNode;}public void remove(K key){if(key == null) return ;root = remove(root, key);}private TreeNode remove(TreeNode treeNode, K key){if(treeNode == null) return null;int cmp = key.compareTo(treeNode.key);if (cmp < 0) return remove(treeNode.lChild, key);else if (cmp > 0) return remove(treeNode.rChild, key);else {if(treeNode.rChild == null) return treeNode.lChild;if(treeNode.lChild == null) return treeNode.rChild;TreeNode node = treeNode;treeNode = minKey(node.rChild);treeNode.rChild = deleteMin(node.rChild);treeNode.lChild = node.lChild;}return treeNode;}
}
最后的最后：代码很多是用递归实现。不得不承认，实现二叉树的某些方法时，的确用递归很方便而且代码简单。但是有些时候最好还是尽力去消除递归。