HashMap之TreeNode
HashMap之TreeNode
##简述
在分析HashMap之前先说⼀下内部类TreeNode。TreeNode类是⼀颗红⿊树的各种操作。当然TreeNode不只是简单的红⿊树操作，还有与HashMap业务相关的代码
先看⼀下类的继承关系
Entry是⼀个接⼝，主要有⼀些让⼦类去实现的get、set⽅法
Node是⼀个单向链表
最后就是TreeNode红⿊树了
先看⼀下简单的Node单向链表，然后再看复杂⼀点的TreeNode
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
< = next;
}
public final K getKey()        { return key; }
public final V getValue()      { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
很简单，⼀个Node相当于链表的⼀个节点，next属性对应着下⼀个节点
TreeNode
TreeNode也是，⼀个TreeNode代表红⿊树的⼀个节点
红⿊树是在⼆叉查树基础上，对每⼀个节点添加⼀个颜⾊属性形成的，同时整个红⿊⼆叉树需要同时满⾜⼀下五条性质
1. 每个节点或是红⾊，或是⿊⾊的
2. 跟节点是⿊⾊的
3. 每个叶节点（NIL）是⿊⾊的
4. 如果⼀个节点是红⾊的，则它的两个⼦节点都是⿊⾊的
5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数码的⿊节点
如图
叶节点（NIL）不包含任何数据，只是⼀个标记，没有实际意义
下⾯通过红⿊树的插⼊、删除、查、左旋、右旋进⼀步了解TreeNode
先看⼀下构造
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
可以看到调⽤了⽗类的构造⽅法，也就是说，TreeNode是红⿊树的同时也是⼀个单项链表
##旋转
先说⼀下左旋和右旋操作
添加和删除操作肯能会违反红⿊树的的性质，⽽保持红⿊树的性质是通过旋转来操作的
如添加了⼀个红节点N就违反了性质4，在通过2个动图看⼀下是怎么旋转的
左旋
右旋
以上⾯的静态图来说明右旋操作，左旋⼀样，只是操作是相反的
上图添加了节点N违反性质4，右旋G节点：
使P成为根节点并变成⿊⾊满⾜性质2
G成为P的右节点
P的右节点成为G的左节点
1 static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
2                                        TreeNode<K,V> p) {
3    TreeNode<K,V> l, pp, lr;
4    if (p != null && (l = p.left) != null) {
5        if ((lr = p.left = l.right) != null)
6            lr.parent = p;
7        if ((pp = l.parent = p.parent) == null)
8            (root = l).red = false;
9        else if (pp.right == p)
10            pp.right = l;
11        else
12            pp.left = l;
13        l.right = p;
14        p.parent = l;
15    }
16    return root;
17 }
equals不等于代码虽然不多，但是有点乱，我们⼀点⼀点的分析。我们假设传⼊的参数roo是G节点，p也是G节点
参数root是根节点，p是被旋转的节点
变量l是p的左节点、pp是p的⽗节点、lr是l右节点
第4⾏判断p不等于null并把左节点赋值给l，如果l为null的话就不能右旋了
第5⾏是完成上⾯性质c，并把值赋值给lr
第7⾏把p的⽗节点赋值给l的⽗节点，并把值赋值给pp，因为我们传⼊的参数G没有⽗节点，所以pp为null，为了满⾜红⿊树的性质2，把颜⾊设置成⿊⾊
第9⾏和第11⾏，是判断p是左节点还是右节点，如果是右节点则吧⽗节点的右节点设置成l，反之亦然
第13⾏设置l的右节点为p，也就是P的右节点设置成G
第14⾏设置p的⽗节点为l，也就是设置G的⽗节点为P
##查
从当前节点查指定节点，根据参数h判断是从左边还是右边查

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。