Java集合（3）一 红黑树、TreeMap与TreeSet（上）

引言

在系列的第一篇文章中说过Map<K,V>接口与Set<E>接口，Set<E>接口定义了一组不能添加重复元素的集，不能通过索引来访问的集；Map<K,V>接口定义了从键映射到值的一组对象。同时也说过了因为键集不能重复的特性，Map<K,V>的键集由Set<E>来实现。通过查看TreeSet<E>的构造函数，可以看出他是通过TreeMap<K,V>来实现的，只不过仅使用了key。所以在这篇文章中我们会详细讲解TreeMap<K,V>，对TreeSet<E>就不做过多说明。

public TreeSet() {
    this(new TreeMap<E,Object>());
}

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

框架结构

TreeMap<K,V>继承了SortedMap<K,V>接口，SortedMap<K,V>提供了排序功能，通过comparator方法用来对TreeMap里面的每个对象进行比较来达到排序的目的。默认的排序是升序排序，也可以通过构造函数传入比较器Comparator来进行排序。

//SortedMap接口包含的比较方法comparator
public interface SortedMap<K,V> extends Map<K,V> {
    Comparator<? super K> comparator();
}

public interface Comparator<T> {
    int compare(T o1, T o2);

    boolean equals(Object obj);
}
//TreeMap构造函数传入比较器Comparator
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

public Comparator<? super K> comparator() {
    return comparator;
}
//TreeSet构造函数传入比较器Comparator
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

public Comparator<? super E> comparator() {
    return m.comparator();
}

数据结构

TreeMap<K,V>是有序的Map，底层使用了红黑树这种数据结构来实现。红黑树是一种应用非常广泛的树结构，在这里先简单说下红黑树这种数据结构相比较其他树类型结构的优缺点：

1. 红黑树是一种自平衡的二叉查找树，也叫对称二叉B树，红黑树的查找、插入和删除的时间复杂度都为O(logn)，应用非常广泛。
2. 红黑树相对于AVL树（平衡二叉树），牺牲了部分平衡性（红黑树不是完全平衡的二叉树）以换取插入/删除操作时更少的旋转操作，整体在插入/删除的性能上要优于AVL树。所以很多在内存中排序的数据结构都使用红黑树来而不是使用AVL树来存储。
3. 红黑树相对于B-树和B+树，相同节点的情况下红黑树由于深度比B-和B+树要深的多，对IO读写非常频繁，所以适合放在内存中的少量读取，而B-和B+树由于每个节点元素非常之多，访问IO的次数就相对少，适合存储在磁盘中的大量数据，类似数据库记录的存储结构。由于本文篇幅有限，文章中将重点讲述二叉树和红黑树，对AVL树、B-树、B+树不做过多讲解。

二叉排序树

在分析TreeMap<K,V>的源码之前，我们先从二叉排序树说起，因为红黑树也是一颗二叉树，只不过是满足一定条件的二叉树，理解了二叉排序树可以更方便理解红黑树。二叉树排序树是一种非常典型的树结构，通常使用链表做为存储结构（也可以使用数组）。由于树结构每个节点都会存储父子节点的引用，用链表结构更容易表达。如果使用数组来存储，当出现空子节点时对数组空间是一种浪费，同时在查找特定元素时由于数组的元素没有父子节点的引用，只能根据一定规则来遍历，非常不方便，所以大多数情况下都使用链表来存储树结构。二叉树可以通过中序遍历得到一个有序的序列，查找和删除都非常方便，一般情况下时间复杂度为O(logn),最坏O(n)。排序二叉树要么是一颗空树，要么具有以下性质：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。下图是一颗典型的二叉树：

二叉树遍历

二叉树做为一种树结构，遍历的目的是为了依次访问树中所有的节点，并且使每个节点只被访问一遍。他的遍历的方式很多，一般有前中后序和层序遍历四种。中序遍历就是先访问左子树，再访问根节点，最后访问右节点，根据二叉排序树的性质可以知道，通过中序遍历可以得到一个由小到大（默认情况下）的排序序列。所以中序遍历使用的最频繁。下图是中序遍历的图例和代码实现：

public class BinaryTree {
    public void traversalBinaryTree(TreeNode tree) {
		//如果到了叶子节点则退出当前方法，继续向下寻找
		if (tree == null) {
			return;
		}
		//迭代查找左节点，一直到最左边的叶子节点
		traversalBinaryTree(tree.left);
		System.out.println(tree.value);
		//迭代查找右节点，一直到最左边的叶子节点
		traversalBinaryTree(tree.right);
	}

    class TreeNode {
		//节点的值
		int value;
		//左节点
		TreeNode left;
		//右节点
		TreeNode right;
		//父节点
		TreeNode parent;
		
		public TreeNode(int treeValue, TreeNode parentNode) {
			value = treeValue;
			parent = parentNode;
			left = null;
			right = null;
		}
	}
}

前序遍历和后序遍历：

//前序遍历
System.out.println(tree.value);
traversalBinaryTree(tree.left);
traversalBinaryTree(tree.right);
//后序遍历
traversalBinaryTree(tree.left);
traversalBinaryTree(tree.right);
System.out.println(tree.value);

二叉树添加

明白了二叉树的遍历，理解二叉树的添加就非常简单，通过中序遍历从小到大查找到要添加值的空叶子节点为止，我们来实现一个二叉树的添加方法：

public void addBinaryTreeNode(int value) {
    //根节点
    TreeNode tree = root;
    if (tree == null) {
        //根节点为空则新建一个跟节点
        root = new TreeNode(value, null);
        return;
    }
    //用来存储新节点的父节点
    TreeNode parentNode;
    do {
        //使用上次循环后的节点做为引用
        parentNode = tree;
        //如果新插入的 value 小于当前value，则向左边查找
        if (value < tree.value) {
            tree = tree.left;
        //如果新插入的 value 大于当前value，则向右边查找
        } else if (value > tree.value) {
            tree = tree.right;
        //如果相等则证明有相同节点，不添加
        } else {
            return;
        }
    } while (tree != null);
    //新建节点，parentNode为新节点的父节点
    TreeNode node = new TreeNode(value, parentNode);
    //新节点为左节点或者右节点
    if (value < parentNode.value) {
        parentNode.left = node;
    } else {
        parentNode.right = node;
    }	
}

public static void main(String[] args) {

    BinaryTree binaryTree = new BinaryTree();

    binaryTree.addBinaryTreeNode(10);
    binaryTree.addBinaryTreeNode(5);
    binaryTree.addBinaryTreeNode(20);
    binaryTree.addBinaryTreeNode(7);
    binaryTree.addBinaryTreeNode(6);
    binaryTree.addBinaryTreeNode(3);
    binaryTree.addBinaryTreeNode(15);
    binaryTree.addBinaryTreeNode(30);

    binaryTree.traversalBinaryTree(binaryTree.root);
}

//	Console:
//	3
//	5
//	6
//	7
//	10
//	15
//	20
//	30

通过上面二叉树添加节点的逻辑，我们再来分析TreeMap<K,V>源码中添加节点的实现。TreeMap<K,V>通过put(K key, V value)方法将key和value放在一个Entry<K,V>节点中，Entry<K,V>相当于上面代码中的Node节点。

public V put(K key, V value) {
    //根节点
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        //根节点为空则新建一个跟节点
        root = new Entry<>(key, value, null);
        //记录Map元素的数量
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    //如果comparator不为空则代表使用定制的比较器进行排序
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            //如果新插入的key小于当前key，则向左边查找
            if (cmp < 0)
                t = t.left;
            //如果新插入的key大于当前key，则向右边查找
            else if (cmp > 0)
                t = t.right;
            //相等则覆盖
            else
                return t.setValue(value);
        } while (t != null);
    }
    //如果comparator为空则使用默认比较器进行排序
    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);
    }
    //通过上面查找到插入节点的父节点parent并初始化新节点Entry<K,V>
    Entry<K,V> e = new Entry<>(key, value, parent);
    //如果新插入的key小于父节点的key，则将插入节点作为父节点的左孩子
    if (cmp < 0)
        parent.left = e;
    //如果新插入的key大于父节点的key，则将插入节点作为父节点的右孩子
    else
        parent.right = e;
    //重点：修复红黑树（后面会说）
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

二叉树删除

二叉树的删除相比添加复杂一些，因为如果删除的节点不是叶子节点，需要考虑由那个节点来替代当前节点的位置。删除可以分6种情况：

1. 删除的节点没有左右子节点，并且没有父节点，则为根节点，直接删除即可；
2. 删除的节点没有左右子节点，有父节点，是为叶子节点，直接删除即可；
3. 删除的节点是根节点，有左节点或右节点，用左节点或者右节点替换被删除的根节点；
4. 删除的节点不是根节点，只有左节点，用左节点替换被删除的节点；
5. 删除的节点不是根节点，只有右节点，用右节点替换被删除的节点；
6. 删除的节点有左右子节点，用删除节点的直接后继节点替换被删除的节点的值，然后删除直接后继节点，情况转换为2、4或者5。

下面按照二叉树删除的6种情况我们来实现一个二叉树的删除算法：

public void removeBinaryTreeNode(int value) {
    // 根节点
    TreeNode tree = root;
    if (tree == null) {
        return;
    }
    TreeNode currentNode = findBinaryTreeNode(value);
    if (currentNode == null) {
        return;
    }
    
    if (currentNode.left == null && currentNode.right == null) {
        //情况一 删除根节点，并且没有左右子节点
        if (currentNode.parent == null) {
            root = null;
        } else {
            //情况二 删除叶子节点
            if (currentNode.parent.left == currentNode) {
                currentNode.parent.left = null;
            } else {
                currentNode.parent.right = null;
            }
            currentNode.parent = null;
        }
    } else if (currentNode.left == null || currentNode.right == null) {
        TreeNode replaceNode = currentNode.left == null ? currentNode.right : currentNode.left;
        replaceNode.parent = currentNode.parent;
        //情况三 删除根节点 并且只有一个子节点
        if (currentNode.parent == null) {
            root = replaceNode;
        //情况四 不是根节点 只有左节点
        } else if (currentNode == currentNode.parent.left) {
            currentNode.parent.left = replaceNode;
        //情况五 不是根节点 只有右节点
        } else {
            currentNode.parent.right = replaceNode;
        }
        currentNode.parent = currentNode.left = currentNode.right = null;
    }  else {
        //情况六 同时有左右节点
        //successorNode 需要删除节点的后继节点
        TreeNode successorNode = currentNode.right;
        TreeNode parentNode;
        //查找后继节点
        do {
            parentNode =  successorNode;
            successorNode = successorNode.left;
        } while (successorNode != null);
        successorNode = parentNode;
        //覆盖需要删除的节点的值为后继节点的值
        currentNode.value = successorNode.value;
        //后继节点的左节点一定为空，如果不为空则说明当前节点不是后继节点
        if (successorNode.right != null) {
            //关联后继节点的右节点和后继节点的父节点
            TreeNode replaceNode = successorNode.right;
            replaceNode.parent = successorNode.parent;
            if (successorNode.parent.left == successorNode) {
                successorNode.parent.left = replaceNode;
            }
            if (successorNode.parent.right == successorNode) {
                successorNode.parent.right = replaceNode;
            }
        }
        //删除后继节点
        successorNode.parent = successorNode.left = successorNode.right = null;
    }
}
//查找当前值所对应的树节点
public TreeNode findBinaryTreeNode(int value) {
    // 根节点
    TreeNode tree = root;
    if (tree == null) {
        return null;
    }
    // 用来存储新节点的父节点
    TreeNode parentNode;
    do {
        // 循环迭代从小到大查找直到叶子为空
        parentNode = tree;
        if (value < tree.value) {
            tree = tree.left;
        } else if (value > tree.value) {
            tree = tree.right;
        } else {
            return parentNode;
        }
    } while (tree != null);
    return null;
}

通过上面二叉树删除节点的逻辑，再来分析TreeMap<K,V>源码中删除节点的实现。TreeMap<K,V>通过remove(Object key)来删除key所代表的节点，先通过getEntry(key)查找到需要删除的节点Entry<K,V> p，然后通过deleteEntry(Entry<K,V> p)删除p节点。

public V remove(Object key) {
    //查找到key所代表的节点p
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    //如果被删除的节点左右孩子都不为空，则查找到P的直接后继节点，用后继节点的键和值覆盖P的键和值，然后删除后继节点即可（实际上是情况六）
    //这一步非常巧妙，将要删除的节点转换为要删除节点的直接后继节点，情况六转换为情况二，四，五
    if (p.left != null && p.right != null) {
        //查找到P的直接后继节点
        Entry<K,V> s = successor(p);
        //后继节点覆盖键和值到P
        p.key = s.key;
        p.value = s.value;
        //将要删除的节点变为P的后继节点，删除后继节点即可
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    //查找用来替换的节点
    //经过上面的步骤，如果P存在左节点，则不存在右节点，直接用左节点替换即可。因为如果左右节点都存在，则会查找到后继（后继节点的左节点一定为空）。
    //如果P左节点不存在，存在右节点，则直接用右节点来替换即可。
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    //通过上面的步骤说明左右节点只可能同时存在一个，replacement为左右子节点当中的任何一个
    if (replacement != null) {
        // Link replacement to parent
        //p节点将要删除，将用来替换的节点的父节点指向p的父节点
        replacement.parent = p.parent;
        //p的父节点为空，则说明删除的是根节点（情况三）
        if (p.parent == null)
            root = replacement;
        //replacement替换为左节点（情况四）
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        //replacement替换为右节点（情况五）
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        //删除P节点
        p.left = p.right = p.parent = null;

        // Fix replacement
        //重点：修复红黑树（后面会说）
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    //如果替换的节点为空，p的父节点也为空则为根节点，直接删除即可（情况一）
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    //如果替换的节点为空，p的父节点不为空，说明为叶子节点（情况二）
    } else { //  No children. Use self as phantom replacement and unlink.
        //重点：修复红黑树（后面会说）
        if (p.color == BLACK)
            fixAfterDeletion(p);
        //删除叶子节点和父节点的关联
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}
//查找t节点的直接后继节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

总结

在这篇文章中我们自己实现了二叉树的遍历、添加节点以及删除节点的操作逻辑，然后详解了TreeMap<K,V>中关于节点删除和添加的逻辑，略过了红黑树的操作。看完后相信大家对二叉树的基本操作有了一定了解，下一篇文章中将详细讲解TreeMap<K,V>中对满足红黑树性质所进行的操作。