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

weblog 精帖
404

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

二叉树左旋

        左旋的过程是将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

猜你喜欢
  • blog 八皇后问题

    八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。1.方
  • blog 最小生成Kruskal算法-数据结构和算法

    最小生成算法和其应用         什么是最小生成:一个有 n 个结点的连通图的生成是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成可以用krus
  • blog 二叉基本操作 c++

    二叉基本操作 c++class node{public : int data; node * left; node * right; node(); node(int data); node(int data,node * left,no
  • blog avl的插入和删除操作

    package avlTree;import java.util.LinkedList;/** * avl(平衡二叉) * @author Administrator * */public class AvlTree { privat
  • ofc linux vi编辑器命令

    linux vi编辑器命令
  • blog 二叉的遍历-(递归法)和(非递归法)

    整理 二叉的遍历-(递归法)和(非递归法)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:package tree;public class Node<E> { private E e;//数据域 private Node<E
  • blog java集合之TreeMap实现原理

    java集合之TreeMap实现原理         TreeMap集合的实现其实说简单也简单说复杂也复杂,说简单是因为TreeMap底层实现完全依靠这个数据结构,相比与HashMap来说Tr
  • blog java工具 jmap 命令的使用方法以及堆内存快照的创建及分析(1)

            jmap是java虚拟机自带的一种内存映像工具,我们可以通过该工具配合不同的参数来查看java虚拟机内存的详细信息(如程序中出现的所有对象的数量以及占用内存大小等),以及通过虚拟机内存
  • blog 二叉删除节点 c++

    二叉删除节点 c++先看一个简单的图删除节点是分以下几种情况: 1.待删节点为叶子节点:此种情况下直接删除叶子节点即可 2.待删节点只有左子,或只有右子,那么将左子或右子的根节点替换该节点即可 3.待删节点既有
  • blog 二叉的一些性质

    转载:https://www.cnblogs.com/willwu/p/6007555.html1. 的定义 是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。 把它叫做“”是因为它看起来像一棵倒挂