红黑树的性质:
每个节点要么是黑色的, 要么是红色的
根节点是黑色的
每个叶子节点都是黑色的
不能有连续两个红色节点
任意一个节点到每个叶子节点的路径上都包含数量相同的黑色节点
新插入的节点总是红色的
?
[事先声明: N(now)表示当前节点, P(parent)表示 N 的父节点, U(uncle)表示 N 的叔叔节点, G(grandfather)表示 N 的祖父节点, 也就是 P 和 U 的父节点.]
?
几种需要变色和旋转的可能:
插入节点的父节点是红色的:
?
1. 插入节点的父节点和其叔叔节点 (祖父节点的另一个子节点) 均为红色.
应对策略: 将当前节点的父亲节点 P 和叔叔节点 M 涂黑, 祖父节点 G 涂红, 再将祖父节点 G 设置为当前节点.
?
2. 叔叔节点不存在或为黑节点, 插入节点的父亲节点是祖父节点的左节点
2.1 插入节点是其父节点的左节点
应对策略: P 设置为黑色, PP 设为红色, 对 PP 进行右旋
2.2 插入节点是其父节点的右节点
应对策略: 把 P 进行左旋, 把 P 设置为插入节点, 进行 2.1 处理
?
3. 叔叔节点不存在或为黑节点, 插入节点的父亲节点是祖父节点的右节点
3.1 插入节点是其父节点的右节点
应对策略: P 设置为黑色, PP 设为红色, 对 PP 进行左旋
2.2 插入节点是其父节点的左节点
应对策略: 把 P 进行右旋, 把 P 设置为插入节点, 进行 3.1 处理
?
代码实现:
- private void insertFixUp(RBNode<T> node){
- ????RBNode<T> parent,gparent;// 定义父节点和祖父节点
- ????? ?
- ????// 需要修正的条件: 父节点存在, 且父节点的颜色是红色
- ????while(((parent = parentOf(node)) != null) && isRed(parent)){
- ????????gparent = parentOf(parent);// 获得祖父节点
- ????????? ?
- ????????// 若父节点是祖父节点的左子节点, 下面的 else 相反
- ????????if(parent == gparent.left){
- ????????????RBNode<T> uncle = gparent.right;// 获得叔叔节点
- ????????????? ?
- ????????????//case1: 叔叔节点也是红色
- ????????????if(uncle != null && isRed(uncle)){
- ????????????????setBlack(parent);// 把父节点和叔叔节点涂黑
- ????????????????setBlack(gparent);
- ????????????????setRed(gparent);// 把祖父节点涂红
- ????????????????node = gparent;// 把位置放到祖父节点处
- ????????????????continue;// 继续 while 循环, 重新判断
- ????????????
- }
- ????????????? ?
- ????????????//case2: 叔叔节点是黑色, 且当前节点是右子节点
- ????????????if(node == parent.right){
- ????????????????leftRotate(parent);// 从父节点出左旋
- ????????????????RBNode<T> tmp = parent;// 然后将父节点和自己调换一下, 为下面右旋做准备
- ????????????????parent = node;
- ????????????????node = tmp;
- ????????????
- }
- ????????????? ?
- ????????????//case3: 叔叔节点是黑色, 且当前节点是左子节点
- ????????????setBlack(parent);
- ????????????setRed(gparent);
- ????????????rightRotate(gparent);
- ????????
- }else{
- // 若父节点是祖父节点的右子节点, 与上面的情况完全相反, 本质是一样的
- ????????????RBNode<T> uncle = gparent.left;
- ????????????? ?
- ????????????//case1: 叔叔节点也是红色的
- ????????????if(uncle != null && isRed(uncle)){
- ????????????????setBlack(parent);
- ????????????????setBlack(uncle);
- ????????????????setRed(gparent);
- ????????????????node = gparent;
- ????????????????continue;
- ????????????
- }
- ????????????? ?
- ????????????//case2: 叔叔节点是黑色的, 且当前节点是左子节点
- ????????????if(node == parent.left){
- ????????????????rightRotate(parent);
- ????????????????RBNode<T> tmp = parent;
- ????????????????parent = node;
- ????????????????node = tmp;
- ????????????
- }
- ????????????? ?
- ????????????//case3: 叔叔节点是黑色的, 且当前节点是右子节点
- ????????????setBlack(parent);
- ????????????setRed(gparent);
- ????????????leftRotate(gparent);
- ????????
- }
- ????
- }
- ????setBlack(root);// 将根节点设置为黑色
- }
- ?
- ?
红黑树相比平衡二叉树(AVL):
1. 在查询性能方面红黑树略微逊色于 AVL 树, 因为红黑树不是严格的平衡树
2. 在增删方面, avl 每次增删都需要进行大量的平衡度计算, 而红黑树为了维持红黑性质所做的红黑变换和旋转的开销, 相较于 avl 树为了维持平衡的开销要小得多
整体来说: 红黑树是牺牲了严格的高度平衡的优越条件为 代价红黑树能够以 O(log2 n)的时间复杂度进行搜索, 插入, 删除操作. 此外, 由于它的设计, 任何不平衡都会在三次旋转之内解决.
红黑树
来源: http://www.bubuko.com/infodetail-3474905.html