data_structures_project/Tries.java at master · kandrew5/data_structures_project · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
import java.util.HashMap;

public class Tries {

	private class NodeT
	{
		String key;//ãñáììá ôçò ëåîçò
		HashMap<String, NodeT> kiddo;//áñ÷éêïðïéïõìå ôï Hashmap ðïõ êáíåé map ôá string ìå áíôéêåéìåíá ôõðïõ NodeT
		boolean endofword;//boolean ìåôáâëçôç ðïõ äåé÷íåé áí õðáñ÷åé ëåîç ðïõ ôåëåéùíåé ìå ôï ãñáììá key

		NodeT(String key, HashMap<String, NodeT> kiddo)//constructor ãéá ôï NodeT
		{
			this.key=key;
			this.kiddo=kiddo;
			endofword=false;//áñ÷éêïðïéïõìå ôçí ìåôáâëçôç ìå false
		}
	}

		private NodeT root= new NodeT(null, new HashMap<>());//áñ÷éêïðïéïõìå ôçí ñéæá ìå ôéìç null

		public void insert(String key)
		{
			NodeT temp= root;
			int i=0;
			int length=key.length();
			String index;


			for(i=0;i<length;i++)//ïóï ç ëåîç å÷åé áêïìá ÷áñáêôçñåò
			{
				index=Character.toString(key.charAt(i));
				if(temp.kiddo.containsKey(index))//ç containsKey åëåã÷åé áí õðáñ÷åé çäç ôï ãñáììá ãéá áëëç ëåîç
				{
					temp=temp.kiddo.get(index);
					continue;
				}
				else
				{
					break;
				}
			}

			while(i<length)//ïôáí ðëåïí äåí å÷ïõìå áëëïõò êïéíïõò ÷áñáêôçñåò(ìå áëëåò ëåîåéò) ðñïóèåôïõìå åíá åíá ôá õðïëïéðá óôïé÷åéá
			{
				index=Character.toString(key.charAt(i));
				temp.kiddo.put(index, new NodeT(null, new HashMap<>()));
				temp=temp.kiddo.get(index);
				i++;
			}
		temp.endofword=true;
	}

	public boolean searchT(String key)
	{
		boolean success=false;
		NodeT temp=root;
 		int i=0;
		int length=key.length();
		String index;
		for(i=0;i<length;i++)
		{
			index=Character.toString(key.charAt(i));
			if(temp.kiddo.containsKey(index)==false)
			{
				break;
			}
			if(temp.kiddo.containsKey(index))
			{
				temp=temp.kiddo.get(index);
				continue;
			}
		}
		if(i==length && temp.endofword)//ìïíï ïôáí å÷åé ôåëåéùóåé ç ëåîç êáé ç endofword åéíáé true èá å÷ïõìå âñåé ôï óôïé÷åéï
		{
			success=true;
			System.out.println("the bool value is true");
		}
		else{System.out.println("the bool value is false");}
		return success;
	}

	public void deleteT(String key)
	{
		int length=key.length();
		if(length>0)
		{
			deleteHelp(root,key,0);
		}
	}
		private boolean deleteHelp(NodeT x, String key, int i)
		{
			if(x!=null)
			{
				if(i==key.length() && x.endofword==true)//áí å÷åé ôåëåéùóåé ç ëåîç êáé ç endofword åéíáé true
				{
					x.endofword=false;
					if(x.kiddo!=null)//áí äåí å÷åé êáíåíá áëëï ðáéäé
					{
						return x.kiddo.isEmpty();//åðåóôñåøå true
					}
				}
				else
				{
					String index=Character.toString(key.charAt(i));
					i++;
					if(deleteHelp(x.kiddo.get(index),key,i))//áíáäñïìéêç êëçóç ôçò deleteHelp
					{
						x.kiddo.remove(index);//ìïíï áí ç ðáñáðáíù ôéìç åéíáé true áöáéñåóå ôï óôïé÷åéï
						return x.endofword==false && x.kiddo.isEmpty();
					}
				}
			}
				return false;
		}
}