源码分析[4] HashMap之红黑树
About 6 min
二叉搜索树BST
先介绍一下二叉搜索树. 之后再引出红黑树.
BST的特点
- 当前节点的左子节点小于当前节点.
- 当前节点的右子节点大于当前节点.
缺陷
我们先计算一下理想情况下的BST的时间复杂度. 对于节点数为n的二叉树, 其深度m满足:
< n <=
如果遍历一个节点的时间花费为O(1), 那么遍历到我们想要的节点就大约需要: O(log_2n)
性能还是不错的.
但是当二叉树倾斜后时间复杂度将变为O(n), 此时的查找为链表查找, 每次都会寻址, 查询效率大大降低.
下面是我写的一段BST实现的代码:
package com.nikola.treetest.tree;
import java.util.Objects;
import lombok.Data;
import lombok.ToString;
import lombok.extern.slf4j.Slf4j;
/**
* 二叉树的实现
*
* @author nikolazhang
*/
@Slf4j
public class BST {
public static void main(final String[] args) {
final BST bst = new BST();
final Node<Integer> head = bst.new Node<>(7);
head.addChild(2);
head.addChild(6);
head.addChild(7);
head.addChild(9);
head.addChild(10);
head.addChild(11);
head.addChild(12);
head.addChild(13);
head.addChild(14);
head.addChild(15);
head.addChild(16);
log.debug("输出信息为: {}", head);
}
@Data
@ToString(exclude = "parent")
public class Node<T extends Comparable<T>> {
private T data;
private Node<T> left;
private Node<T> right;
private Node<T> parent;
public Node(final T t) {
this.data = Objects.requireNonNull(t);
}
/**
* 向二叉树中添加节点
*
* @param t 将要放入二叉树中的值
*/
public void addChild(final T t) {
// 创建一个新节点
final Node<T> child = new Node<>(Objects.requireNonNull(t));
// 遍历当前节点信息并比较两个节点
Node<T> e;
int res;
for (e = this; e != null;) {
// 比较当前节点和新节点, 如果新节点小于等于当前节点则添加到左子树, 否则添加到右子树
if ((res = e.compareTo(child)) < 0) {
if (e.left == null) {
e.left = child;
child.setParent(e);
break;
} else {
e = e.left;
}
} else if (res == 0) {
log.debug("和当前节点数值相同, 不做处理");
break;
} else {
if (e.right == null) {
e.right = child;
child.setParent(e);
break;
} else {
e = e.right;
}
}
}
}
/**
* 删除元素
*
* @param t
*/
public boolean deleteChild(T t) {
Node<T> targetNode = findNode(t);
if (Objects.nonNull(targetNode)) {
Node<T> parentNode = targetNode.getParent();
parentNode.setLeft(targetNode.getLeft());
parentNode.setRight(targetNode.getRight());
targetNode = null;
return true;
} else {
log.debug("{} 不存在", t);
return false;
}
}
/**
* 判断t是否存在
*
* @param t
* @return
*/
public boolean isExist(final T t) {
// 返回节点不为空则存在
return Objects.nonNull(findNode(t));
}
/**
* 查询t所在的节点
*
* @param t
* @return
*/
public Node<T> findNode(final T t) {
Node<T> e;
int res;
for (e = this; e != null;) {
if ((res = compareTo(t, e.getData())) < 0) {
if (e.left == null) {
return null;
} else {
e = e.left;
}
} else if (res == 0) {
return e;
} else {
if (e.right == null) {
return null;
} else {
e = e.right;
}
}
}
return null;
}
/**
* 比较两个节点
*/
public int compareTo(final Node<T> o) {
return compareTo(o.getData(), this.data);
}
/**
* 比较数值
*
* @param t1
* @param t2
* @return
*/
private int compareTo(T t1, T t2) {
return t1.compareTo(t2);
}
}
}
输出结果为(这里我手动格式化了一下):
BST.Node(
data=7,
left=BST.Node(
data=2,
left=null,
right=BST.Node(
data=6,
left=null,
right=null)),
right=BST.Node(
data=9,
left=null,
right=BST.Node(
data=10,
left=null,
right=BST.Node(
data=11,
left=null,
right=BST.Node(
data=12,
left=null,
right=BST.Node(
data=13,
left=null,
right=BST.Node(
data=14,
left=null,
right=BST.Node(
data=15,
left=null,
right=BST.Node(
data=16,
left=null,
right=null)))))))))
很明显添加形如: 10, 11, 12, 13, 14......这样的递增数字的时候, 会导致二叉树不断右斜(所有的子节点都在右子节点上).
进而性能向链表退化.
红黑树
平衡二叉树可以解决BST的倾斜退化问题, 红黑树就是这其中的一种解决方案. (另外如AVL等)
红黑树性质
- 任何一个节点都有颜色，黑色或者红色
- 根节点是黑色的
- 父子节点之间不能出现两个连续的红节点
- 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等
- 空节点被认为是黑色的
红黑树的自平衡
红黑树进行自平衡有以下几种处理方法: 变色, 左旋, 右旋.
这里简单说一下左旋和右旋的步骤, 请看下图(分别以R,H 和 L,H做左旋和右旋演示, 图画的有点拙劣 X_X):
对于新手,建议你先有这几点意识:
- 旋转只会发生在父子节点之间
- 旋转之后, 父子节点关系发生变化, 父节点变成子节点, 子节点变成父节点.
- 旋转方向上的子节点的子节点会改变父级指向. 比如: 右旋则子级节点的右子节点的父级会指向到子节点的父级上, 成为其左子节点.
- 左旋只会发生在右子节点和父节点之间; 右旋只会发生在左子节点和父节点之间.
- 左旋其父节点最终要变为左子节点, 右旋父节点最终要变成右子节点.
演示
下面演示加入10, 5, 20, 1, 3生成红黑树的过程:
- 添加10时, 父节点为空, 则将10设置为头节点, 并将其涂成黑色.
- 当新的节点插入时, 颜色要设置为红色, 插入红色时, 不会影响到达新的节点的黑色数量的计算. 但是插入红色唯一出现的问题是会违反规则3, 这个时候就需要进行变色和旋转. 使红黑树重新达到自平衡.
- 当插入节点5时, 我们设置其节点为红色, 校验父节点的颜色, 发现为黑色. 则红黑树条件满足. 插入节点20的情况与之相同
- 当插入节点1时, 遍历红黑树此时1应该放在5的左子树上. 当1设置为红色后, 发现父节点5也为红色. 这时我们需要将父节点5变为黑色,这时到达20的子节点的黑色节点数量和到达5的子节点的黑色数量不一致, 因此兄弟节点20也需要变成黑色, 以满足条件4.
- 之后再添加节点3, 3要先放到1的右子树上(如图所示). 并且颜色为红色.
首先我们先进行旋转让树达到平衡, 首先肯定不能对1和5进行右旋,因为3占据了右子节点. 因此先对1,3进行左旋, 如下图.
之后再进行3,5右旋,如下图.
进行完以上处理树已经缴纳满足平衡二叉树了. 但是仍旧不满足条件3,4. 此时我们进行变色处理. 将5变成红色, 3变成黑色.
这样就满足了红黑树的5个条件
end
这里有一个数据结构的模拟网站: www.cs.usfca.edu有兴趣可以自己尝试一下.
这篇文章我也是边学习边探索边写的(主要是探索), 有些坑还没有填上(比如红黑树的删除). 下一篇继续再说说hashmap中的红黑树的实现吧.
