转载请标明出处，谢谢！
https://www.jianshu.com/p/de829eab944c
关联文章
冒泡、选择排序 https://www.jianshu.com/p/176b0b892591
栈和队列 https://www.jianshu.com/p/8cb602ef4e21
顺序表、单双链表 https://www.jianshu.com/p/3aeb5998e79e
二叉树 https://www.jianshu.com/p/de829eab944c
图论 https://www.jianshu.com/p/cf03e51a3ca2
二叉树
二叉树的定义及其基本性质
二叉树（Binary Tree）是n(n≥0)个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交、分别称为左子树和右子树的子二叉树构成，二叉树也是递归定义的，在树种定义的度、层次等术语，同样适用于二叉树。
二叉树的5种表现
image
**满二叉树和完全二叉树 **
一棵高度为h的满二叉树（Full Binary Tree）是具有2h−1(h≥0)2h−1(h≥0)个结点的二叉树。满二叉树的最大特点是每一层次的结点数都达到最大值，我们可以对满二叉树的结点进行连续编号并约定根结点的序号为0，从根结点开始，自上而下，每层自左向右编号。如下图所示（a）：
image
原文：https://blog.csdn.net/javazejian/article/details/53727333
对于二叉树的详细信息，转至原文 ：java数据结构与算法之双链表设计与实现
二叉树的排序
/**
* 前序遍历
* @param root
*/
public void preOrderTree(Node root) {
if (root == null) {
return;
}
System.out.println("pre = " + root.toString());
preOrderTree(root.left);
preOrderTree(root.right);
}
/**
* 中序遍历
* @param root
*/
public void inOrderTree(Node root) {
if (root == null) {
return;
}
inOrderTree(root.left);
System.out.println("in = " + root.toString());
inOrderTree(root.right);
}
/**
* 后序遍历
* @param root
*/
public void postOrderTree(Node root) {
if (root == null) {
return;
}
postOrderTree(root.left);
postOrderTree(root.right);
System.out.println("post = " + root.toString());
}
二叉排序树 (二叉搜索树)
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
创建一个结点类
public class BinaryNode<T extends Comparable> implements Serializable {
private static final long serialVersionUID = -6477238039299912313L;
public BinaryNode<T> left;//左结点
public BinaryNode<T> right;//右结点
public T data;
public BinaryNode(T data,BinaryNode left,BinaryNode right){
this.data=data;
this.left=left;
this.right=right;
}
public BinaryNode(T data){
this(data,null,null);
}
}
二叉排序树的插入
事实上对于二叉查找树的插入操作的设计是比较简单，我们只要利用二叉查找树的特性（即对每个父结点，它的左子树中所有项的值小T中的值，而它的右子树中所有项的值都大于T中的值），找到只对应的插入位置即可，假如现在我们要插入data=4的结点，那么可以这样操作，沿着树查找(比较结点的数据与data的大小从而决定往左/右子树继续前行)，如果找到data(4),则什么也不做，否则将data插入到遍历的路径上的最后一个点，如下图所示：
image
/**
* 添加结点
*
* @param value
* @param t
* @return
*/
private BinaryNode<T> insert(T value, BinaryNode<T> t) {
if (t == null) {
/*root结点*/
return new BinaryNode<>(value);
}
int result = value.compareTo(t.data);
if (result < 0) {
/*如果插入的数据小于父节点的值则插入左边*/
t.left = insert(value, t.left);
} else if (result > 0) {
/*如果插入的数据大于父节点的值则插入右边*/
t.right = insert(value, t.right);
} else {
/*反之如果相等就直接返回*/
return t;
}
return t;
}
打印数据：中序遍历可以从小到大排序（左根右）
/**
* 中序遍历打印
*/
private void printTree() {
printTree(root);
}
private void printTree(BinaryNode<T> t) {
if (t != null) {
printTree(t.left);
System.out.print(t.data + "---");
printTree(t.right);
}
}
测试一下
@Test
public void test() {
BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
binarySearchTree.insert(7);
binarySearchTree.insert(2);
binarySearchTree.insert(9);
binarySearchTree.insert(1);
binarySearchTree.insert(5);
binarySearchTree.insert(8);
binarySearchTree.insert(6);
binarySearchTree.insert(3);
binarySearchTree.insert(4);
binarySearchTree.printTree();
}
image.png
二叉排序树删除
对于二叉树来说，删除是一种比较麻烦的操作，因为涉及到了多种情况
① 如果要删除的结点q恰好是叶子结点，那么它可以立即被删除
② 如果要删除的结点q拥有一个孩子结点，则应该调整要被删除的父结点(p.left 或 p.right)指向被删除结点的孩子结点（q.left 或 q.right）
③ 如果要删除的结点q拥有两个孩子结点，则删除策略是用q的右子树的最小的数据替代要被删除结点的数据，并递归删除用于替换的结点(此时该结点已为空)，此时二叉查找树的结构并不会被打乱，其特性仍旧生效。采用这样策略的主要原因是右子树的最小结点的数据替换要被删除的结点后可以满足维持二叉查找树的结构和特性，又因为右子树最小结点不可能有左孩子，删除起来也相对简单些。
image
原文：https://blog.csdn.net/javazejian/article/details/53727333
/**
* 删除结点
*
* @param value
* @param t
* @private
*/
private BinaryNode<T> remove(T value, BinaryNode<T> t) {
if (t == null) {
return t;
}
int result = value.compareTo(t.data);
if (result < 0) {
/*在左子树中执行删除*/
t.left = remove(value, t.left);
} else if (result > 0) {
/*在右子树中执行删除*/
t.right = remove(value, t.right);
} else if (t.left != null && t.right != null) {
/*找到右子树中最小的元素并替换需要删除的元素值*/
t.data = findMin(t.right).data;
/*将右子树的最小值删除*/
t.right = remove(t.data, t.right);
} else {
/*如果被删除节点是一个叶子 或只有一个儿子*/
t = t.left != null ? t.left : t.right;
}
return t;
}
查找树中的最大和最小的值：树中的最左边的结点值就是最小值，最右边的结点值就是最大值
/**
* 查找树中最小的结点
*
* @param root
* @return
*/
private BinaryNode<T> findMin(BinaryNode<T> root) {
if (root == null) {
return null;
} else if (root.left == null) {
return root;
}
return findMin(root.left);
}
/**
* 查找树中最大的结点
*
* @param root
* @return
*/
private BinaryNode<T> findMax(BinaryNode<T> root) {
if (root == null) {
return null;
} else if (root.right == null) {
return root;
}
return findMax(root.right);
}
测试：
@Test
public void test() {
BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
binarySearchTree.insert(7);
binarySearchTree.insert(2);
binarySearchTree.insert(9);
binarySearchTree.insert(1);
binarySearchTree.insert(5);
binarySearchTree.insert(8);
binarySearchTree.insert(6);
binarySearchTree.insert(3);
binarySearchTree.insert(4);
binarySearchTree.remove(2);
binarySearchTree.printTree();
if (binarySearchTree.find(6)) {
System.out.println("\n查找到数据6");
} else {
System.out.println("\n查找不到数据6");
}
System.out.println("\n最大数据"+binarySearchTree.findMax(binarySearchTree.root)
.data.toString());
System.out.println("\n最小数据"+binarySearchTree.findMin(binarySearchTree.root)
.data.toString());
}
image.png
AVL树
AVL树又称为高度平衡的二叉搜索树，一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二叉查找树(空树的高度为-1)，
用一张图说明下 原文：https://blog.csdn.net/javazejian/article/details/52953190
image
平衡二叉树的单旋转算法与实现
从图3和图4可知，在原始AVL树插入7结点后，结点9变为失衡点，树再满足AVL性质，因此需要对9结点进行左左单旋转(即向右旋转)后，得到图4，我们发现此时并没有操作树的根结点(6)，实际上这是因为正常情况下，不必从树的根结点进行旋转，而是从插入结点处开始，向上遍历树，并更新和修复在这个路径上的每个结点的平衡及其平衡信息(高度)即可。
image
/**
* 左左单旋转(LL旋转及右旋转) w变为x的根结点, x变为w的右子树
*
* @param x
* @return
*/
private AVLNode<T> singleRotateRight(AVLNode<T> x) {
//把w结点旋转为根结点
AVLNode<T> w = x.left;
//同时w的右子树变为x的左子树
x.left = w.right;
//x变为w的右子树
w.right = x;
//重新计算x/w的高度
x.height = Math.max(height(x.left), height(x.right)) + 1;
w.height = Math.max(height(w.left), x.height) + 1;
return w;//返回新的根结点
}
右右单旋转(RR)情景④分析
接着再来看看右右单旋转(RR)的情景，如下图，可以发现与左左单旋转的情况恰好是一种镜像关系，同样结点X并不能满足AVL树的性质，在这样的情景下，需要对X结点进行左旋转来修复树的平衡，如图1经左旋转后变了图2，此时X变为了根结点，W变为X的左孩子，X的左子树变为W的右子树，而树又重新恢复了平衡。如图3和图4的实例情景，原始的AVL树在12处插入结点18后，结点10就变成了失衡点，因为10的左子树和右子树的高度相差2，显然不符合AVL树性质，需要对结点10进行右右单旋转修复(向左旋转)，然后得到图4，此时树重新回到了平衡，这便是右右单旋转(RR)的修复情景。
image
/**
* 右右单旋转(RR旋转左旋转) x变为w的根结点, w变为x的左子树
*
* @return
*/
private AVLNode<T> singleRotateLeft(AVLNode<T> w) {
AVLNode<T> x = w.right;
w.right = x.left;
x.left = w;
//重新计算x/w的高度
x.height = Math.max(height(x.left), w.height) + 1;
w.height = Math.max(height(w.left), height(w.right)) + 1;
//返回新的根结点
return x;
}
平衡二叉树的双旋转算法与实现
image
在左右双旋转实例图123中，在原AVL树种插入结点7后，结点8变成了失衡点，此时需要把6结点变为根结点才能重新恢复平衡。因此先进行左向旋转再进行右向旋转，最后树恢复平衡。算法代码实现如下：
/**
* 左右旋转(LR旋转) x(根) w y 结点 把y变成根结点
*
* @return
*/
private AVLNode<T> doubleRotateWithLeft(AVLNode<T> x) {
//w先进行RR旋转
x.left = singleRotateRight(x.left);
//再进行x的LL旋转
return singleRotateLeft(x);
}
右左双旋转(RL)情景③分析
对于右左双旋转(RL)情景和左右双旋转(LR)情景是一对镜像，旋转的原理上一样的，这里就不废话了，给出下图协助理解即可(已很清晰了)：
image
/**
* 右左旋转(RL旋转)
*
* @param w
* @return
*/
private AVLNode<T> doubleRotateWithRight(AVLNode<T> w) {
//先进行LL旋转
w.right = singleRotateLeft(w.right);
//再进行RR旋转
return singleRotateRight(w);
}
红黑树
红黑树顾名思义就是结点是红色或者是黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树而言我们必须增加如下规则，这也是红黑树最重要的5点规则：
1、每个结点都只能是红色或者黑色中的一种。
2、根结点是黑色的。
3、每个叶结点（NIL节点，空节点）是黑色的。
4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
这里我们通过分析TreeMap的源码先分析一下 红黑树的插入：
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
*
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
public V put(K key, V value) {
TreeMapEntry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new TreeMapEntry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
TreeMapEntry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
这里我们看到，红黑树实际上就是一颗二叉排序树因此他的插入也是遵循了二叉排序树的规则，及比父节点小的结点插入其左边，反之插入右边。
我们重点看下fixAfterInsertion(e)的方法，该方法顾名思义是调整树的结点位置和颜色等从而使其遵循红黑树的规则：
/** From CLR */
private void fixAfterInsertion(TreeMapEntry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
我们根据插入的规则一行行分析代码
image
1.首先插入的结点必须是按照二叉排序树的方式插入，这一点我们前面已经分析过了。且插入的结点是红色的（代码一开始就将插入的点x置为红色了）
2.插入的是根节点直接土黑：代码最后2351我们将root结点的颜色设置了黑色。
3.如果插入的节点的父节点是黑色的无须调整
4.如果插入的节点的父节点是红色的(重点来了):
我们一点一点的分析：
image.png
如果父节点是祖父节点的左孩子
情况1：祖父节点的另一个子节点（叔叔节点）是红色
对策： 将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点开始算法
分析：这个东西确实比较绕口，我们简单理解：如果插入的节点，它的父节点是它父节点的父节点的左孩子，那么它的父节点的父节点的右孩子以及它的父节点涂黑等等。。。（因为它的父节点是左边，它父节点的兄弟节点也就是右边=）。好吧，感觉越说越乱了，还是很难理解啊，我们直接上源码把！
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
}
我们看源码的第一个if条件
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
这个就很好理解了，其中parentOf(parentOf(x))表示的就是它父节点的祖父节点（父节点的父节点）
接下去
TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));
其中rightOf(parentOf(parentOf(x)));表示的就是父节点的兄弟节点
我们看第二个if条件其实就是满足了上面的情况1:
情况1：祖父节点的另一个子节点（叔叔节点）是红色
对策： 将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点开始算法
继续分析：
image.png
情况2：如果叔叔节点是黑色的又分为了两种情况
情况2.1 当前节点是其父节点的右孩子
对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。
image.png
从左边的图中我们可以看到 当前节点是7 是2节点的右孩子，那么当前节点的父节点2作为新的当前节点，然后左旋，得到了右图。我们看下代码：
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
很奇怪为什么这里并没有else呢？
不急，我们紧接着看情况2
情况2.2：当前节点是其父节点的左孩子
对策：父节点变为黑色，祖父节点变红色，再祖父节点为支点进行右旋
image.png
左图是情况1变换后的图片
当前节点2现在已经变成了其父节点的左孩子，满足条件2。所以相对应的策略是
父节点7变为黑色，祖父节点11变红色，再由祖父节点为支点进行右旋，变成了右图。代码：
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
所以情况1和2 的统一代码就是
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
以上，我们就分析完了父节点是祖父节点的左孩子
那么父节点是祖父节点的右孩子就是上面情况的反情况而已
image.png
同样的，删除也有它的一些规则。这里先不做分析。
image.png
网友评论