前言
Set接口是继承与Collection的，而Map是独立的一个接口。
其中Set的实现类有：
- TreeSet
- HashSet
Map实现的类有：
- HashMap
- TreeMap
（HashSet和HashMap底层是一个哈希表，TreeSet和TreeMap底层是一棵搜索树（红黑树））
TreeMap和TreeSet，即java中利用搜索树实现的Map和Set，实际上应用的就是红黑树，而红黑树是一棵近似平衡的二叉搜索树（在二叉搜索树的基础上+上颜色以及红黑树性质的验证）
搜索树
定义树：
public class BinarySearchTree { static class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; } } public TreeNode root = null; }
概念
二叉搜索树，也被称为二叉排序树（可能为一棵空树），具备以下性质：
- 若它的左子树不为空，则左子树上所有的节点的值，都小于根节点的值
- 若它的右子树不为空，则右子树上所有的节点的值，都大于根节点的值
- 它的左右子树也分别为二叉搜索树
二叉搜索树
中序遍历二叉搜索树，得到的结果是一组有序的数据。
查找
如上图，首先假设上图的二叉树已经存在，且根节点为root，要查找的值为val，如果root为空就返回null，定义一个cur节点来遍历这棵树，如果root.val > val，根据二叉搜索树的性质，就去root结点的左子树去找，否则就去右子树找，如果找到了（cur.val == val），就然后cur结点，直到cur == null，就返回空的结点。
/** * 查找二叉搜索树val的值 * val * */ public TreeNode find(int val) { TreeNode cur = root; while (cur != null) { if (cur.val == val) { return cur; } else if (cur.val < val) { cur = cur.right; } else { cur = cur.left; } } return null; }
插入
搜索树满足概念中性质a,b,c三点，如果要插入一个val。值首先定义一个cur节点，如果root == null就 new一个 值为val的节点newNode，并将root置为这个节点（root == newNode）
如果root != null，就进行搜索，如果root.val > val，就去左边继续搜索，如果root.val < val就去右边搜索。如果当前cur结点的左和右都为null，则直接比较插入即可。
例如在上图中插入6，12 > 6，就去12的左树插入，12的左树的根值为5 < 6，所以去5这个节点的右树插入，其右树跟为9 > 6，又因为val为9这个结点的左和右都为null。所以直接在这个结点的左侧插入。
// 不使用parent结点 public void insert1(int val) { if (root == null) { root = new TreeNode(val); return; } TreeNode newNode = new TreeNode(val); TreeNode cur = root; while (cur.left != null && cur.right != null) { if (newNode.val > cur.val) { cur =cur.right; }else { cur =cur.left; } } if (newNode.val > cur.val) { cur.right = newNode; }else { cur.left = newNode; } }
当然也可以使用parent结点来记录cur的上一个结点，如果cur == null的时候，就可以找到cur的上一个结点parent，并在parent这个结点上插入。
public void insert2(int val) { if (root == null) { root = new TreeNode(val); return; } TreeNode newNode = new TreeNode(val); TreeNode cur = root; TreeNode parent = null; while (cur != null) { parent = cur; if (cur.val < val) { cur =cur.right; }else { cur = cur.left; } } if (parent.val < val) { parent.right = newNode; }else { parent.left = newNode; } }
删除
二叉搜索树
如何删除
设cur节点为当前要删除的节点，parent为cur结点的父节点。
- 如果 cur.left == null。
a.cur == root && root.left == null ，则root = cur.right。
b.cur != root && cur == parent.left ，则 parent.left = cur.right
c.cur != root && cur == parent.right，则 parent.right = cur.right
- 如果cur.right == null，则原理同上。
- cur == root，则root = root.left
- cur != root && cur == parent.left，则 parent.left = cur.left
- cur != root && cur == parent.right，则 prent.right = cur.left
图略
- cur.left != null && cur.right != null。
某个二叉搜索树
假设有这样一棵二叉搜索树。root为根节点，cur为当前将要被删除的节点。
该如何删除？
需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(值最小)，用它的值填补到被
删除节点中，再删除这个最小值节点即可。
首先，你需要找出cur节点和cur的父节点：
实现
public void remove(int val) { TreeNode cur = root; TreeNode parent = null; while(cur != null){ if (cur.val == val) { removeNode(parent, cur); break; }else if (cur.val > val) { parent = cur; cur = cur.left; }else { parent = cur; cur = cur.right; } } }
然后需要在cur的右树里面找到其最小值，这个最小值无非就是cur的右子树的第一个结点，或者是右子树上左树的最左的一个端点。找到这个节点之后，将其删除。
然后综上所述的cur.left == null 或者 cur.right == null的情况来完成removeNode这个方法；
private void removeNode(TreeNode parent, TreeNode cur) { // 要删除的节点的左子树为空 if (cur.left == null) { if (cur == root) { root = cur.right; }else if (parent.left == cur) { parent.left = cur.right; }else { parent.right = cur.right; } // 要删除的节点的右子树为空 }else if (cur.right == null) { if (cur == root) { root = cur.left; }else if (parent.left == cur) { parent.left = cur.left; }else { parent.right = cur.left; } }else/* suggests that:cur.left != null && cur.right != null */ { TreeNode target = cur.right; TreeNode targetParent = cur; while (target.left != null) { targetParent = target; target = target.left; } cur.val = target.val; if (target == targetParent.left) { targetParent.left = target.right; }else { targetParent.right = target.right; } } }
性能分析
无论是插入，还是删除操作，都需要先查找，所以查找的速度代表了二叉搜索树中各个操作的性能。查找是根据节点的值比较来的，所以树越趋向于平衡（完全二叉树或者满二叉树），查找的次数就越趋向于树的深度，否则则会趋向于节点的个数，例如单分支的二叉搜索树：他的搜索时间复杂度为O(n)
完全二叉树
单分支二叉树（右单支）
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为： 
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2
数据结构-Java Map 和 Set-2
