|
|
发表于 2004-7-10 12:24:22
|
显示全部楼层
好了， 我整个关于2－4 tree, Red-black tree 和 2－4， Red-black tree转换的class写出来了， 但很长， 你们将就点看吧。。。。。。[PHP]/******************************************************************************************
This project is to write a Java class that can take any red-black tree and convert it into
its corresponding (2.4) tree and can take any (2,4) tree convert it into its corresponding
red-black tree.
There are three following main classes:
1. A class called RBTree implementing the Dictionary ADT using a red-black search tree
2. Another class called TwoFourTree implementing the Dictionary ADT using a 2-4 search tree
3. The other class called Convert that can take any red-black tree and convert it into its
corresponding (2,4) tree and can take any (2,4) tree and convert it into its corresponding
red-black tree
programmer: Qian-Ru Liang
Date: 6-26-2004
*********************************************************************************************/
class item{
private Object key, element;
item(Object k, Object e){
key = k;
element = e;
}
item(Object k){
key = k;
}
item (){
key = null;
element = null;
}
public Object element() { return element; }
public Object key() { return key;}
public void setelement(Object e){ element = e; }
public void setkey(Object k) { key = k; }
}
class twofourNode{
private item itemArray[];
private twofourNode linkArray[]; // children link array
private twofourNode parent;
private int itemlength; // length for itemArray
private int linklength; // length for linklength
private IntegerComparator comp;
private int linkadded, linkremoved; // the lastest index that link inserted and removed
// constructor
twofourNode(){
itemlength = 0;
linklength = 1;
itemArray = new item[4];
linkArray = new twofourNode[1];
parent = null;
linkadded = -1;
linkremoved = -1;
comp = new IntegerComparator();
}
twofourNode(twofourNode p){
itemlength = 0;
linklength = 1;
itemArray = new item[4];
linkArray = new twofourNode[1];
parent = p;
linkadded = -1;
linkremoved = -1;
comp = new IntegerComparator();
}
twofourNode(int noItem){
itemlength = noItem;
linklength = itemlength + 1;
itemArray = new item[4];
linkArray = new twofourNode[linklength];
parent = null;
linkadded = -1;
linkremoved = -1;
comp = new IntegerComparator();
}
twofourNode(int noItem, twofourNode p){
itemlength = noItem;
linklength = itemlength + 1;
itemArray = new item[4];
linkArray = new twofourNode[linklength];
parent = p;
linkadded = -1;
linkremoved = -1;
}
// Query methods
public int size(){ return itemlength; }
public boolean overflow(){ return (itemlength == 4); }
public boolean underflow(){ return (itemlength == 0); }
public int nolink(){ return linklength; }
public int getlinkadded() { return linkadded; }
public int getlinkremoved() { return linkremoved; }
// Access methods
public Object[] getkeys(){
Object keys[] = new Object[itemlength];
for (int i = 0; i <= itemlength - 1; i++)
keys = itemArray.key();
return keys;
}
// searchkey function return an index of the key located in the itemArray
public int searchkey(Object k){
int i = 0;
while (i < itemlength && !comp.isEqualTo(k,itemArray.key()))
i++;
return i;
}
public Object getelement(Object k){
int i = searchkey(k);
return itemArray.element();
}
public Object[] getelements(){
Object elements[] = new Object[itemlength];
for (int i = 0; i <= itemlength - 1; i++)
elements = itemArray.element();
return elements;
}
public item[] getItems(){
item temp[] = new item[itemlength];
for (int i = 0; i < itemlength; i++)
temp = itemArray;
return temp;
}
public item getItem(Object k){
int i = searchkey(k);
return itemArray;
}
// Obtain all child links in this twofourNode
public twofourNode[] getchildren(){
twofourNode info[] = new twofourNode[linklength];
for (int i = 0; i < linklength; i++)
info = linkArray;
return info;
}
public twofourNode getparent(){ return parent; }
// Obtain the right child link relative to k
public twofourNode getrightchild(Object k){
int i;
i = searchkey(k);
return linkArray[i + 1];
}
// Obtain the left child link relative to k
public twofourNode getleftchild(Object k){
int i;
i = searchkey(k);
return linkArray;
}
// Obtain the leftmost child link
public twofourNode getleftmost(){ return linkArray[0]; }
// Obtain the rightmost child link
public twofourNode getrightmost() { return linkArray[linklength - 1]; }
// Obtain the item with smallest key --> leftmost item
public item getsmallest() { return itemArray[0]; }
// Obtain the item with greatest key --> rightmost item
public item getgreatest() { return itemArray[itemlength - 1]; }
// Obtain the item with the mid key --> middle item if it is avaliable
public item getmid() { return itemArray[1]; }
// supportive methods for update methods
// find the exact index that the item should be inserted
public int insertindex(Object k){
int i;
for (i = 0; i < itemlength; i++){
if (comp.isLessThan(k, itemArray.key()))
return i;
i++;
}
return i;
}
// copy the old child links to a new link array with old linklength plus 1 --> for addchild() and removechild functions
public void copylink(int volume){ // for addlinks && removelinks
twofourNode temp[] = new twofourNode[linklength];
for (int i = 0; i <= volume - 1; i++) // copy the old child links
temp = linkArray;
linkArray = temp;
}
// **There is a relationship between index of item inserted(i) or removed and that of child link added(j) or deleted: j = i + 1;
// update methods
public void insertItem(item input){
Object k = input.key();
int i;
if(underflow()){
itemArray[0] = input;
itemlength++;
linkadded = 1;
}
else if(comp.isGreaterThan(k, itemArray[itemlength - 1].key())){
itemArray[itemlength] = input;
itemlength++;
linkadded = itemlength;
}
else{
i = insertindex(k);
for (int j = itemlength - 1; j >= i; j--)
itemArray[j + 1] = itemArray[j];
itemArray = input;
itemlength++;
linkadded = i + 1;
}
}
public item removeItem(item input){
Object k = input.key();
int i;
item temp = input;
i = searchkey(k);
for (int j = i; j <= itemlength - 2; j++)
itemArray[j] = itemArray[j + 1];
itemlength--;
linkremoved = i + 1;
return temp;
}
public void addchild(twofourNode p, int linkadded){
int volume = linklength;
linklength++;
copylink(volume);
if (linkadded == linklength - 1)
linkArray[linkadded] = p;
else{
for (int i = volume - 1; i >= linkadded; i--)
linkArray[i + 1] = linkArray;
linkArray[linkadded] = p;
}
}
public twofourNode removechild(int linkremoved){
twofourNode temp = linkArray[linkremoved];
for (int i = linkremoved; i <= linklength - 2; i++)
linkArray = linkArray[i + 1];
linklength--;
copylink(linklength);
return temp;
}
public void setparent(twofourNode p){ parent = p; }
public void setleftchild(twofourNode p, Object k) {
int i = searchkey(k);
linkArray = p;
}
public void setrightchild(twofourNode p, Object k) {
int i = searchkey(k);
linkArray[i + 1] = p;
}
public void setrightmost(twofourNode p){ linkArray[itemlength - 1] = p; }
public void setleftmost(twofourNode p) { linkArray[0] = p; }
public void printkeys() {
Object temp[] = getkeys();
Integer a;
for (int i = 0; i < temp.length; i++){
a = (Integer)temp;
System.out.print(a.intValue() + " ");
}
}
}
class twofourTree{
private twofourNode root;
int size;
IntegerComparator C;
int capacity;
twofourTree(IntegerComparator c){
root = new twofourNode();
size = 0; // number of internal nodes
C = c;
capacity = 1000;
}
twofourTree(){
root = new twofourNode();
size = 0; // number of internal nodes
capacity = 1000;
C = new IntegerComparator();
}
// Auxiliary methods
// findnode() is the way to find the exact node where the item is located at. If reachs external node, then no item found.
public twofourNode findnode(Object k, twofourNode p){
if (isExternal(p)) // p.size() == 0--> underflow
return p;
else {
int casecontrol = p.size();
Object[] v = p.getkeys();
if (casecontrol == 1){
if (C.isLessThan(k, v[0])){
p = p.getleftchild(v[0]);
return findnode(k, p);
}
else if (C.isGreaterThan(k, v[0])){
p = p.getrightchild(v[0]);
return findnode(k, p);
}
else
return p;
}
else if (casecontrol == 2){
if (C.isLessThan(k, v[0])){
p = p.getleftchild(v[0]);
return findnode(k, p);
}
else if(C.isGreaterThan(k, v[0]) && C.isLessThan(k, v[1])){
p = p.getrightchild(v[0]);
return findnode(k, p);
}
else if(C.isGreaterThan(k, v[1])){
p = p.getrightchild(v[1]);
return findnode(k, p);
}
else
return p;
}
// when casecontrol == 3
else{
if (C.isLessThan(k, v[0])){
p = p.getleftchild(v[0]);
return findnode(k, p);
}
else if(C.isGreaterThan(k, v[0]) && C.isLessThan(k, v[1])){
p = p.getrightchild(v[0]);
return findnode(k, p);
}
else if(C.isGreaterThan(k, v[1]) && C.isLessThan(k, v[2])){
p = p.getrightchild(v[1]);
return findnode(k, p);
}
else if(C.isGreaterThan(k, v[2])){
p = p.getrightchild(v[2]);
return findnode(k, p);
}
else
return p;
}
}
}
// supportive method for removeitem();
public void swap(item remove, item replace){
item temp = remove;
Object k, e;
k = replace.key();
e = replace.element();
remove.setkey(k);
remove.setelement(e);
k = temp.key();
e = temp.element();
replace.setkey(k);
replace.setelement(k);
}
// suportive method for removeitem();
public twofourNode findswapnode(twofourNode p, Object k){
p = p.getrightchild(k);
while (!isExternal(p))
p = p.getleftmost();
p = parent(p);
return p;
}
public void checkKey(Object k) throws InvalidKeyException{
if(!C.isComparable(k))
throw new InvalidKeyException("Key " + k + " is not comparable");
}
public void checkTree() throws EmptyTreeException{
if (size() == 0)
throw new EmptyTreeException("The tree is an empty tree!");
}
public twofourNode getnextsibling(twofourNode p){
twofourNode mother = parent(p);
twofourNode[] temp = mother.getchildren();
int i = 0;
while (i < temp.length && temp != p)
i++;
if (i == 0)
return temp[i + 1];
else if (i == temp.length - 1)
return temp[i - 1];
else{
if (temp[i + 1].size() > 1)
return temp[i + 1];
else
return temp[i - 1];
}
}
public boolean leftsibling(twofourNode p){
twofourNode next = parent(p);
twofourNode[] temp = next.getchildren();
int i = 0;
while (i < temp.length && temp != p)
i++;
if (i == 0)
return false;
else if (i == temp.length - 1)
return true;
else{
if (temp[i + 1].size() > 1)
return false;
else
return true;
}
}
// Decide which item in the parent is going to transfer to underflow child when itemRemove() is executed
public item ObtainParentMove(twofourNode child){
int i;
twofourNode sibling = getnextsibling(child);
boolean left = leftsibling(child);
item Pitems[] = parent(child).getItems();
twofourNode children[] = parent(child).getchildren();
for (i = 0; i < children.length; i++){
if (children == child)
break;
}
if (left)
return Pitems[i - 1];
else
return Pitems;
}
// Access methods
public twofourNode[] children(twofourNode p) throws NullNodeException{
if (p.size() == 0)
throw new NullNodeException("This node is a null node!");
return p.getchildren();
}
public twofourNode parent(twofourNode p) throws RootNodeException{
if (isRoot(p))
throw new RootNodeException("This node is root without any parent!");
return p.getparent();
}
public twofourNode[] siblings(twofourNode p){
twofourNode v = parent(p);
twofourNode s[] = new twofourNode[v.nolink()];
twofourNode temp[] = children(v);
int i, j;
i = 0;
// this loop is to copy all children except p itself
while (i < v.nolink()){
if (temp != p)
s = temp;
else
s = null;
i++;
}
// this loop is to find the p's index
while (i < s.length && s != null)
i++;
j = i;
if (j == s.length - 1)
return s;
else{
// shift left
for (i = j; i <= v.nolink() - 2; i++)
s = s[i + 1];
return s;
}
}
// methods of the Dictionary ADT
//Query Methods
public int size(){ return size; }
public boolean isEmpty() { return (size == 0); }
public boolean isRoot(twofourNode v) { return (v == root); }
public boolean isInternal(twofourNode v){ return (!v.underflow()); }
public boolean isExternal(twofourNode v){ return (v.underflow()); }
public twofourNode root(){ return root; }
// Preorder traverse the tree
public void elements(twofourNode v, Object[] result, int index){
if (isExternal(v))
return;
else{
item[] temp = v.getItems();
int i;
twofourNode children[] = v.getchildren();
for (i = 0; i < temp.length; i++){
result[index] = temp.element();
index++;
}
for (i = 0; i < v.nolink(); i++)
elements(children, result, index);
}
}
// Preorder traverse the tree
public void keys(twofourNode v, Object[] result, int index){
if (isExternal(v))
return;
else{
item[] temp = v.getItems();
int i;
twofourNode children[] = v.getchildren();
for (i = 0; i < temp.length; i++){
result[index] = temp.key();
index++;
}
for (i = 0; i < v.nolink(); i++)
keys(children, result, index);
}
}
// for Print()
public twofourNode findEnd(){
twofourNode end = root;
while (!isExternal(end))
end = end.getrightmost();
return end;
}
// Access methods
public Object findElement(Object k) throws InvalidKeyException{
checkKey(k);
twofourNode p = root;
p = findnode(k, p);
if (!isExternal(p))
return p.getelement(k);
else{
System.out.print("No this item found!\n");
return null;
}
}
public Object[] findAllElements(Object k) throws EmptyTreeException{
checkTree();
twofourNode p = root;
Object[] result = new Object[capacity];
int i = 0;
while (!isExternal(findnode(k, p))){
result = p.getelement(k);
p = p.getleftchild(k);
i++;
}
return result;
}
// Update methods
public void expandExternal(twofourNode p, Object k){
twofourNode temp = new twofourNode(p);
p.addchild(temp, p.nolink()); // if p is not overflow, after insertion of k, setrightchild to new external
}
public void insertitem(item input) throws InvalidKeyException{
Object k = input.key();
twofourNode p = root;
checkKey(k);
if (isRoot(p) && isExternal(p)){
p.insertItem(input);
expandExternal(p, k);
}
else{
p = findnode(k, p);
if (isExternal(p)){
p = parent(p);
p.insertItem(input);
expandExternal(p, k);
if (p.overflow()){
split(p);
}
}
else{
while (!isExternal(findnode(k, p)))
p = p.getleftchild(k);
p = parent(p);
p.insertItem(input);
expandExternal(p, k);
if (p.overflow()){
split(p);
}
}
}
}
public item removeitem(Object k) throws InvalidKeyException{
checkKey(k);
twofourNode p = root;
twofourNode w; // sibling
item item1, item2;
int i;
boolean left;
p = findnode(k, p);
item1 = p.getItem(k);
if (isExternal(p.getleftmost())){
p.removeItem(item1);
i = p.getlinkremoved();
if (!p.underflow()){ p.removechild(i); }
else{
w = getnextsibling(p); // get left or right sibling of p
left = leftsibling(p); // check this sibling is on left side of p or not
if ( w.size() > 1 )
transfer(p, w, left); // do transfer if the sibling w has more than two children
else
fuse(p, w); // do fuse if the sibling w has only two children
}
return item1;
}
else{
w = findswapnode(p, k);
item2 = w.getsmallest();
swap(item1, item2);
item1 = p.removeItem(item2);
i = p.getlinkremoved();
if (!p.underflow()) { p.removechild(i); }
else{
w = getnextsibling(p);
left = leftsibling(p);
if (w.size() > 1)
transfer(p, w, left);
else
fuse(p, w);
}
return item1;
}
}
public void split(twofourNode old){
if (!old.overflow()) { return; }
else{
int i;
Object k;
twofourNode temp;
twofourNode parent = parent(old);
// initialize two new nodes in which both their parents are parent of the old node
twofourNode left = new twofourNode(2, parent);
twofourNode right = new twofourNode(1,parent);
item[] tempold = old.getItems();
twofourNode[] linkold = old.getchildren();
// copy items to new split two nodes
for (i = 0; i < 2; i++)
left.insertItem(tempold);
right.insertItem(tempold[3]);
// copy children links of two nodes
for (i = 1; i < 3; i++){
left.addchild(linkold, i);
linkold.setparent(left);
}
left.setleftmost(linkold[0]);
linkold[0].setparent(left);
right.setleftmost(linkold[3]);
linkold[3].setparent(left);
right.setrightmost(linkold[4]);
linkold[4].setparent(left);
if (isRoot(old)){
parent = new twofourNode();
root = parent;
k = tempold[2].key();
// insert third item of old one into parent node
parent.insertItem(tempold[2]);
i = parent.getlinkadded();
// set children links to split nodes
parent.addchild(right,i);
parent.setleftchild(left, k);
size++;
return;
}
else {
k = tempold[2].key();
parent.insertItem(tempold[2]);
i = parent.getlinkadded();
parent.addchild(right, i);
parent.setleftchild(left, k);
size++;
split(parent(old));
}
}
}
public void fuse(twofourNode old, twofourNode sibling){
if (isRoot(old)){
root = old.getleftmost();
return;
}
else {
int i, j;
boolean left;
item Pitem;
Pitem = ObtainParentMove(old);
sibling.insertItem(Pitem);
i = sibling.getlinkadded();
// copy underflow node's child to its sibling and set the child to new parent: the sibling
sibling.addchild(old.getleftmost(), i);
old.getleftmost().setparent(sibling);
size--;
// remove the item from parent;
old = parent(old);
old.removeItem(Pitem);
j = old.getlinkremoved();
if (!old.underflow()){
old.removechild(j);
return;
}
else{
left = leftsibling(old);
sibling = getnextsibling(old);
if (sibling.size() > 1){
transfer(old, sibling, left);
return;
}
else
fuse(old, sibling);
}
}
}
public void transfer(twofourNode old, twofourNode sibling, boolean leftsibling){
twofourNode parent = parent(sibling);
twofourNode copychild;
int i;
item Pitem = ObtainParentMove(old);
item Sitem;
old.insertItem(Pitem);
if (leftsibling){
Sitem = sibling.removeItem(sibling.getgreatest());
copychild = sibling.removechild(sibling.nolink() - 1);
copychild.setparent(old);
old.addchild(copychild,0);
}
else{
Sitem = sibling.removeItem(sibling.getsmallest());
copychild = sibling.removechild(0);
copychild.setparent(old);
old.addchild(copychild, old.nolink());
}
parent.insertItem(Sitem);
}
}
// Exception Handler
class InvalidKeyException extends RuntimeException{
public InvalidKeyException(String err){
super(err);
}
}
class NullNodeException extends RuntimeException{
public NullNodeException(String err){
super(err);
}
}
class RootNodeException extends RuntimeException{
public RootNodeException(String err){
super(err);
}
}
class EmptyTreeException extends RuntimeException{
public EmptyTreeException(String err){
super(err);
}
}
class InvalidElementException extends RuntimeException{
public InvalidElementException(String err){
super(err);
}
}
class IntegerComparator{
private int int1, int2;
IntegerComparator(){
int1 = 0;
int2 = 0;
}
private void getinteger(Object a, Object b){
if (a == null || b == null)
throw new InvalidElementException("Null Argument!");
int1 = ((Integer) a).intValue();
int2 = ((Integer) b).intValue();
}
public boolean isLessThan(Object a, Object b){
getinteger(a, b);
if (int1 < int2)
return true;
else
return false;
}
public boolean isLessThanOrEqualTo(Object a, Object b){
getinteger(a, b);
if (int1 <= int2)
return true;
else
return false;
}
public boolean isEqualTo(Object a, Object b){
getinteger(a, b);
if (int1 == int2)
return true;
else
return false;
}
public boolean isGreaterThan(Object a, Object b){
getinteger(a, b);
if(int1 > int2)
return true;
else
return false;
}
public boolean isGreaterThanOrEqualTo(Object a, Object b){
getinteger(a, b);
if(int1 >= int2)
return true;
else
return false;
}
public boolean isComparable(Object a){
if (a==null)
return false;
else{
try{ Integer b = (Integer) a; }
catch (ClassCastException e) { return false;}
return true;
}
}
}
class RBitem extends item {
private boolean red;
public RBitem(Object k, Object elem, boolean color){
super(k, elem);
red = color;
}
public RBitem(){
super();
red = false;
}
public boolean isRed() { return red; }
public void makeRed() { red = true; }
public void makeBlack() { red = false; }
public void setColor(boolean color) { red = color; }
}
class RBnode extends RBitem{
private RBnode parent, left, right'
RBnode(){ }
RBnode (Object e, Object k, RBnode u, RBnode v, RBnode w){
setelement(e);
setkey(k);
parent = u;
left = v;
right = w;
}
public RBnode getleft() { return left; }
public RBnode getright() { return right; }
public RBnode getparent() { return parent; }
public void setleft(RBnode v) { left = v; }
public void setright(RBnode v) { right = v; }
public void setparent(RBnode v) { parent = v; }
public RBitem getitem(){ return Item; }
}
class RBTree{
static boolean Red = true;
static boolean Black = false;
private root;
private int size;
private IntegerComparator C;
private int capacity;
RBTree(IntegerComparator c){
root = new RBnode(null, null, null, null, null);
size = 0; // number of internal nodes
C = c;
capacity = 1000;
}
RBTree(){
root = new RBnode(null, null, null, null, null);
size = 0; // number of internal nodes
capacity = 1000;
C = new IntegerComparator();
}
// Query methods
public int size() { return size; }
public boolean isExternal(RBnode p) {
return (p.getleft() == null && p.getright() == null);
}
public boolean isInternal(RBnode p) {
return (p.getleft() != null && p.getright() != null);
}
public boolean isEmpty() { return (size == 0); }
public RBnode root() { return root; }
public isRoot(RBnode p) { return (p == root); }
public RBnode parent(RBnode p) { return p.getparent(); }
public RBnode leftchild(RBnode p) { return p.getleft(); }
public RBnode rightchild(RBnode p) { return p.getright(); }
public RBnode sibling(RBnode v){
RBnode p = parent(v);
RBnode lc = leftchild(p);
if (v == lc)
return rightchild(p);
else
return lc;
}
public RBnode[] children(RBnode p){
RBnode children[] = new RBnode[2];
children[0] = p.getleft();
children[1] = p.getright();
return children;
}
public Object replaceElement(RBnode v, item newItem){
item temp = v.element();
v.setelement(newItem.element(e))
v.setkey(newItem.key(k));
return temp;
}
public void swapElements(RBnode v, RBnode w){
Object temp = w.element();
w.setelement(v.element());
v.setelement(temp);
}
public void expandExternal(RBnode v){
if(isExternal(v)){
v.setleft(new RBnode(null, null, v, null, null));
v.setright(new RBnode(null, null, v, null, null));
}
}
public void removeAboveExternal(RBnode v){
if(isExternal(v)){
RBnode p = parent(v);
RBnode s = sibling(v);
if (isRoot(p)){
s.setparent(null);
root = s;
}
else{
RBnode g = parent(p);
if(p == leftchild(g))
g.setleft(s);
else
g.setright(s);
s.setparent(g);
}
size--;
}
}
// Auxiliary methods
protected void checkKey(Object key) throws InvalidKeyException{
if(!C.isComparable(k))
throw new InvalidKeyException("Key " + k + " is not comparable");
}
protected RBitem findPosition(Object key, RBnode pos){
if (isExternal(pos))
return pos;
else{
Object curKey = pos.key();
if(C.isLessThan(key, curKey))
return findPosition(key, leftchild(pos));
else if(C.isGreaterThan(key, curKey))
return findPosition(key, rightchild(pos));
else
return pos;
}
}
public boolean isPosRed(RBnode v){ return v.isRed(); }
public void setRed(RBnode v) { v.makeRed(); }
public void setBlack(RBnode v) { v.makeBlack(); }
public void setColor(RBnode v, boolean newcolor) { v.setcolor(newcolor); }
public boolean wasParentRed(RBnode v) { return parent(v).isRed(); }
public boolean hasRedChild(RBnode v) {
if (rightchild(v).isRed() || leftchild(v).isRed())
return true;
else
return false;
}
public int height(RBnode v){
int count;
if (isExternal(v))
return 0;
else{
h = 0;
RBnode[] temp = children(v);
int i;
while (i < temp.length)
h = Math.max(h, height(temp));
return h + 1;
}
}
public RBnode tallerchild(RBnode v){
if (height(leftchild(v)) >= height(rightchild(v)))
return leftchild(v);
else
return rightchild(v);
}
public RBnode redchild(RBnode v){
if (rightchild(v).isRed())
return rightchild(v);
else if (leftchild(v).isRed())
return leftchild(v);
else
return null;
}
public void insertItem(Object key, Object element) throws InvalidKeyException{
checkKey(key);
RBnode insPos = root();
do {
insPos = findPosition(key, insPos);
if(isExternal(insPos))
break;
else
insPos = rightchild(insPos);
} while(true);
expandExternal(insPos);
item newItem = new item(key, element);
replaceElement(insPos, newItem);
RBnode posZ = insPos;
replaceElement(posZ, new RBitem(key, element, Red));
if (isRoot(posZ))
posZ.makeBlack();
else
remedyDoubleRed(posZ);
}
public Object removeElement(Object key) throws InvalidKeyException{
Object toReturn;
checkKey(key);
RBnode remPos = findPosition(key, root());
if(isExternal(remPos){ return NO_SUCH_KEY; }
else{
toReturn = remPos.element();
if(isExternal(leftchild(remPos)))
remPos = leftchild(remPos);
else if (isExternal(rightchild(remPos)))
remPos = rightchild(remPos);
else{
RBnode swapPos = remPos;
remPos = rightchild(swapPos);
do
remPos = leftchild(remPos);
while (isInternal(remPos));
swapElements(swapPos, parent(remPos));
}
removeAboveExternal(remPos);
RBnode posR = remPos;
if (toReturn != NO_SUCH_KEY){
if (wasParentRed(posR) || isRoot(posR) || isPosRed(posR))
setBlacke(posR);
else
remedyDouble(Black(posR);
}
return toReturn;
}
protected void remedyDoubleRed(RBnode posZ) {
RBnode posV = parent(posZ);
if (isRoot(posV))
return
if(!isPosRed(sibling(posV))){
posV = restructure(posZ);
setBlack(posV);
setRed(leftchild(posV));
setRed(rightchild(posV));
}
else{
setBlack(posV);
setBlack(sibling(posV));
RBnode posU = parent(posV);
if (isRoot(posU))
return;
setRed(posU);
remedyDoubleRed(posU);
}
}
protected void remedyDoubleBlack(Position posR) {
RBnode posX, posY, posZ;
boolean oldColor;
posX = parent(posR);
posY = sibling(posR);
if(!isPosRed(posY)){
posZ = redChild(posY);
if(hasRedChild(posY)){
oldColor = isPosRed(posX);
posZ = restructure(posZ);
setColor(posZ, oldColor);
setBlack(posR);
setBlack(leftchild(posZ));
setBlack(rightchild(posZ));
return;
}
setBlack(posR);
setRed(posY);
if (!isPosRed(posX)){
if (!isRoot(posX))
remedyDoubleBlack(posX);
return;
}
setBlack(posX);
return;
}
if (posY == rightchild(posX))
posZ = rightchild(posY);
else
posZ = leftchild(posY);
restructure(posZ);
setBlack(posY);
setRed(posX);
remedyDoubleBlack(posR);
}
public restructure (RBnode v){
RBnode a, b, c, x, y, z;
x = v;
y = tallerchild(x);
z = tallerchild(y);
if (y == leftchild(x) && z == leftchild(y)){
a = z;
b = y;
c = x;
swapElements(b, x);
b.setleft(a);
b.setright(c);
c.setleft(b.getright());
b.getright().setparent(c);
return;
}
else if (y == rightchild(x) && z == rightchild(y)){
a = x;
b = y;
c = z;
swapElement(b, x);
b.setleft(a);
b.setright(c);
a.setright(b.getleft());
b.getleft().setparent(a);
return;
}
else if (y == rightchild(x) && z = leftchild(y)){
a = x;
c = y;
b = z;
swapElement(b, x);
b.setleft(a);
b.setright(c);
a.setright(b.getleft());
b.getleft().setparent(a);
c.setleft(b.getright());
b.getright().setparent(c);
return;
}
else if (y == leftchild(x) && z = rightchild(y)){
a = y;
b = z;
c = x;
swapElement(b, x);
b.setleft(a);
b.setright(c);
a.setright(b.getleft());
b.getleft().setparent(a);
c.setleft(b.getright());
b.getright().setparent(c);
return;
}
else
return;
}
}
class convert{
twofourTree mytwofour;
RBTree myRBtree;
convert(){
mytwofour = new twofourTree(1000);
myRBtree = new RBTree(1000);
}
public toTwoFour(RBtree tree, RBnode p1, twofourNode p2){
if (p1.isRed()){
twofourNode parent = p2.getparent();
parent.insertItem(p1);
int i = parent.getaddchild();
twofourNode ltemp = new twofourNode(1, parent);
twofourNode rtemp = new twofourNode(1, parent);
ltemp.insertItem(leftchild(p1));
rtemp.insertItem(rightchild(p1));
parent.addchild(ltemp, i - 1);
parent addchild(rtemp, i);
}
else{
p2 = new twofourNode();
p2.insertItem(p1);
}
toTwoFour(tree, p1.leftchild(), p2.getleftmost());
toTwoFour(tree, p1.rightchild(), p2.getrightmost());
}
} [/PHP] |
|
IP卡
狗仔卡
楼主
显身卡