TwoThreetree.java

[Previous page] [TreeGUI.java] [Mystack.java] [NodeGUI.java]

/* *************************************************************************

*** Filename:TwoThreetree.java
Associated java files: NodeGUI.java, Mystack.java, TreeGUI.java
Compiler : JDK 1.1.4

*** 과 목 : 화일처리론
*** 담당교수 : 박영배

*** 명지대학교 컴퓨터공학과 3학년 민정식
*** E-Mail : mxxk@uriel.net
*** Execute on(Refe. to) http://www.uriel.net/~mxxk/File/btree.html
*** **********************************************************************/

import java.util.Stack;

public class TwoThreetree {
node23 tree[];
int y, a, t, stackindex, size;
Mystack parentstack;

static final int NIL = -1;
static final int SUCCESS = 1;
static final int FAIL = 0;

// Constructor
public TwoThreetree (int msize) {
    tree = new node23[msize + 1];
    size = msize;
    t = NIL;
    stackindex = 1;

    for (int i = 1; i <= size; i++) {
      tree[i] = new node23();
      tree[i].Rdata = tree[i].Ldata = 0;
      tree[i].left = NIL;
      tree[i].middle = NIL;
      tree[i].right = NIL;
    }
}

public boolean Insert23 (int key) {

    parentstack = new Mystack(size/2);
    int p; boolean NotDone;
    if (t == NIL) {
      NewRoot(t, key, NIL);
      return true;
    }
    else {
      p = FindNode(key);
      if (p == NIL) {
System.out.println("Insert23(), key is already in the tree");
return false;
      }
      else { // key is not in the tree
a = NIL; NotDone = true; y = key;

while (NotDone) {
   if (tree[p].Rdata == 0) {
     PutIn(p, y, a);
     NotDone = false;
   }
   else {
     Split(p, y, a);
     if (p == t) {
       NewRoot(t, y, a);
       NotDone = false;
     }
     else
       p = parentstack.pop();
   }
}
parentstack.clear();
      }
      return true;
    }
}
public boolean Search23(int key) {
    int p;
    boolean NotDone;
    if (t == NIL) {
      return false;
    }
    else {
      p = t; NotDone = true;
      while((NotDone) && (p != NIL)) {
if((tree[p].Ldata == key) || (tree[p].Rdata == key))
   NotDone = false;
else if(tree[p].Ldata > key)
   p = tree[p].left;
else if(tree[p].Ldata < key) {
   if(tree[p].Rdata == 0)
     p = tree[p].middle;
   else {
     if(tree[p].Rdata < key)
       p = tree[p].right;
     else
       p = tree[p].middle;
   }
}
else
   ;
      }

      if(NotDone == true) {
return false;
      }
      else
return true;
    }
}

public void Split (int p, int key, int b) {
int x;
x = stackindex; stackindex++;

    // 1) 키가 가장클경우
    if (tree[p].Rdata < key) {
      tree[x].Ldata = key;
      tree[x].middle = b;
      tree[x].left = tree[p].right;
      y = tree[p].Rdata;
    }
    else {
      tree[x].Ldata = tree[p].Rdata;
      tree[x].middle = tree[p].right;
      // 2) 키가 중간값일 경우
      if (tree[p].Ldata < key ) {
tree[x].left = b;
y = key;
      }
      // 3) 키가 제일 작은경우
      else {
tree[x].left = tree[p].middle;
y = tree[p].Ldata;
tree[p].Ldata = key;
tree[p].middle = b;
      }
    }
    tree[p].Rdata = 0;
    tree[p].right = NIL;
    a = x;
}

public void PutIn (int p, int key, int k) {
    if (tree[p].Ldata < key) {
      tree[p].Rdata = key;
      tree[p].right = k;
    }
    else {
      // moving element and pointer
      tree[p].Rdata = tree[p].Ldata;
      tree[p].right = tree[p].middle;
      tree[p].Ldata = key;
      tree[p].middle = k;
    }
}

public int FindNode (int key) {
int p;
p = t;

while(p != NIL) {

      if((tree[p].Ldata == key) || (tree[p].Rdata == key)) {
parentstack.push(p);
return NIL;
      }
      if(tree[p].Ldata > key) {
parentstack.push(p); // Root에서 'p'로의 경로를 유지한다
p = tree[p].left;
      }
      else if((tree[p].Ldata < key) && (tree[p].Rdata == 0)) {
parentstack.push(p);
p = tree[p].middle;
      }
      else if((tree[p].Ldata < key) && (tree[p].Rdata > key)) {
parentstack.push(p);
p = tree[p].middle;
      }
      else {
parentstack.push(p);
p = tree[p].right;
      }
    }
    return (parentstack.pop());
}

public void NewRoot( int x, int k, int z) {
    int p;
    p = stackindex; stackindex++;
    tree[p].Ldata = k;
    tree[p].left = x;
    tree[p].middle = z;
    t = p;
}

public boolean Delete23 (int key) {
    int p, q, r;

    boolean NotDone = true;
    parentstack = new Mystack(size/2);

    if((p = FindNode(key)) != NIL) {
      System.out.println("Delete23(), key:" + key + " is not in the tree");
      return false;
    }
    else {
      p = parentstack.pop();

      if(tree[p].left != NIL) {// `p' 가 non-leaf노드를 가르킴

p = FindLeafnode(p, key);// 'p'는 이젠 leaf node를 포인팅함
if (tree[p].Rdata == 0) // 내부노드대신 리프노드를 삭제함
   key = tree[p].Ldata;
else
   key = tree[p].Rdata;
      }

      if(key == tree[p].Ldata)   // 리프노드에 있는 원소를 삭제
if(tree[p].Rdata != 0) {
   tree[p].Ldata = tree[p].Rdata;
   tree[p].Rdata = 0;
   NotDone = false;
}
else
   tree[p].Ldata = 0;
      else {
tree[p].Rdata = 0;
NotDone = false;
      }

if (tree[t].Ldata == 0) // 이젠 빈트리일때
NotDone = false;

while (NotDone == true) {

r = parentstack.pop();     // 로테이트와 결합을위한 포인터 셋팅
if(tree[r].middle == p)
   q = tree[r].left;
else
   q = tree[r].middle;

if(tree[q].Rdata != 0) {
   Rotate(p, q, r);
   NotDone = false;
}
else {
   Combine(p, q, r);
   if(tree[r].Ldata != 0)
     NotDone = false;
   else {
     if(r == t) {
       if (tree[r].left == p)
t = p;
       else
t = q;
       NotDone = false;
     }
     else
       p = r;
   }
}
      }
      parentstack.clear();
    }
    return true;
}

public int FindLeafnode(int ptr, int key) {

    int p, q;
    boolean Lnode;

    p = ptr;
    if(tree[ptr].Ldata == key) {
      parentstack.push(p);
      p = tree[p].left;
      Lnode = true;
    }
    else {
      parentstack.push(p);
      p = tree[p].middle;
      Lnode = false;
    }

    q = p;
    while(p != NIL) {
      if(tree[p].Rdata == 0) {
q = p;
parentstack.push(p);
p = tree[p].middle;
      }
      else {
q = p;
parentstack.push(p);
p = tree[p].right;
      }
    }

    if(tree[q].Rdata != 0) {
      if(Lnode)
tree[ptr].Ldata = tree[q].Rdata;
      else
tree[ptr].Rdata = tree[q].Rdata;
    }
    else
      if(Lnode)
tree[ptr].Ldata = tree[q].Ldata;
      else
tree[ptr].Rdata = tree[q].Ldata;
    return (parentstack.pop());
}

public void Rotate(int p, int q, int r) {
    // 세가지 경우를 갖는다,
    // 1) `p' 는 'r'의 왼쪽자식 노드이다
    // 2) `p' 는 'r'의 중앙자식 노드이다
    // 3) 'p' 는 'r'의 오른쪽자식 노드이다

    // case #1
    if(p == tree[r].left) {
      tree[p].Ldata = tree[r].Ldata;
      tree[p].middle = tree[q].left;
      tree[r].Ldata = tree[q].Ldata;
      tree[q].Ldata = tree[q].Rdata;
      tree[q].left = tree[q].middle;
      tree[q].middle = tree[q].right;
    }

    // case #2
    else if(p == tree[r].middle) {
      tree[p].Ldata = tree[r].Ldata;
      tree[p].middle = tree[p].left;
      tree[p].left = tree[q].right;
      tree[r].Ldata = tree[q].Rdata;
    }

    // case #3
    else {
      tree[p].Ldata = tree[r].Rdata;
      tree[p].middle = tree[p].left;
      tree[p].left = tree[q].right;
      tree[r].Rdata = tree[q].Rdata;
    }
    tree[q].Rdata = 0;
    tree[q].right = NIL;
}

public void Combine(int p, int q, int r) {

    // case #1
    if (p == tree[r].left) {
      tree[p].Ldata = tree[r].Ldata;
      tree[p].Rdata = tree[q].Ldata;
      tree[p].middle = tree[q].left;
      tree[p].right = tree[q].middle;

      Dispose(tree[r].middle);
      tree[r].Ldata = tree[r].Rdata;
      tree[r].middle = tree[r].right;
    }

    // case #2
    else if (p == tree[r].middle) {
      tree[q].Rdata = tree[r].Ldata;
      tree[q].right = tree[p].left;
      tree[r].Ldata = tree[r].Rdata;

      Dispose(tree[r].middle);
      tree[r].middle = tree[r].right;
    }

    // case #3
    else {
      tree[q].Rdata = tree[r].Rdata;
      tree[q].right = tree[p].left;
      Dispose(tree[r].right);
    }
    tree[r].Rdata = 0;
    tree[r].right = NIL;
}

public void Dispose(int ptr) {
    tree[ptr].Ldata = 0;
    tree[ptr].Rdata = 0;
    tree[ptr].right = NIL;
    tree[ptr].middle = NIL;
    tree[ptr].left = NIL;

}

public String print(int level, int ptr) {
    StringBuffer tmp = new StringBuffer();
    String p = "";
    if(ptr == NIL){
      return p;
    }

    for(int i = 0; i < level; i++)
      tmp.append("\t.");
    tmp.append("\t" + tree[ptr].Ldata + "," + tree[ptr].Rdata +"\n");
    tmp.append(print(level+1, tree[ptr].left));
    tmp.append(print(level+1, tree[ptr].middle));
    tmp.append(print(level+1, tree[ptr].right));

return tmp.toString();
}

public boolean isempty()
{
   if (t == NIL)
     {
       System.out.print("true\n");
       return true;
     }
   else
     {
       System.out.print("false\n");
       return false;
     }
}

public void empty()
{
   t = NIL;
   stackindex =1;
   }

public void cons(int i, TwoThreetree l, TwoThreetree r)
{
   int lpos = stackindex+1;
   int rpos = stackindex+2;
   NewRoot(lpos,i,rpos);
   tree[lpos] = l.tree[l.t];
   tree[rpos] = r.tree[r.t];
   stackindex+=2;

}

   public void cons2(int i, int j, TwoThreetree l, TwoThreetree m, TwoThreetree r)
{
   int lpos = stackindex+1;
   int mpos = stackindex+2;
   int rpos = stackindex+3;
   NewRoot(lpos,i,mpos);
   tree[t].Rdata = j;
   tree[t].right = rpos;
   tree[lpos] = l.tree[l.t];
   tree[mpos] = m.tree[m.t];
   tree[rpos] = r.tree[r.t];
   stackindex+=3;

}

// pre: 루트에서 한 Item을 갖는 한트리를 취함
// post: 루트에서 Data Item 반환
public int root()
{
    if ((t == NIL) || (tree[t].Rdata > 0)) // 비어있거나 루트에서 두개의Item일 경우
    {
      System.out.print("error\n");
      return -1;
     }
   else // 루트에서 하나의 Item일 경우
     {
      System.out.print(tree[t].Ldata+"\n");
      return tree[t].Ldata;
     }
}

// pre: 루트에서 한 Item을 갖는 한트리를 취함
// post: 루트에서 Data Item 반환
public int first()
{
    if ((t == NIL) || (tree[t].Rdata ==0)) // 비어있거나 루트에서 한개의Item일 경우
    {
      System.out.print("error\n");
      return -1;
     }
   else // 루트에서 두개의 아이템일경우
     {
      System.out.print(tree[t].Ldata+"\n");
      return tree[t].Ldata; // 루트에서 첫번째 아이템 반환
     }
}

// pre: 루트에서 두개의 Item을 갖는 한트리를 취함
// post: 루트에서 두번빼Item 반환
public int second()
{
    if ((t == NIL) || (tree[t].Rdata ==0)) // 빈트리이거나 루트에서 하나의 아이템만 있는경우
    {
      System.out.print("error\n");
      return -1;
     }
   else // two items at its root
     {
      System.out.print(tree[t].Rdata+"\n");
      return tree[t].Rdata; // 루트에서 첫번째 아이템 반환
     }
}

// returns the left subtree
public void left()
{
   if (t == NIL) // 빈트리이면 에러출력
      System.out.print("error\n");
   else
    System.out.print(print(0,tree[t].left)); // 왼쪽 서브트리를 보여줌
}

// 오른쪽 서브트리 반환
public void right()
{
   if (t == NIL) // e빈트리이면 에러출력
      System.out.print("error\n");
   else if (tree[t].Rdata ==0) // 만일 부모에서 하나의 아이템이라면 중간트리는 오른쪽 트리다
      System.out.print(print(0,tree[t].middle)); // 오른쪽 서브와 상등하는 서브트리 display
   else
      System.out.print(print(0,tree[t].right)); // 오른쪽 서브트리 display
}

// returns the middle subtree
public void middle()
{
   if (t == NIL || tree[t].Rdata == 0) // 비어있거나 1아이템노드이면 오류제공
      System.out.print("error\n");
   else
      System.out.print(print(0,tree[t].middle)); // 중간 서브트리 display
}

// 1이나 2반환
public int numvals()
{
    if (t == NIL) // 빈트리
    {
      System.out.print("error\n");
      return -1;
     }
    else if (tree[t].Rdata == 0) // 1이면 1리턴
      {
      System.out.print(1+"\n");
      return 1;
      }
   else // 루트에서 2개의 아이템이면 2를 리턴
     {
      System.out.print(2+"\n");
      return 2;
     }
}

   public static void main (String args[]) {

     // 5 trees
     TwoThreetree treea = new TwoThreetree(10);
     TwoThreetree treeb = new TwoThreetree(10);
     TwoThreetree treec = new TwoThreetree(10);
     TwoThreetree treed = new TwoThreetree(10);
     TwoThreetree sometree = new TwoThreetree(10);

     treeb.Insert23(3); // construct a tree
     treec.Insert23(12);
     treed.Insert23(20);

     // testing isempty, root, first, second left rigth middle
     // and testing numvals on empty
     treea.empty();
     System.out.print("isempty empty = ");
     treea.isempty();
     System.out.print("root empty = ");
     treea.root();
     System.out.print("first empty = ");
     treea.first();
     System.out.print("second empty = ");
     treea.second();
     System.out.print("left empty = ");
     treea.left();
     System.out.print("right empty = ");
     treea.right();
     System.out.print("middle empty = ");
     treea.middle();
     System.out.print("numvals empty = ");
     treea.numvals();

     // testing isempty, root, first, second left rigth middle
     // and testing numbals on (cons i l r)
     treea.cons(5,treeb, treec);
     System.out.print("\n\nDisplay of tree: cons(5, treeb, treec)\n");
     System.out.print(treea.print(0,treea.t));
     System.out.print("\nisempty (cons 5 treeb treec) = ");
     treea.isempty();
     System.out.print("root (cons 5 treeb treec) = ");
     treea.root();
     System.out.print("first (cons 5 treeb treec) = ");
     treea.first();
     System.out.print("second (cons 5 treeb treec) = ");
     treea.second();
     System.out.print("left (cons 5 treeb treec) = ");
     treea.left();
     System.out.print("right (cons 5 treeb treec) = ");
     treea.right();
     System.out.print("middle (cons 5 treeb treec) = ");
     treea.middle();
     System.out.print("numvals (cons 5 treeb treec) = ");
     treea.numvals();

     // testing isempty, root, first, second left rigth middle
     // and testing numbals on (cons2 i j l m r)
     treea.cons2(5,18,treeb, treec,treed);
     System.out.print("\n\nDisplay of tree: cons(5,18,treeb,treec,treed)\n");
     System.out.print(treea.print(0,treea.t));
     System.out.print("\nisempty (cons2 5 18 treeb treec treed) = ");
     treea.isempty();
     System.out.print("root (cons2 5 18 treeb treec treed) = ");
     treea.root();
     System.out.print("first (cons2 5 18 treeb treec treed) = ");
     treea.first();
     System.out.print("second (cons2 5 18 treeb treec treed) = ");
     treea.second();
     System.out.print("left (cons2 5 18 treeb treec treed) = ");
     treea.left();
     System.out.print("right (cons2 5 18 treeb treec treed) = ");
     treea.right();
     System.out.print("middle (cons2 5 18 treeb treec treed) = ");
     treea.middle();
     System.out.print("numvals (cons2 5 18 treeb treec treed) = ");
     treea.numvals();

}

class node23 {
int Ldata, Rdata;
int right, middle, left;
}

[Previous page] [TreeGUI.java] [Mystack.java] [NodeGUI.java]