【红黑树】java代码实现

红黑树本质上是对于2-3-4B树在遵循平衡二叉树规则的二叉树实现，通过旋转和颜色保证树本身的查询深度，有这么几条规则。
所有节点或为红色或为黑色，根节点比为黑色
新插入的节点为红色，任意两个红色节点都被一个以上的黑色节点隔开
遵循平衡二叉树规则旋转，根节点颜色不随旋转发生变化

本节点info字段用于存值，进行插入时拿来做比较
left和right分别为左右子节点
isRed用于标记节点颜色，默认为红色，当新节点

    private int info;
    private Point left;
    private Point right;
    private boolean isRed=true;//用于标记颜色，非红即黑，默认为红色

遵循平衡二叉树插入规则，左小右大向下传递，之后调用树平衡和颜色调整方法

    //插入
    public void add(Point p){
        if(this.info>p.getInfo()){
            if(this.left!=null){
                this.left.add(p);
            }else{
                this.left = p;
            }
        }
        if(this.info 
删除方法 
删除方法思路遵循2-3-4B树的删除规则，选取离删除节点最近的值取代当前节点，
 表现在平衡二叉树的情况下则是，选取左子树的最底右子节点或右子树的最底左子节点至被删除节点处，继承颜色并取代该值，同时删除被取到的节点
 
    //删除
    public void remove(int num){
        if(this.info>num){
            this.left.remove(num);
        }
        if(this.info 
树平衡 
进行插入和删除 *** 作之后需平衡左右子树
 思路为获取左右子树深度，差值超过2之后进行平衡
 在此处颜色不随节点位置旋转
 
    private void balance(){
        //如果其左子树长度高于右，则进行向右旋转
        if(this.getLeftHight()-this.getRightHight()>1){
            this.rightRotate();
            return;
        }
        //如果其右子树长度高于左，则进行向左旋转
        if(this.getRightHight()-this.getLeftHight()>1){
            this.leftRotate();
            return;
        }
    }
    public int getLeftHight(){
        if(this.getLeft()==null){
            return 0;
        }
        return this.getLeft().getHight();
    }
    public int getRightHight(){
        if(this.getRight()==null){
            return 0;
        }
        return this.getRight().getHight();
    }

    public int getHight(){
        if(this.getRight()==null && this.getLeft()==null){
            return 1;
        }else{
            return Math.max(this.getLeft() == null ? 0 : this.getLeft().getHight(), this.getRight() == null ? 0 : this.getRight().getHight())+ 1;
        }
    }

    //向左旋转
    private void leftRotate() {
        

        Point newPoint;
        if(this.getRight().getLeft()!=null && this.getRight().getRight()==null){
            newPoint = this.getRight();
            this.setRight(this.getRight().getLeft());
            this.getRight().setRight(newPoint);
            this.getRight().getRight().setLeft(null);
        }
        newPoint = new Point(this.info);
        if(this.getLeft()!=null){
            newPoint.setLeft(this.getLeft());
        }
        this.setLeft(newPoint);
        this.setInfo(this.getRight().getInfo());
        
        if(this.getRight().getLeft()!=null){
            this.getLeft().setRight(this.getRight().getLeft());
        }
        this.setRight(this.getRight().getRight());
        //此代码中实现的旋转仅为值的旋转，保证根节点为黑色
        this.isRed=false;
    }
    //向右旋转
    private void rightRotate() {
        
        Point newPoint;
        if(this.getLeft().getRight()!=null && this.getLeft().getLeft()==null){
            newPoint = this.getLeft();
            this.setLeft(this.getLeft().getRight());
            this.getLeft().setLeft(newPoint);
            this.getLeft().getLeft().setRight(null);
        }

        newPoint = new Point(this.info);
        if(this.getRight()!=null){
            newPoint.setRight(this.getRight());
        }
        this.setRight(newPoint);
        this.setInfo(this.getLeft().getInfo());
        
        if(this.getLeft().getRight()!=null){
            this.getRight().setLeft(this.getLeft().getRight());
        }
        this.setLeft(this.getLeft().getLeft());
        //此代码中实现的旋转仅为值的旋转，保证根节点为黑色
        this.isRed=false;
    }

 
颜色调整 
此处关注节点为爷爷节点，检测子节点和孙子节点是否存在连续红色，若存在则将自身变红，将子节点变黑，此方法逐步递归向上，直至将红色传递至根节点，此时遵循根节点必为黑色的原则，将根节点设置为黑色
 
 void changeColor(){
        if(this.left!=null && this.left.left!=null){
            if(this.left.isRed && this.left.left.isRed){
                this.isRed = true;
                this.left.isRed = false;
            }
        }
        if(this.left!=null && this.left.right!=null){

        }
        if(this.left!=null && this.right.left!=null){

        }
        if(this.left!=null && this.right.right!=null){

        }
        if(this.right!=null && this.left.left!=null){

        }
        if(this.right!=null && this.left.right!=null){

        }
        if(this.right!=null && this.right.left!=null){

        }
        if(this.right!=null && this.right.right!=null){

        }
        //setRootColorBlack();
    }

 
完整代码 
没有细调，大家当伪码看吧
 
package ReadBlackTree;

public class Point {
    private int info;
    private Point left;
    private Point right;
    private boolean isRed=true;//用于标记颜色，非红即黑，默认为红色

    public Point(int num){this.info = num;}
    public int getInfo() {
        return info;
    }

    public void setInfo(int info) {
        this.info = info;
    }

    public Point getLeft() {
        return left;
    }

    public void setLeft(Point left) {
        this.left = left;
    }

    public Point getRight() {
        return right;
    }

    public void setRight(Point right) {
        this.right = right;
    }

    public boolean isRed() {
        return isRed;
    }

    public void setRed(boolean red) {
        isRed = red;
    }
    //删除
    public void remove(int num){
        if(this.info>num){
            this.left.remove(num);
        }
        if(this.infop.getInfo()){
            if(this.left!=null){
                this.left.add(p);
            }else{
                this.left = p;
            }
        }
        if(this.info1){
            this.rightRotate();
            return;
        }
        //如果其右子树长度高于左，则进行向左旋转
        if(this.getRightHight()-this.getLeftHight()>1){
            this.leftRotate();
            return;
        }
    }
    public int getLeftHight(){
        if(this.getLeft()==null){
            return 0;
        }
        return this.getLeft().getHight();
    }
    public int getRightHight(){
        if(this.getRight()==null){
            return 0;
        }
        return this.getRight().getHight();
    }

    public int getHight(){
        if(this.getRight()==null && this.getLeft()==null){
            return 1;
        }else{
            return Math.max(this.getLeft() == null ? 0 : this.getLeft().getHight(), this.getRight() == null ? 0 : this.getRight().getHight())+ 1;
        }
    }

    //向左旋转
    private void leftRotate() {
        

        Point newPoint;
        if(this.getRight().getLeft()!=null && this.getRight().getRight()==null){
            newPoint = this.getRight();
            this.setRight(this.getRight().getLeft());
            this.getRight().setRight(newPoint);
            this.getRight().getRight().setLeft(null);
        }
        newPoint = new Point(this.info);
        if(this.getLeft()!=null){
            newPoint.setLeft(this.getLeft());
        }
        this.setLeft(newPoint);
        this.setInfo(this.getRight().getInfo());
        
        if(this.getRight().getLeft()!=null){
            this.getLeft().setRight(this.getRight().getLeft());
        }
        this.setRight(this.getRight().getRight());
        //此代码中实现的旋转仅为值的旋转，保证根节点为黑色
        this.isRed=false;
    }
    //向右旋转
    private void rightRotate() {
        
        Point newPoint;
        if(this.getLeft().getRight()!=null && this.getLeft().getLeft()==null){
            newPoint = this.getLeft();
            this.setLeft(this.getLeft().getRight());
            this.getLeft().setLeft(newPoint);
            this.getLeft().getLeft().setRight(null);
        }

        newPoint = new Point(this.info);
        if(this.getRight()!=null){
            newPoint.setRight(this.getRight());
        }
        this.setRight(newPoint);
        this.setInfo(this.getLeft().getInfo());
        
        if(this.getLeft().getRight()!=null){
            this.getRight().setLeft(this.getLeft().getRight());
        }
        this.setLeft(this.getLeft().getLeft());
        //此代码中实现的旋转仅为值的旋转，保证根节点为黑色
        this.isRed=false;
    }

}

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5637686.html