手撕红黑树(1)-预备知识

weblog 1487 0 0

本篇文章为红黑树的预备知识,暂且不涉及节点颜色。

二叉树左旋

        左旋的过程是将x的右子树绕x逆时针旋转,使得x的右子树成为x的父节点,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

示例:

旋转前

       |                             
/------3(null)-------\               
|                    |               
1(null)       /------10(null)\       
              |              |       
              6(null)        15(null)

旋转后

                     |               
       /-------------10(null)\       
       |                     |       
/------3(null)\              15(null)
|             |                      
1(null)       6(null)                

相关代码:

/**
 * 左旋
 * p为旋转的中心点
 */
public void rotateLeft(Node<T,E> p) {
	if (p != null) {
		Node<T,E> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

二叉树右旋

        右旋的过程是将x的左子树绕x顺时针旋转,使得x的左子树成为x的父节点,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然满足。

示例

旋转前

                     |               
       /-------------10(null)\       
       |                     |       
/------3(null)\              15(null)
|             |                      
1(null)       6(null)                

旋转后 

       |                             
/------3(null)-------\               
|                    |               
1(null)       /------10(null)\       
              |              |       
              6(null)        15(null)

相关代码:

/**
 * 右旋
 * 以p点为中心点旋转
 */
public void rotateRight(Node<T,E> p) {
    if (p != null) {
        Node<T,E> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
	}
}

二叉搜索树寻找某节点的前驱节点和后继节点

参考:http://www.jiajiajia.club/official/weblog/39

猜你喜欢
weblog 2702 简介 (RedBlackTree)是一种自平衡二叉查找,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。和AVL类似,都是在进行插入和删除操作时通过特定
数据结构与算法 3109 在关于的多种算法中都用到了的旋转来使保持相对平衡,比如avl等...1.的左旋(pivot为旋转中心点)2.来个动图3.代码演示:/** *左旋 *p为旋转的中心点
weblog 290 成为java架构师需要学习那些原文:https://blog.csdn.net/zuiyingong6567/article/details/80285827既然java架构师,首先你要是一个高
official 97 了5、6、7、8号房间。四个人的编号0、1、2、3其实是一个“相对位置”,而各自入住的房间号是一个“绝对位置”。只要道О号同学住的是房号为N的房间,那么M号同学的房号一定是N+M。也就是说,只要道各
java基础 1587 泛型1.什么是泛型Java泛型(generics)是JDK5中引入的一个新特性,泛型提供了编译时类型安全检测机制,该机制允许程序员在编译时检测到非法的类型。泛型的本质是参数化类型,也就是说所操作的数
java基础 405 参数 抽象类 接口 默认的方法实现 它可以有默认的方法实现 接口完全是抽象的。它根本不存在方法的实现 实现 子类使用extends关键字来继承抽象类。如果子类不是抽象类的话,它需要提供抽象类中所有声明的方法的实现。 子类使用关键字implements来实现接口。它需要提供接口中所有声明的方法的实现 构造器 抽象类可以有构造
java基础 581 java集合之TreeMap实现原理TreeMap集合的实现其实说简单也简单说复杂也复杂,说简单是因为TreeMap底层实现完全依靠这个数据结构,相比与HashMap来说TreeMap不用考虑
数据结构与算法 6275 题目:判断下方两棵二叉右方的二叉是否为左方二叉的子1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
目录