红黑树测试类运行后为什么控制台报StackOverFlowError异常
package itheima9;
import com.sun.jdi.Value;
public class RedBlackTree<Key extends Comparable<Key>,Value> {
//成员变量-根节点
private Node root;
//成员变量-树中元素个数
private int N;
//成员变量-当前结点的指向链接为红色
private final boolean redColor=true;
//成员变量-当前结点的指向链接为黑色
private final boolean blackColor=false;
//内部类-结点类
private class Node{
//成员变量-键
private Key key;
//成员变量-值
private Value value;
//成员变量-左子节点
private Node left;
//成员变量-右子节点
private Node right;
//成员变量-当前结点的指向链接的颜色
private boolean color;
//构造方法
public Node(Key key, Value value, Node left, Node right, boolean color) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.color = color;
}
}
//成员方法-获取树中个数
public int size(){
return N;
}
//成员方法-判断当前结点是否为红色
private boolean isRed(Node n){
if(n==null){
return false;
}
return n.color==redColor;
}
//成员方法-红黑树左旋 并获取整个树
private Node rotateLeft(Node h){
//获取h结点的右子节点
Node x = h.right;
//让x结点的左子节点变成h结点的右子节点
x.left=h.right;
//让h结点变成x结点的左子节点
h=x.left;
//让x结点的指向链接颜色变成h结点的指向链接颜色
x.color=h.color;
//让h结点的指向链接颜色变成红色
h.color=redColor;
return x;
}
//成员方法-红黑树右旋
private Node rotateRight(Node h){
//获取h结点的左子节点
Node x = h.left;
//让x结点的右子节点成为h结点的右子节点
h.right=x.right;
//让h结点成为x结点的右子节点
x.right=h;
//让x结点的指向链接颜色变成黑色
x.color=h.color;
//让h结点的指向链接颜色变成红色
h.color=redColor;
return x;
}
//成员方法-颜色反转
private void flipColor(Node h){
//让h结点的指向链接颜色变成红色
h.color=redColor;
//让h结点的左子节点和右子节点的指向链接颜色变成黑色
h.left.color=blackColor;
h.right.color=blackColor;
}
//成员方法-往整个树中插入元素
public void put(Key key,Value value){
root = put(root, key, value);
//根节点的指向链接总是为黑色
root.color=blackColor;
}
//成员方法-往指定树中插入元素 并返回插入后的新树
public Node put(Node h,Key key,Value value){
//安全性校验-如果指定树为空
if(h==null){
//插入后N+1
N++;
//创建一个新结点
Node newN = new Node(key, value, null, null, redColor);
return newN;
}
//如果指定树非空
//定义一个变量 用于比较当前键和指定节点键的大小
int i = key.compareTo(h.key);
//如果当前键小于指定节点的键 递归调用put方法 在去与指定节点的左子节点进行比较
if(i<0){
h.left=put(h.left,key,value);
}//如果当前键大于指定节点的键 递归调用put方法 在去与指定节点的右子节点进行比较
else if (i>0) {
h.right=put(h.right,key,value);
}//如果当前键等于指定节点的键 直接替换指定节点的值
else {
h.value=value;
}
//如果右子节点为红色 且 左子节点为黑色 那么需要进行左旋
if(isRed(h.right)&&!isRed(h.left)){
rotateLeft(h);
}//如果左子节点为红色 且 左子节点的左子节点为红色 那么需要进行右旋
if (isRed(h.left)&&isRed(h.left.left)) {
rotateRight(h);
}//如果左子节点和右子节点都为红色 那么需要进行颜色反转
if (isRed(h.left)&&isRed(h.right)) {
flipColor(h);
}
return h;
}
//成员方法-在整个树中获取指定键对应的值
public Value get(Key key){
return get(root,key);
}
//成员方法-在指定树中获取指定键对应的值
public Value get(Node h,Key key){
//安全性校验-指定树为空
if(h==null){
return null;
}
//定义一个变量 用于储存指定树和指定键的大小比较
int i = key.compareTo(h.key);
//如果指定键小于指定结点的键 那么递归调用get方法 在当前结点的左子树中查找
if(i<0){
return get(h.left,key);
}//如果指定键大于指定结点的键 那么递归调用get方法 在当前结点的右子树中查找
else if (i>0) {
return get(h.right,key);
}//如果指定键等于指定结点的键 那么直接获取指定节点的值
else {
return h.value;
}
}
}
