rbnode.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 102 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//12 Mar 2008
package cn.edu.whu.iss.algorithm.unit14;

import cn.edu.whu.iss.algorithm.unit13.RBTreeElement;

public class RBNode<T> extends RBTreeElement<T>{

	public static final int DEFAULT_SIZE = 1,SENTINEL_SIZE = 0;
	private RBNode<T> leftChild,rightChild,parent;
	
	private int size = DEFAULT_SIZE;
	
	public RBNode(T o) {
		super(o);
	}

	public RBNode<T> getChild(int direction){
		if(direction<0){
			return leftChild;
		}else if(direction>0){
			return rightChild;
		}
		return null;
	}
	
	public RBNode(T o, RBNode<T> sentinel){
		super(o,sentinel);
		this.parent = sentinel;
		this.leftChild = sentinel;
		this.rightChild = sentinel;
		super.parent = this.parent;
		super.leftChild = this.leftChild;
		super.rightChild = this.rightChild;
	}
	
	public void setChild(int dir,RBNode<T> child){
		if(dir<0){
			leftChild = child;
		}else if(dir>0){
			rightChild = child;
		}
	}
	
	public RBNode<T> getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(RBNode<T> leftChild) {
		this.leftChild = leftChild;
	}

	public RBNode<T> getRightChild() {
		return rightChild;
	}

	public void setRightChild(RBNode<T> rightChild) {
		this.rightChild = rightChild;
	}

	public RBNode<T> getParent() {
		return parent;
	}

	public void setParent(RBNode<T> parent) {
		this.parent = parent;
	}

	public int getSize() {
		return size;
	}

	public void setSize(int size) {
		this.size = size;
	}
	
	public void increaseSize(){
		this.size++;
	}
	
	public void decreaseSize(){
		this.size--;
	}
	
	public void computeSize(){
		this.size = this.getLeftChild().getSize()+this.getRightChild().getSize()+1;
	}

	public boolean hasTwoBlackChildren(){
		return leftChild.isBlack()&&rightChild.isBlack();
	}
	
}