本文详细介绍了二叉树的基础概念，包括满二叉树、完全二叉树以及二叉排序树（二叉搜索树）。特别地，深入探讨了AVL树和红黑树这两种自平衡二叉查找树的特性，如平衡因子、插入平衡处理等。在HashMap中，当链表节点超过一定数量时，会转换为红黑树以提高查找效率。文章还展示了HashMap中TreeNode的结构和树化过程，强调了树化过程中如何保持红黑树的性质。
二叉树的基本概念
二叉树
树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
二叉树的子节点分为左节点和右节点。
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。
二叉树的常见概念
- 叶子节点：度为零的结点
- 分支结点：度不为零的结点
- 结点的度：结点拥有的子树的数目
- 层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加
- 树的高度：树中结点的最大层次
二叉树的常见结论：
-
二叉树第k层上的结点数目最多为2k - 1(k >= 1)
-
深度为k的二叉树至多有2^(k) - 1个结点(k>=1)，叶子节点为 2^(k - 1)
-
包含n个结点的二叉树的高度至少为**( log2(n) )+1**
-
在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
二叉排序树/二叉搜索树
二叉排序树（Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
重点结论：二叉排序树的中序遍历是有序的（严格递增）
AVL树
AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
它的特点有：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树(二叉排序树，二叉搜索树)。
红黑树
红黑树，本质上来说是一颗二叉搜索树，下图就是一颗二叉搜索树，即对于每一个父节点，它的左子树的节点的值小于父节点的值，而它的右子树的节点值大于父节点的值
红黑树，就跟它的名字一样，又红又黑，红黑并进，理实交融，节点是非红即黑的，看起来就像这样:
红黑树的主要特性
- 每一个节点的要么是黑色的，要么是红色的
- 根节点是黑色的
- 每一个叶子节点（NIL）是黑色的
- 如果一个节点是红色的，则它的必须是黑色的。（也就是说父子节点不能同时为红色）
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。（这一点是平衡的关键）
TreeNode结构
既然我们已经知道红黑树长什么样了，那么我们再来看看HashMap中的TreeNode代码里是如何表示的：
/**
* 用于Tree bins 的Entry。 扩展LinkedHashMap.Entry（进而扩展Node），因此可以用作常规节点或链接节点的扩展。
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 红黑树父节点
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // 删除后需要取消链接
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
} //省略后续代码
TreeNode继承自LinkedHashMap中的内部类——LinkedHashMap.Entry，而这个内部类又继承自Node，所以算是Node的孙子辈了。我们再来看看它的几个属性，parent用来指向它的父节点，left指向左孩子，right指向右孩子，prev则指向前一个节点（原链表中的前一个节点），注意，这些字段跟Entry，Node中的字段一样，是使用默认访问权限的，所以子类可以直接使用父类的属性。
树化的过程
当HashMap桶中的元素个数超过一定数量(8个)时，就会树化，也就是将链表转化为红黑树的结构。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...省略部分代码...
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//当桶中元素个数超过阈值（8）时就进行树化
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
...省略部分代码...
}
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//将节点替换为TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null) //hd指向头结点
hd = p;
else {
//这里其实是将单链表转化成了双向链表，tl是p的前驱，每次循环更新指向双链表的最后一个元素，用来和p相连，p是当前节点
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
//将链表进行树化
hd.treeify(tab);
}
}
从代码中可以看到，在treeifyBin函数中，先将所有节点替换为TreeNode，然后再将单链表转为双链表，方便之后的遍历和移动操作。而最终的操作，实际上是调用TreeNode的方法treeify进行的。
final void treeify(Node<K,V>[] tab) {
//树的根节点
TreeNode<K,V> root = null;
//x是当前节点，next是后继
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//如果根节点为null，把当前节点设置为根节点
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//这里循环遍历，进行二叉搜索树的插入
for (TreeNode<K,V> p = root;;) {
//p指向遍历中的当前节点，x为待插入节点，k是x的key，h是x的hash值，ph是p的hash值，dir用来指示x节点与p的比较，-1表示比p小，1表示比p大，不存在相等情况，因为HashMap中是不存在两个key完全一致的情况。
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
//如果hash值相等，那么判断k是否实现了comparable接口，如果实现了comparable接口就使用compareTo进行进行比较，如果仍旧相等或者没有实现comparable接口，则在tieBreakOrder中比较
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x; //进行插入平衡处理
root = balanceInsertion(root, x);
break;
}
}
}
} //确保给定节点是桶中的第一个元素
moveRootToFront(tab, root);
}
//这里不是为了整体排序，而是为了在插入中保持一致的顺序
static int tieBreakOrder(Object a, Object b) {
int d;
//用两者的类名进行比较，如果相同则使用对象默认的hashcode进行比较
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
这里的逻辑其实不复杂，仅仅是循环遍历当前树，然后找到可以该节点可以插入的位置，依次和遍历节点比较，比它大则跟其右孩子比较，小则与其左孩子比较，依次遍历，直到找到左孩子或者右孩子为null的位置进行插入。
真正复杂一点的地方在于balanceInsertion函数，这个函数中，将红黑树进行插入平衡处理，保证插入节点后仍保持红黑树的性质。这个函数稍后在TreeNode的插入中进行介绍，这里先看看moveRootToFront，这个函数是将root节点移动到桶中的第一个元素，也就是链表的首节点，这样做是因为在判断桶中元素类型的时候会对链表进行遍历，将根节点移动到链表前端可以确保类型判断时不会出现错误。
/**
* 把给定节点设为桶中的第一个元素
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
//first指向链表第一个节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
//如果root不是第一个节点，则将root放到第一个首节点位置
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
//这里是防御性编程，校验更改后的结构是否满足红黑树和双链表的特性
//因为HashMap并没有做并发安全处理，可能在并发场景中意外破坏了结构
assert checkInvariants(root);
}
}
root.next = first;
root.prev = null;
}
//这里是防御性编程，校验更改后的结构是否满足红黑树和双链表的特性
//因为HashMap并没有做并发安全处理，可能在并发场景中意外破坏了结构
assert checkInvariants(root);
}
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
