AVL tree based Dictionary

afas87 0 Newbie Poster

15 Years Ago

hi,,
attached a java code for a simple dictionary based on AVL tree principle,,
the 3 files are:
Node.java: the base class
AVL.java:the function
and Menu:the menu class of the programe

regards

java

AVL.java (7.59 KB)

package avl;
import javax.swing.*;

public class AVL {
	Node root;
	int count;

//make  the tree empty
public void makeEmpty(){
	root=null;
	count=0;
}

//Find function that rerun the node of the specified word
public Node find(String element,Node root){
	while( root != null )
        if( element.compareTo( root.element ) < 0 )
            root = root.left;
        else if( element.compareTo( root.element ) > 0 )
            root = root.right;
        else
            return root;    // Match

    return null;   // No match
}

//FindMin function taht rerun the Node of the first of the Dictionary.. the most left node
public Node findMin(Node t){
    if( t == null )
        return t;

    while( t.left != null )
        t = t.left;
    return t;
}

//Height function that return the height of the Node or -1 if the Node equlas null
public int height( Node t )
{
    return t == null ? -1 : t.height;
}

//Single Right Rouatate 
public Node SRR(Node k1){
	Node tempParent = k1.parent;
	Node k2 = k1.left; //k2 will be in position of k1
	{if(tempParent!=null&&(tempParent.left==k1))
		tempParent.left=k2;
	 else if(tempParent!=null&&(tempParent.right==k1))
		tempParent.right=k2;}
	
    k1.left = k2.right;
    if(k2.right!=null)
    k2.right.parent=k1;
    k2.right = k1;
    k2.parent=k1.parent;
    k1.parent=k2;
	//set the height of the rearranged Nodes
    k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
    k2.height = Math.max( height( k2.left ), k1.height ) + 1;
    
	if(k1==root)
		root=k2;   //if k1 was the root, k2 will be the route
    return k2;	
}

//Single Left Routate
public Node SLR(Node k1){
	Node tempParent = k1.parent;
	Node k2 = k1.right;
	k2.parent=tempParent;
	{if(tempParent!=null&&(tempParent.left==k1))
		tempParent.left=k2;
	 else if(tempParent!=null&&(tempParent.right==k1))
		tempParent.right=k2;}
	
	k1.right=k2.left;
	if(k2.left!=null)
		
	k2.left.parent=k1;
	k2.left=k1;
	k1.parent=k2;
	k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
	k2.height = Math.max( height( k2.left ), k1.height ) + 1;

	if(k1==root)		//if k1 was the root, k2 will be the route
		root=k2;
    
    return k2;
	
}

//Double Right Routate
public Node DRR(Node k1){
//DRR consists of  two Single Routates, first Rouate left then rouatte right
	k1.left=SLR(k1.left);
	return SRR(k1);
	
}
public Node DLR(Node k1){
//DLF consists of  two Single Routates, first Rouate right then rouatte left
	k1.right=SRR(k1.right);
	return SLR(k1);
	
}

//insert function that insert anode in the tree and check the balance
//after insertion
public Node insert(String word,String mean,Node t,Node p){

	if( t == null ){
	//this procedure do the insertion 
        {t = new Node(word,mean);
        	t.parent=p;
        }
        if(count==0)
        	root=t;
        count++;
        }
	else if( word.compareTo( t.element ) < 0 )
    {
        t.left = insert( word,mean,t.left ,t);
		//check the balance of the tree
        if( height( t.left ) - height( t.right ) == 2 )
        {
            if( word.compareTo( t.left.element ) < 0 )
                t = SRR( t );
            else
                t = DRR( t );}
    }
    else if( word.compareTo( t.element ) > 0 )
    {
        t.right = insert( word,mean,t.right,t );
        if( height( t.right ) - height( t.left ) == 2 ){
            if( word.compareTo( t.right.element ) > 0 )
                t = SLR( t );
            else
                t = DLR( t );}
    }
    else
        ;
		//set the height of the new node
    t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
   
    return t;
}

//Delete function that delete aNode from the tree
//retun true if the node deleted and false if the tree empty

public boolean delete(Node t,Node root){

	if((root==null)) //if the treee empty retrun false
		return false;
	else if((t.left==null)&&(t.right==null))
			delWithNoChild(t);
	else if((t.left==null)||(t.right==null))
		delWithOneChild(t);
	else delWithChilds(t);
	return true;
		
}

//delete the node with no childs
private boolean delWithNoChild(Node t){
	if(t==root)
		{
		count=0;
		t=null;
		}
	else
	{
	Node tempParent = t.parent;
	
	if(tempParent.left==t)
		t.parent.left=null;
	else
		tempParent.right=null;
	
	tempParent.height=Math.max(height(tempParent.left),height(tempParent.right))+1;
	if((height(tempParent.right)-height(tempParent.left))==2)
		SLR(tempParent);
	else if((height(tempParent.left)-height(tempParent.right))==2)
			SLR(tempParent);
	}
	return true;
}

//delete the node with only one child
private boolean delWithOneChild(Node t){
	if(t==root)//in case of the deleted node is the root
	{
		if(t.right==null)
		{
			root=t.left;
			t.left.parent=null;
		}
		else
		{
			root=t.right;
			t.right.parent=null;
		}
	}
	else
	{
	Node temp =t;
	{if(t.right==null)
		temp=t.left;
	else 
		temp=t.right;}
	
	Node tempParent=t.parent;
	if(tempParent.right==t)
		tempParent.right=temp;
	else
		tempParent.left=temp;
	
	temp.parent=tempParent;
	tempParent.height=Math.max(tempParent.right.height,tempParent.left.height);
	if((tempParent.right.height-tempParent.left.height)==2)
	SRR(tempParent.left);
	else if((tempParent.left.height-tempParent.right.height)==2)
		SLR(tempParent.right);
	}
	return true;
}

//delete the node with two childs
private boolean delWithChilds(Node t){
	Node temp=findMin(t.right);
	t.element=(temp.element);
	t.meaning=(temp.meaning);
	delWithNoChild(temp);
	return true;
}

//print tree in order form
public void printTree(JTextArea txt){
	if(root==null)
		txt.setText("Tree is Empty!!");
	else {
		txt.setText(" ");
		printTree(root,txt);
	}
}
//print the tree in postorder form
public void printPostOrderTree(JTextArea txt){
	if(root==null)
		txt.setText("Tree is Empty!!");
	else {
		txt.setText(" ");
		printPostOrderTree(root,txt);
	}
}

//print the  tree in post order form
public void printPreOrderTree(JTextArea txt){
	if(root==null)
		txt.setText("Tree is Empty!!");
	else {
		txt.setText(" ");
		printPreOrderTree(root,txt);
	}
}


public void printTree(Node root,JTextArea txt){
   if(root!=null)
	{	   
		printTree( root.left,txt );
    	txt.append(root.element+"\n ");
        printTree( root.right,txt );
    }		
}
public void printPreOrderTree(Node root,JTextArea txt){
	   if(root!=null)
		{	    
			txt.append(root.element+"\n ");
		   	printTree( root.left,txt );
	        printTree( root.right,txt );
	    }		
	}
public void printPostOrderTree(Node root,JTextArea txt){
   if(root!=null)
	{	    
		printTree( root.left,txt );
        printTree( root.right,txt );
        txt.append(root.element+"\n ");
    }		
}

//print words with common first char
public void printWords(String sub,Node root,JTextArea txt){
	if(root!=null)
	{	    
		printWords( sub,root.left,txt );
    	if(root.element.substring(0,1).equals(sub))
    	txt.append(" "+root.element+"\n");
        printWords( sub,root.right,txt );
    }		
}

//modify word only
public void modifyWord(String word,String newWord,Node root){
	Node mod = find(word,root);
	if(mod==null)
		System.out.println("No match");
	else{
		String mean=mod.meaning;
		delete(mod,root);
		insert(newWord,mean,root,null);
		System.out.println("Modification done");
	}
}

//modify word with meaning 
public void modifyMean(String word,String newMeaning,Node root){
	Node mod = find(word,root);
	if(mod==null)
		System.out.println("No match");
	else{
		mod.meaning=newMeaning;
		System.out.println("Modification done");
}
}
}

Menu.java (13.05 KB)

The attachment preview is chopped off after the first 10 KB. Please download the entire file.

package avl;

import java.awt.color.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.*;
import java.util.Scanner;

import javax.swing.*;

//the menu class which deal with interface of the programe//
//it generate the file edit,help menues//
public class Menu extends JFrame implements ActionListener {
		static AVL tree = new AVL();	
		String fileName=new String();
		final static JTextArea txt= new JTextArea(5,4);
public Menu() {
		
	
        setTitle("AVL Tree Based Dictionary");
        setSize(400, 400);
        
        // Creates a menubar for a JFrame
        JMenuBar menuBar = new JMenuBar();
    
		JPanel textFrame = new JPanel(new BorderLayout());
		txt.setBackground(Color.BLACK);
		txt.setForeground(Color.WHITE);
		txt.setEditable(false);
		textFrame.add(txt);
		add(textFrame,BorderLayout.CENTER);
	
        
        // Add the menubar to the frame
        setJMenuBar(menuBar);
        
        // Define and add drop down menus to the menubar
        JMenu fileMenu 		= new JMenu("File");
        JMenu editMenu 		= new JMenu("Edit");
        JMenu helpMenu 		= new JMenu("Help");
        JMenu printMenu		= new JMenu("Print"); 
        JMenu searchMenu	= new JMenu("Search");
        menuBar.add(fileMenu);
        menuBar.add(editMenu);
        menuBar.add(printMenu);
        menuBar.add(searchMenu);
        menuBar.add(helpMenu);
        
        // Create and add  menu items to sthe drop down menu
        JMenuItem newAction 			= new JMenuItem("New");
        JMenuItem openAction 			= new JMenuItem("Open File");
        JMenuItem updateFileAction 		= new JMenuItem("update file");
        
        JMenuItem insertAction 			= new JMenuItem("Insert");
        JMenuItem deleteAction 			= new JMenuItem("Delete");
        JMenuItem modifyAction 			= new JMenuItem("Modify aWord");
        
        
        JMenuItem printInOrderAction 	= new JMenuItem("Print InOrder");
        JMenuItem printPreOrderAction 	= new JMenuItem("Print PreOrder");
        JMenuItem printPostOrderAction 	= new JMenuItem("Print PostOrder");
       
        JMenuItem searchAction			= new JMenuItem("Search");
        JMenuItem aboutAction 			= new JMenuItem("About");
        
        
        fileMenu.add(newAction);
        fileMenu.add(openAction);
        fileMenu.addSeparator();
        fileMenu.add(updateFileAction);
        
        editMenu.add(insertAction);
        editMenu.add(deleteAction);
        editMenu.addSeparator();
        editMenu.add(modifyAction);
        
        printMenu.add(printInOrderAction);
        printMenu.add(printPreOrderAction);
        printMenu.add(printPostOrderAction);
        
        searchMenu.add(searchAction);
        helpMenu.add(aboutAction);
    
        //creat the action performed when choose one of the menues
       
newAction.addActionListener(new ActionListener() {
        	public void actionPerformed(ActionEvent arg0) {
        		tree.makeEmpty();
        		JOptionPane.showMessageDialog(null, "the AVL Tree is now Blank!!","Blank TREE",2);
        	}}
            );

openAction.addActionListener(new ActionListener() {
        	public void actionPerformed(ActionEvent arg0) {
        		fileName=JOptionPane.showInputDialog(null,"Type the file name with full directory","Open",1);
	     try {
	    	 readFromFile(fileName);} 
	     catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();}
        	}}
        	);
updateFileAction.addActionListener(new ActionListener() {
        	public void actionPerformed(ActionEvent arg0) {
        		if(fileName.length()==0)
        			JOptionPane.showMessageDialog(null,"No Opened File!!","Error",JOptionPane.ERROR_MESSAGE);
        		else{	
        		try {
					writeToFile(fileName);}
				 catch (FileNotFoundException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				 	}
        		JOptionPane.showMessageDialog(null, "Done");
        			}
        	}}
            );
searchAction.addActionListener(new ActionListener() {
        	public void actionPerformed(ActionEvent arg0) {
        		searchMenu();
        		}}
            );
insertAction.addActionListener(new ActionListener() {
			public void actionPerformed(ActionEvent arg0) {
				insertMenu();
			}}
    );
deleteAction.addActionListener(new ActionListener() {
	public void actionPerformed(ActionEvent arg0) {
		deleteMenu();
	}}
);
modifyAction.addActionListener(new ActionListener() {
	public void actionPerformed(ActionEvent arg0) {
		modifyMenu();
	}}
);
printInOrderAction.addActionListener(new ActionListener() {
	public void actionPerformed(ActionEvent arg0) {
		tree.printTree(txt);
	}}
);
printPreOrderAction.addActionListener(new ActionListener() {
	public void actionPerformed(ActionEvent arg0) {
		tree.printPreOrderTree(txt);
	}}
);
printPostOrderAction.addActionListener(new ActionListener() {
	public void actionPerformed(ActionEvent arg0) {
		tree.printPostOrderTree(txt);
	}}
);
aboutAction.addActionListener(new ActionListener() {
	public void actionPerformed(ActionEvent arg0) {
		JOptionPane.showMessageDialog(null,"BY: Abdulfattah Safa,1050187");
	}}
);
 }
public void readFromFile(String fileName) throws FileNotFoundException{
	File file=new File(fileName);
	if(!file.canRead()||!file.exists()) //if the file has erorrs
	{
	JOptionPane.showMessageDialog(null,"File name you have typed either does not exist or cant be read","Error",2);
	fileName=null;
	}
	else{
	String x=new String ();
	String y=new String();
	Scanner scanner = new Scanner(file);
	while(scanner.hasNext())
	{
		x=scanner.next();
		y=scanner.next();
		tree.insert(x,y, tree.root,null);
		
	}
	JOptionPane.showMessageDialog(null,"Done");
		}
	file.exists();
}

public void writeToFile(String fileName) throws FileNotFoundException{
		
	File file=new File(fileName);
	PrintWriter print = new PrintWriter(file);
	writeToFile(tree.root,print);
	print.close();
}


public void writeToFile(Node root,PrintWriter print){
if(root!=null)
	{	    
	writeToFile(root.left,print );
	print.println(root.element+" "+root.meaning);
    writeToFile(root.right,print );
	}		
}

//construct  the Edit menu item subMenus
public void insertMenu(){
	final JFrame insertFrame = new JFrame();
	JPanel p1 = new JPanel(new FlowLayout());
	JPanel p2 = new JPanel(new FlowLayout());
	JPanel p3 = new JPanel(new FlowLayout());
	
	JButton wordPane = new JButton("New Word");
	final JTextArea wordArea = new JTextArea(2,10);
	wordArea.setBackground(Color.BLACK);
	wordArea.setForeground(Color.white);
	JButton meanPane = new JButton("Meanining");
	final JTextArea meanArea = new JTextArea(2,10);
	meanArea.setBackground(Color.BLACK);
	meanArea.setForeground(Color.white);
	
	JButton insertButton=new JButton("Insert");
	JButton cancelButton = new JButton("Cancel");
	
	p1.add(wordPane);
	p1.add(wordArea);
	p2.add(meanPane);
	p2.add(meanArea);
	p3.add(insertButton);
	p3.add(cancelButton);
	
	insertFrame.add(p1,BorderLayout.NORTH);
	insertFrame.add(p2,BorderLayout.CENTER);
	insertFrame.add(p3,BorderLayout.SOUTH);
	insertFrame.setTitle("Insert New Word");
	insertFrame.setSize(300,200);
	insertFrame.setLocationRelativeTo(null);
	insertFrame.setVisible(true);
	
insertButton.addActionListener(new ActionListener() {
    	public void actionPerformed(ActionEvent arg0) {
    		if(wordArea.getText().length()!=0){
    			tree.insert(wordArea.getText(),meanArea.getText(),tree.root,null);
        		JOptionPane.showMessageDialog(null,"Done");
    		}
    		
    	}}    
	);
cancelButton.addActionListener(new ActionListener() {
	public void actionPerformed(ActionEvent arg0) {
		insertFrame.setVisible(false);
	}}    
);
}

public static void deleteMenu(){
	String word=JOptionPane.showInputDialog(null,"Type the word tou want tod delete:","Delete",1);
	if(tree.find(word,tree.root)==null)
		JOptionPane.showMessageDialog(null,"The word you have typed doesnt match any word in the tree","eror",2);
	else
		{tree.delete(tree.find(word,tree.root),tree.root);
	JOptionPane.showMessageDialog(null,"Done");}
}

public static void modifyMenu(){
	final JFrame modifyFrame = new JFrame();
	JPanel pa = new JPanel(new FlowLayout());
	JPanel pb = new JPanel(new FlowLayout());
	JPanel pc = new JPanel(new FlowLayout());
	
	JPanel p1 = new JPanel(new FlowLayout());
	JPanel p2 = new JPanel(new FlowLayout());
	JPanel p3 = new JPanel(new FlowLayout());
	JPanel p4 = new JPanel(new FlowLayout());
	JPanel p5 = new JPanel(new FlowLayout());
	
	JButton wordPane = new JButton("OldWord");
	final JTextArea wordArea = new JTextArea(2,10);
	wordArea.setBackground(Color.BLACK);
	wordArea.setForeground(Color.white);
	JButton meanPane = new JButton("Meaning");
	final JTextArea meanArea = new JTextArea("dont fill",2,10);
	meanArea.setBackground(Color.BLACK);
	meanArea.setForeground(Color.white);
	meanArea.setEditable(false);
	
	JButton newWordPane = new JButton("NewWord");
	final JTextArea newWordArea = new JTextArea(2,10);
	newWordArea.setBackground(Color.BLACK);
	newWordArea.setForeground(Color.WHITE);
	
	JButton newMeanPane = new JButton("Meaning");
	final JTextArea newMeanArea = new JTextArea(2,10);
	newMeanArea.setBackground(Color.BLACK);
	newMeanArea.setForeground(Color.white);
	
	JButton modifyButton=new JButton("Modify");
	JButton cancelButton = new JButton("Cancel");
	
	p1.add(wordPane);
	p1.add(wordArea);
	p2.add(meanPane);
	p2.add(meanArea);
	p3.add(newWordPane);
	p3.add(newWordArea);
	p4.add(newMeanPane);
	p4.add(newMeanArea);
	p5.add(modifyButton);
	p5.add(cancelButton);
	
	pa.add(p1,BorderLayout.NORTH);
	pa.add(p2,BorderLayout.SOUTH);
	
	pb.add(p3,BorderLayout.NORTH);
	pb.add(p4,BorderLayout.SOUTH);
	
	pc.add(p5,BorderLayout.CENTER);
	
	modifyFrame.add(pa,BorderLayout.NORTH);
	modifyFrame.add(pb,BorderLayout.CENTER);
	modifyFrame.add(pc,BorderLayout.SOUTH);
	modifyFrame.setTitle("Modify Word");
	modifyFrame.setSize(500,200);
	modifyFrame.setL

Node.java (0.3 KB)

package avl;

public class Node {
	protected String element;
	protected String meaning;
	protected Node left;
	protected Node right;
	protected Node parent;
	protected int height;

public Node(String word,String mean){
	element =word ;
	meaning=mean;
	parent=left=right=null;
	height=0;
	
}
}

1 Contributor
0 Replies
84 Views

Be the first to reply

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.