Data Structure前情提要——二叉树红黑树
前情提要——二叉树
二叉树之前已经提到过，二叉树这种数据结构只能有两个子数，一左一右。
叶子节点就是左右孩子都是空的，但是并不是每一颗树都像上图所示的那样这么规整，有些树树可以只有左孩子没有右孩子的。二叉树的节点一定会大于左节点的值小于右节点的值，每一个节点都要满足，所有每一个节点下面拿出来的树都可以作为一个二叉树。既然有大于等于了，那么这科树的元素一定要有可比较性才可以。
Create a BST
package Tree.BST;
public class BST<E extends Comparable<E>> {
/**
* Binary Search Tree
*/
private class Node {
public E e;
public Node left, right;
public Node(E e) {
this.e = e;
left = right = null;
}
}
private Node root;
private int size;
public BST() {
root = null;
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
}和上面描述的基本一致的。
Insert an element
插入一个元素也很简单，查看当前元素是否是大于或者小于节点元素，如果是大于，那么就右边递归即可，二叉树的插入非递归写法和链表很像。
public void add(E e) {
root = add(root, e);
}
private Node add(Node node, E e) {
if (node == null) {
size++;
return new Node(e);
}
if (e.compareTo(node.e) < 0) {
node.left = add(node.left, e);
} else {
node.right = add(node.right, e);
}
return node;
}Select an element
判断一个元素和查找一个元素算法基本一致，小于左边找，大于右边找即可。 ··· public boolean contains(E e) { return contains(root, e); }
public boolean contains(Node node, E e) {
if (node == null) {
return false;
} else if (e.equals(node.e)) {
return true;
} else if (e.compareTo(node.e) < 0) {
return contains(node.left, e);
} else {
return contains(node.right, e);
}
}···
Traversal
前中后序遍历都很简单，代码和前面C++都都是一样的。对于中序遍历的非递归遍历。非递归遍历可以对比递归来实现，数据结构里面有递归属性的只有栈了，所以可以用栈来实现。先把根元素压进栈，由于前序遍历直接输出第一个遍历到到元素，所以先出栈输出之后再把出栈的元素的子节点压进去，要注意的是右孩子先压，左孩子再压，因为遍历的顺序是先遍历左边再遍历右边，以此类推，只到空为止。 递归处理很简单，几行就好了，主要繁琐到就是非递归遍历到过程，前序遍历的非递归。这个算算比较简单到，因为先遍历到是一开始遍历到到点，再依次是左右子树，没有倒叙过程，都是有顺序性到，所以可以直接用栈处理，先把跟节点扔进去，如果栈不为空，那么就要出栈，直接输出当前元素，在放入左右子树即可，但是放入左右子树需要注意，应当先放入右子树再放入左子树，因为是先遍历左子树再遍历右子树，而栈是反过来的。
public void preOrderNonRecur() {
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
System.out.print(node.e + " ");
if (node.right != null)
stack.push(node.right);
if (node.left != null)
stack.push(node.left);
}
System.out.println();
}这就是前序遍历。中序的非递归遍历就有点复杂了，中序遍历是左中右，这个时候顺序就不是都往下了，没有办法一次性就遍历完，栈里面一开始存储都应该是遍历一开始要拿出来输出都元素，所以可以先把左边子树都遍历完存到栈里面，然后以这些存到栈里面的元素为起点遍历下去。每次出来一个元素都要看看这个元素的右子树是否存在，如果存在就要遍历，但其实不必要这样判断，因为算法前面的大循环已经判断了。
public void inOrderNonRecur() {
Stack<Node> stack = new Stack<>();
Node node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
if (!stack.isEmpty()) {
Node node1 = stack.pop();
System.out.print(node1.e + " ");
node = node1.right;
}
}
System.out.println();对于后序遍历就是最复杂的了，由于后序遍历和前序遍历都是逆的，所以一开始也要先把左子树放到栈里面，出的时候在看看有没有右子树。但是这里有个问题，这里的右子树是先输出再到当前节点的，首先要拿到当前节点，然后再看看右子树有没有，有就遍历，等右子树遍历完之后当前节点还在栈里面，这个时候再拿出来的还是当前节点，这个时候就不知道右子树有没有被遍历过了，这就进入到了一个死循环，所以这里要使用一个标记来看看有没有访问了右子树，如果访问了右子树，就可以放心输出了，因为while循环的时候已经到了最左边的了，这个时候不会再有左子树，只需要考虑右子树即可。
public void lastOrderNonRecur() {
Stack<Node> stack = new Stack<>();
Node node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
if (!stack.isEmpty()) {
Node node1 = stack.peek();
if (!node1.isright) {
node1.isright = true;
node = node1.right;
} else {
node = stack.pop();
System.out.print(node.e + " ");
node = null;
}
}
}
System.out.println();
}中序遍历和后序遍历都从左边扩散到右边。 最后一个就是层序遍历，层序遍历就是广度优先遍历，实现用队列就好了，事实上大多数的广度优先遍历基本都是要使用队列的。之前的数据结构说过，直接给出代码即可：
levelOrder(){
Queue<Node> nodes = new LinkedList<>();
nodes.add(root);
while (!nodes.isEmpty()){
Node node = nodes.remove();
System.out.print(node.e + " ");
if (node.left != null){
nodes.add(node.left);
}
if (node.right != null){
nodes.add(node.right);
}
}
System.out.println();
}红黑树
树的平衡
树的平衡是指树的每一个节点的左右子节点的数目大致一样。两边都相等是最好的，当然这种情况很少见，一般都是两边大致相等。比如在二叉搜索树的时候，如果插入的数字是有顺序的，那么就容易退化成极其不平衡的链表，搜索复杂度就会变成
了。所以对于插入顺序不是平衡的时候，之前所学过的二叉树就不再是一种好的数据结构了。这个时候就要使用红黑树了，红黑树其实也是一种二叉树，只不过是增加了某种特性的二叉树。如果在插入或删除的时候如果出现了不平衡的状态，那么就要进行调整，保持树的平衡。
红黑树的特征
首先每一个节点都有颜色，在删除和添加的过程中是需要保持这些颜色的排列规律。
红黑树的规则
1.每一个节点不是红色就是黑色。 2.根节点总是黑色。 3.如果节点是红色，那么子节点一定是黑色。但是黑色节点下面的子节点可以是红色也可以是黑色。 4.空子节点一定是黑色。对于空子节点而言，本来可能有，但是实际没有的那个字节点就叫做空子节点，比如一个节点只有右子节点，左子节点是没有的，但是左子节点是可以存在的，那么空的这个左子节点就是空子节点。 5.从根到叶节点或者空子节点的没条路径，必须包含相同数目的黑色节点。
红黑树的修正手段也就几种，首先就是改变颜色了，然后就是执行旋转操作。
旋转其实也很容易理解，左旋转的时候，beta这个节点接上了x没有位置放了，所以只能接在x上，右旋转也是一样的意思。所以红黑树的插入算法就需要做出改变，插入的时候前面的步骤是一样的，从根节点向下查找要插入的位置，插入节点之后，后面就需要添加检测树的操作，检测这个树是否是红黑树了，如果不是，那么就要进行修正。一开始插入的这个节点，通常会把它设置成红色，因为这样违法的概率会低一点。 1.如果插入的节点是根节点，那么违法规则2，直接把节点修改成黑色。 2.如果插入的节点父节点是黑色，那么符合，什么都不用做。 3.如果插入的节点的父节点是红色的，而且祖父节点的另一个节点也是红色的，那么就要把祖父节点变红，父节点和叔节点变黑，然后设置祖父节点为当前节点重新开始判断。
这样做的原因其实很简单。首新节点和父节点都是红色，这个时候的常规操作就是要把当前节点变成红色，因为如果节点是黑色的，那么子节点一定要是红色的。但是如果变成黑色的了，那么这边就会多出黑色的一个，这就违法了相同数目的黑色节点的原则了。所以正确的操作应该是要么两边不加，要么两边加，很明显这里只能两边加了，因为添加的节点和父节点是一定要有一个要加的。
4.如果插入的父节点是红色，叔叔节点是黑色，