Scribd
Upload
3 views11 pages

Weak AVL Tree Map Implementation

script of weak all map java

Uploaded by

Diptanshu Rajan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views11 pages

Weak AVL Tree Map Implementation

script of weak all map java

Uploaded by

Diptanshu Rajan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

package col106.assignment4.

WeakAVLMap;
import [Link];
import [Link];
import [Link];

public class WeakAVLMap<K extends Comparable,V> implements


WeakAVLMapInterface<K,V>{

public int rotater=0;


public Node<K,V> root;
public Node<K, V> current;
public WeakAVLMap(){
root = null;

public class Node<K,V>{


K key;
V value;
int rank;
Node<K,V> parent;
Node<K,V> left;
Node<K,V> right;

public Node(K key, V value) {

if(key==null && value ==null){


[Link] = null;
[Link] = null;
[Link]=0;
[Link]=null;
[Link]=null;
}

else{
[Link] = key;
[Link] = value;
[Link]=1;
[Link]=new Node<K,V>(null,null);
[Link]=new Node<K,V>(null,null);
}

}
}

public int rank_diff(Node child){


return ([Link]);
}
public void left_left(Node x){

Node mid = [Link];


Node top = [Link];
Node sup_top = null;

int breaker=0;
if([Link]!=null) sup_top = [Link];
else breaker=1;

[Link]--;
if(breaker==0){
if(sup_top.left==top) sup_top.left=mid;
if(sup_top.right==top) sup_top.right=mid;
}
[Link]=sup_top;

[Link]=[Link];
[Link]=top;

[Link] =top;
[Link] = mid;

if(breaker==1) root = mid;

rotater++;
}

public void left_right(Node x){


Node mid = [Link];
Node top = [Link];
Node sup_top = null;

int breaker=0;
if([Link]!=null) sup_top = [Link];
else breaker=1;

[Link]++;
[Link]--;
[Link]--;
if(breaker==0){
if(sup_top.left==top) sup_top.left=x;
if(sup_top.right==top) sup_top.right=x;
}

[Link] = sup_top;

[Link]=[Link];
[Link]=mid;

[Link]=[Link];
[Link]=top;

[Link]=mid;
[Link]=top;

[Link]=x;
[Link]=x;

if(breaker==1) root = x;

rotater = rotater+2;
}

public void right_right(Node x){


Node mid = [Link];
Node top = [Link];
Node sup_top = null;

int breaker=0;
if([Link]!=null) sup_top = [Link];
else breaker=1;

[Link]--;
if(breaker==0){
if(sup_top.left==top) sup_top.left=mid;
if(sup_top.right==top) sup_top.right=mid;
}
[Link] = sup_top;

[Link]=[Link];
[Link]=top;

[Link]=top;
[Link]=mid;

if(breaker==1) root = mid;

rotater++;
}

public void right_left(Node x){

Node mid = [Link];


Node top = [Link];
Node sup_top = null;

int breaker=0;
if([Link]!=null) sup_top = [Link];
else breaker=1;

[Link]++;
[Link]--;
[Link]--;
if(breaker==0){
if(sup_top.left==top) sup_top.left=x;
if(sup_top.right==top) sup_top.right=x;
}

[Link]=sup_top;

[Link]=[Link];
[Link]=top;

[Link]=[Link];
[Link]=mid;

[Link]=top;
[Link]=mid;

[Link]=x;
[Link]=x;

if(breaker==1) root = x;

rotater = rotater+2;
}
public void rearange(Node x){
int my_count=0;
Node store = x;
Node sibling =null;
Node parent = null;
int checker = rank_diff(x);
int del_check=0;
if(toDelete!=null){

if([Link]==null) del_check=1;
else del_check = rank_diff(toDelete);
}

if(checker==0 || del_check > 0 ){


while(rank_diff(x)==0 || del_check!=0){

parent = [Link];

if([Link]==x) {
sibling = [Link];
[Link]=parent;
}
else{
sibling = [Link];
[Link]=parent;
}

if(rank_diff(sibling)==1 && del_check == 0){


del_check=0;
[Link]++;
x=[Link];
my_count++;
if([Link]==null) {
is_ext(x);
if(del_check==0){
remap_delete([Link]);
remap_delete([Link]);
}
break;
}

else {
x=store;
for(int i=0;i<my_count-1;i++){
x=[Link];
}
store=x;
Node mid = [Link];
Node top = [Link];
Node sup_top = null;

Node store_mid = mid;


Node store_top = top;

int breaker=0;
if([Link]!=null) sup_top = [Link];
else breaker=1;

//LEFT LEFT CASE


if([Link]==x && [Link]==mid){
if(del_check!=0) {
[Link]++;
//[Link]--;
}
left_left(x);

is_ext(store);
is_ext(store_mid);
is_ext(store_top);

if([Link]==null) root=mid;
}

//LEFT RIGHT CASE


else if([Link]==x && [Link]==mid){
if(del_check!=0) {
[Link]++;
[Link]--;
}
left_right(x);
is_ext(store);
is_ext(store_mid);
is_ext(store_top);

if([Link]==null) root=x;
}

//RIGHT RIGHT CASE


else if([Link]==x && [Link]==mid){
if(del_check!=0) {
[Link]++;
//[Link]--;
}

right_right(x);

is_ext(store);
is_ext(store_mid);
is_ext(store_top);

if([Link]==null) root=mid;
}

//RIGHT LEFT CASE


else if([Link]==x && [Link]==mid){
if(del_check!=0) {
[Link]++;
[Link]--;
}
right_left(x);

is_ext(store);
is_ext(store_mid);
is_ext(top);

if([Link]==null) root=x;
}

break;
}
}

}
public void is_ext(Node n){
if([Link]==null || [Link]==null) return;
if([Link]==null && [Link]==null) [Link]=1;
}
public V put(K key, V value){

Node<K, V> toInsert = new Node<K, V>(key, value);


V old_value = null;
if(root==null){
root = toInsert;
[Link]=null;
current = root;
return null;
}

current = root;

while(true){

if([Link](key)){
old_value=[Link];
[Link]=value;
return old_value;
}

else if([Link]([Link])>0){
if([Link]==null){
[Link] = toInsert;
[Link]=current;

rearange(toInsert);
return null;
}
else current = [Link];
}
else if([Link]([Link])<0){
if([Link]==null){
[Link] = toInsert;
[Link]=current;

rearange(toInsert);
return null;
}
else current = [Link];
}
}

}
public Node toDelete;
public V remove(K key){

Node x=root;
V to_return=null;
while([Link]!=null){

if([Link](key)){
toDelete=x;
}

if([Link]([Link])<0) x=[Link];
else x=[Link];
}

if (toDelete==null || [Link]==null) return to_return;


to_return = (V)[Link];

//BOTH EXTERNAL NODES OF toDelete


if([Link]==null && [Link]==null){

if(toDelete==root){
to_return = (V)[Link];
root=null;
toDelete = null;
return to_return;
}
else{
to_return = (V)[Link];

[Link] = null;
[Link] = null;
[Link]=0;
[Link]=null;
[Link]=null;

Node toDelete_parent = [Link];


is_ext(toDelete_parent);

remap_delete(toDelete);
remap_delete(toDelete_parent);

toDelete = null;
return to_return;
}
}

//ONLY one EXTERNAL NODE of toDelete


else if([Link]==null || [Link]==null){

Node internal = null;


if([Link]==null) internal = [Link];
else internal = [Link];

if([Link]==null){
root = internal;
toDelete = null;
return to_return;
}
else{
if(toDelete==[Link]){
[Link]=internal;
[Link]=[Link];
}
else{
[Link]=internal;
[Link]=[Link];
}
to_return = (V)[Link];
}
is_ext(internal);
remap_delete(internal);
remap_delete([Link]);

toDelete = null;
return to_return;
}

//BOTH INTERNAL NODE of toDelete


else{

Node temp = [Link];

if([Link]==null){

[Link]=[Link];
[Link]=[Link];
[Link]=[Link];
[Link]=toDelete;
is_ext(toDelete);
is_ext([Link]);
remap_delete([Link]);
remap_delete(toDelete);
remap_delete([Link]);

toDelete = null;

return to_return;
}

else{
while([Link]!=null){
temp=[Link];
}

[Link]=[Link];
[Link]=[Link];

[Link]=[Link];
[Link]=[Link];

is_ext([Link]);
remap_delete([Link]);
remap_delete([Link]);
remap_delete([Link]);

toDelete = null;
return to_return;

}
}

public void remap_delete(Node x){


if(x==root) return;
if(rank_diff(x)==2) return;

if(rank_diff(x)>2){

while(rank_diff(x)!=2){

Node sibling = null;


if(x==[Link]) sibling = [Link];
else sibling = [Link];

if(rank_diff(sibling)==2){
[Link]--;
x=[Link];
if([Link]==null) break;
}
else if(rank_diff(sibling)==1){
Node child1=[Link];
[Link]=sibling;
Node child2=[Link];
[Link]=sibling;

if(rank_diff(child1)==2 && rank_diff(child2)==2){

[Link]--;
[Link]--;
x=[Link];
if([Link]==null) {
is_ext(x);
is_ext(sibling);
break;
}
}

else if(rank_diff(child1)==1 &&


rank_diff(child2)==1){

Node t = null;

if(sibling==[Link]) t = child1;
else t = child2;

Node t_mid = [Link];


Node t_top = t_mid.parent;

rearange(t);

is_ext(t);
is_ext(t_mid);
is_ext(t_top);

break;
}
else if(rank_diff(child1)==1 ||
rank_diff(child2)==1){

Node t = null;
if(rank_diff(child1)==1) t = child1;
else t = child2;

Node t_mid = [Link];


Node t_top = t_mid.parent;

rearange(t);

is_ext(t);
is_ext(t_mid);
is_ext(t_top);

break;
}

}
}

}
return;

}
public V get(K key){

Node x=root;

while([Link]!=null){

if([Link](key)){
return (V)[Link];
}

if([Link]([Link])<0) x=[Link];
else x=[Link];
}
return null;
}
public Vector in_order;
public void ranger(Node x,K key1, K key2){

toDelete=null;
if([Link]==null) return;

if([Link]([Link])<0){

ranger([Link],key1,key2);
}

if([Link]([Link])<=0 && [Link]([Link])>=0){

in_order.add([Link]);

if([Link]([Link])>0){

ranger([Link],key1,key2);
}

return;
}

public Vector<V> searchRange(K key1, K key2){

in_order = new Vector();


ranger(root,key1,key2);
if(in_order.size()==0){
in_order.add(null);
}
return in_order;
}

public int rotateCount(){


return rotater;
}

public int real_height(Node n){


if(n==null) return 0;
if([Link]==null) return 0;
else{
return 1+max(real_height([Link]),real_height([Link]));
}
}

public int max(int p, int q){


if(p>q) return p;
else return q;
}

public int getHeight(){


int ans = real_height(root);
return ans;
}

public Vector<K> BFS(){

Vector ans = new Vector();


Queue <Node <K,V>> Q = new LinkedList <Node <K,V>> ();

Node<K, V> x = root;


[Link](x);
while([Link]()>0) {

x=[Link]();
if(x==null) break;
[Link]([Link]);
//[Link]([Link]+" "+[Link]);
if([Link]!=null && [Link]!=null) {

[Link]([Link]);
[Link]([Link]);
}

else if([Link]!=null) {

[Link]([Link]);
}
else if([Link]!=null) {

[Link]([Link]);
}

}
return ans;
}
}

You might also like