BST dan AVL Tree Java
package tree2;
import java.util.Stack;
class Node{
public int data,height;
public Node left;
public Node right;
public Node() // constructor-1
{
this.data=0;
height = 0;
right=left=null;
}
public Node(int data) // constructor-2
{
this.data=data;
right=left=null;
height = 0;
}
}
class BstClass
{
private Node root;
public BstClass()
{
root = null;
}
public boolean isEmpty()
{
return(root==null);
}
public void makeEmpty(){
root = null;
}
public void insert(int data_masukan)
{
root = insert( data_masukan, root );
}
public int Height(){
return height(root);
}
private int height (Node data)
{
if (data == null)
return -1;
else {
return Math.max(height(data.left)+1,height(data.right)+1);
}
}
private int max(int lhs, int rhs){
return lhs > rhs ? lhs : rhs;
}
private Node insert( int data_masukan, Node t ) //insert nilai bst
{
if( t == null )
return new Node(data_masukan);
else {
if( data_masukan<t.data )
{
t.left = insert( data_masukan, t.left );
}
else if(data_masukan>t.data )
{
t.right = insert( data_masukan, t.right );
}
return t;
}
}
public void updateAVL(int dataBaru, int dataYangAda){ //mengganti nilai yang ada
Delete(dataYangAda);
AVLinsert(dataBaru);
}
public void AVLinsert(int data_masukan)
{
root = AVLinsert( data_masukan, root );
}
private Node AVLinsert( int data_masukan, Node t ){ //mengatur avl
if( t == null )
return new Node(data_masukan);
else {
if( data_masukan<t.data )
{
t.left = AVLinsert( data_masukan, t.left );
if (height(t.left)-height(t.right)==2)
if (data_masukan<t.left.data)
t = rotateWithLeftChild(t);
else
t = doubleWithLeftChild(t);
}
else if(data_masukan>t.data ){
t.right = insert(data_masukan, t.right);
if (height(t.right)-height(t.left)==2)
if (data_masukan>t.right.data)
t = rotateWithRightChild(t);
else
t = doubleWithRightChild(t);
else
{
t.height = max (height(t.left),height(t.right))+1;
}
}
}return t;
}
private Node rotateWithRightChild(Node k1){
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = max (height(k2.right),k1.height) +1;
return k2;
}
private Node rotateWithLeftChild(Node k2){
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = max( height( k1.left ), k2.height ) + 1;
return k1;
}
private Node doubleWithLeftChild(Node k3){
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}
private Node doubleWithRightChild(Node k4){
k4.right = rotateWithLeftChild( k4.right );
return rotateWithRightChild( k4 );
}
public void InOrder(){
System.out.print("InOrder : ");
InOrder(root);
System.out.println(" ");
}
private void InOrder(Node t){
if (t!=null){
InOrder(t.left);
System.out.print(t.data+" ");
InOrder(t.right);
}
}
public float rata(){
return (float)jumData()/(float)jumNode();
}
public int jumNode(){
return (jumNode(root));
}
private int jumNode(Node t){
if (t==null)
return 0;
else
return (1+jumNode(t.left)+jumNode(t.right));
}
public int jumData(){
return (jumData(root));
}
private int jumData(Node t){
if (t==null)
return 0;
else
return (t.data+jumData(t.left)+jumData(t.right));
}
public int jumDaun(){
return(jumDaun(root));
}
private int jumDaun(Node t){
if (t==null){
return 0;
} else {
if ((t.right==null) && (t.left==null)){
return 1;
} else {
return (jumDaun(t.left)+jumDaun(t.right));
}
}
}
public void Delete(int x){
remove(root,x);
}
private boolean IsDaun(Node t){
return((t.left==null) && (t.right==null));
}
private Node remove(Node t,int x) {
if (t!=null){
if (t.data==x){
if ((t.left==null) && (t.right==null)){
if (root==t){
root=null;
}
t=null;
} else {
if (t.left!=null){
Node parent=t;
Node besar=t.left;
while (besar.right!=null){
parent=besar;
besar =besar.right;
}
t.data=besar.data;
besar=remove(besar,besar.data);
if (t!=parent)
parent.right=besar;
else
parent.left=besar;
} else {
Node parent=t;
Node kecil=t.right;
while (kecil.left!=null){
parent=kecil;
kecil =kecil.left;
}
t.data=kecil.data;
kecil=remove(kecil,kecil.data);
if (t!=parent)
parent.left=kecil;
else
parent.right=kecil;
}
}
}else {
if (x<t.data)
t.left=remove(t.left,x);
else
t.right=remove(t.right,x);
}
}
return t;
}
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int kosong = 32;
int counter=1;
int temp1=0;
boolean kolomkosong = false;
boolean baris_pertama=true;
while(kolomkosong==false)
{
Stack localStack = new Stack();
kolomkosong = true;
if(baris_pertama==false)
{
for(int i=1;i<=counter/2;i++)
{
for(int j=1;j<kosong*2+1;j++)
System.out.print(" ");
System.out.print("|");
if(i!=counter)
{
for(int j=1;j<kosong*2;j++)
System.out.print(" ");
}
}
System.out.println("");
for(int i=1;i<=counter*2;i++)
{
if(i%4==2||i%4==3)
{
for(int j=1;j<=kosong;j++)
System.out.print("-");
}
else
{
for(int j=1;j<kosong+1;j++)
System.out.print(" ");
}
}
System.out.println("");
for(int i=1;i<=counter;i++)
{
for(int j=1;j<kosong+1;j++)
System.out.print(" ");
System.out.print("|");
if(i!=counter)
{
for(int j=1;j<kosong;j++)
System.out.print(" ");
}
}
System.out.println("");
}
for(int j=0; j<kosong; j++)
System.out.print(" ");
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.data);
localStack.push(temp.left);
localStack.push(temp.right);
if(temp.left != null || temp.right != null)
kolomkosong = false;
temp1++;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
temp1++;
}
if(temp1<counter)
{
for(int j=0; j<kosong*2-2; j++)
System.out.print(" ");
}
}
temp1=0;
counter=counter*2;
System.out.println();
kosong /= 2;
baris_pertama=false;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
}
}
}
package tree2;
public class tes {
public static void main(String[] args) {
BstClass x = new BstClass();
x.AVLinsert(50);
x.AVLinsert(40);
x.AVLinsert(30);
// x.AVLinsert(20);
// x.AVLinsert(10);
// x.AVLinsert(5);
x.AVLinsert(75);
x.AVLinsert(80);
x.AVLinsert(85);
x.updateAVL(30, 50);
// x.AVLinsert(90);
x.displayTree();
// x.InOrder();
}
}
Tidak ada komentar:
Posting Komentar