Skip to content

Commit 45b76e5

Browse files
r0hit-guptar0hit-gupta
authored
Merge pull request TheAlgorithms#77 from ParitoshAggarwal/master
Add files via upload
2 parents 0e48afc + c993087 commit 45b76e5

File tree

2 files changed

+367
-0
lines changed

2 files changed

+367
-0
lines changed

‎data_structures/HashMap/HashMap.java

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
2+
3+
import java.util.ArrayList;
4+
import java.util.LinkedList;
5+
6+
public class HashMap<K,V> {
7+
public class hmnodes{ //HashMap nodes
8+
K key;
9+
V value;
10+
}
11+
12+
private int size=0; //size of hashmap
13+
private LinkedList<hmnodes> buckets[]; //array of addresses of list
14+
15+
public HashMap(){
16+
buckets=new LinkedList[4]; //initially create bucket of any size
17+
for(int i=0;i<4;i++)
18+
buckets[i]=new LinkedList<>();
19+
}
20+
21+
public void put(K key,V value) throws Exception{
22+
int bi=bucketIndex(key); //find the index,the new key will be inserted in linklist at that index
23+
int fountAt=find(bi,key); //check if key already exists or not
24+
if(fountAt==-1){
25+
hmnodes temp=new hmnodes(); //if doesn't exist create new node and insert
26+
temp.key=key;
27+
temp.value=value;
28+
buckets[bi].addLast(temp);
29+
this.size++;
30+
}else{
31+
buckets[bi].get(fountAt).value=value;//if already exist modify the value
32+
}
33+
34+
double lambda = (this.size*1.0)/this.buckets.length;
35+
if(lambda>2.0){
36+
rehash(); //rehashing function which will increase the size of bucket as soon as lambda exceeds 2.0
37+
}
38+
39+
return;
40+
}
41+
42+
43+
public V get(K key) throws Exception{
44+
int bi=bucketIndex(key);
45+
int fountAt=find(bi,key);
46+
if(fountAt==-1){
47+
return null;
48+
}else{
49+
return buckets[bi].get(fountAt).value;
50+
}
51+
}
52+
53+
public V remove(K key) throws Exception{
54+
int bi=bucketIndex(key);
55+
int fountAt=find(bi,key);
56+
if(fountAt==-1){
57+
return null;
58+
}else{
59+
this.size--;
60+
return buckets[bi].remove(fountAt).value;
61+
}
62+
}
63+
64+
public boolean containskey(K key) throws Exception{
65+
int bi=bucketIndex(key);
66+
int fountAt=find(bi,key);
67+
if(fountAt==-1){
68+
return false;
69+
}else{
70+
return true;
71+
}
72+
}
73+
74+
public int size(){
75+
return this.size;
76+
}
77+
78+
79+
public boolean isempty(){
80+
return this.size==0;
81+
}
82+
83+
public ArrayList<K> keyset() throws Exception{
84+
ArrayList<K> arr=new ArrayList<>();
85+
for(int i=0;i<buckets.length;i++){
86+
for(int j=0;j<buckets[i].size();j++){
87+
arr.add(buckets[i].get(j).key);
88+
}
89+
}
90+
return arr;
91+
}
92+
93+
public ArrayList<V> valueset() throws Exception{
94+
ArrayList<V> arr=new ArrayList<>();
95+
for(int i=0;i<buckets.length;i++){
96+
for(int j=0;j<buckets[i].size();j++){
97+
arr.add(buckets[i].get(j).value);
98+
}
99+
}
100+
return arr;
101+
}
102+
103+
public void display() throws Exception{
104+
for(int i=0;i<buckets.length;i++){
105+
System.out.print("Bucket: "+i+" ");
106+
for(int j=0;j<buckets[i].size();j++){
107+
hmnodes temp=buckets[i].get(j);
108+
System.out.print("["+temp.key+"->"+temp.value+"]");
109+
}
110+
System.out.println();
111+
}
112+
}
113+
114+
public int find(int bi,K key) throws Exception{
115+
for(int i=0;i<buckets[bi].size();i++){
116+
if(key.equals(buckets[bi].get(i).key))
117+
return i;
118+
}
119+
return -1;
120+
}
121+
122+
public int bucketIndex(K key) throws Exception{
123+
int bi=key.hashCode();
124+
return Math.abs(bi%buckets.length);
125+
}
126+
127+
private void rehash() throws Exception{
128+
LinkedList<hmnodes> ob[]= buckets;
129+
buckets=new LinkedList[ob.length*2];
130+
for(int i=0;i<ob.length*2;i++)
131+
buckets[i]=new LinkedList<>();
132+
133+
size = 0;
134+
for(int i=0;i<ob.length;i++){
135+
for(int j=0;j<ob[i].size();j++){
136+
put(ob[i].get(j).key,ob[i].get(j).value);
137+
}
138+
}
139+
140+
}
141+
}

‎data_structures/Trees/GenericTree.Java

Lines changed: 226 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,226 @@
1+
import java.util.ArrayList;
2+
import java.util.LinkedList;
3+
import java.util.Scanner;
4+
5+
public class treeclass {
6+
private class Node {
7+
int data;
8+
ArrayList<Node> child = new ArrayList<>();
9+
}
10+
11+
private Node root;
12+
private int size;
13+
14+
/*
15+
A generic tree is a tree which can have as many children as it can be
16+
It might be possible that every node present is directly connected to
17+
root node.
18+
19+
In this code
20+
Every function has two copies: one function is helper function which can be called from
21+
main and from that function a private function is called which will do the actual work.
22+
I have done this, while calling from main one have to give minimum parameters.
23+
24+
*/
25+
public treeclass() { //Constructor
26+
Scanner scn = new Scanner(System.in);
27+
root = create_treeG(null, 0, scn);
28+
}
29+
30+
private Node create_treeG(Node node, int childindx, Scanner scn) {
31+
// display
32+
if (node == null) {
33+
System.out.println("Enter root's data");
34+
} else {
35+
System.out.println("Enter data of parent of index " + node.data + " " + childindx);
36+
}
37+
// input
38+
node = new Node();
39+
node.data = scn.nextInt();
40+
System.out.println("number of children");
41+
int number = scn.nextInt();
42+
for (int i = 0; i < number; i++) {
43+
Node childd = create_treeG(node, i, scn);
44+
size++;
45+
node.child.add(childd);
46+
}
47+
return node;
48+
}
49+
50+
/*
51+
Function to display the generic tree
52+
*/
53+
public void display() { //Helper function
54+
display_1(root);
55+
return;
56+
}
57+
58+
private void display_1(Node parent) {
59+
System.out.print(parent.data + "=>");
60+
for (int i = 0; i < parent.child.size(); i++) {
61+
System.out.print(parent.child.get(i).data + " ");
62+
}
63+
System.out.println(".");
64+
for (int i = 0; i < parent.child.size(); i++) {
65+
display_1(parent.child.get(i));
66+
}
67+
return;
68+
}
69+
70+
/*
71+
One call store the size directly but if you are asked compute size this function to calcuate
72+
size goes as follows
73+
*/
74+
75+
public int size2call() {
76+
return size2(root);
77+
}
78+
79+
public int size2(Node roott) {
80+
int sz = 0;
81+
for (int i = 0; i < roott.child.size(); i++) {
82+
sz += size2(roott.child.get(i));
83+
}
84+
return sz + 1;
85+
}
86+
87+
/*
88+
Function to compute maximum value in the generic tree
89+
*/
90+
public int maxcall() {
91+
int maxi = root.data;
92+
return max(root, maxi);
93+
}
94+
95+
private int max(Node roott, int maxi) {
96+
if (maxi < roott.data)
97+
maxi = roott.data;
98+
for (int i = 0; i < roott.child.size(); i++) {
99+
maxi = max(roott.child.get(i), maxi);
100+
}
101+
102+
return maxi;
103+
}
104+
105+
/*
106+
Function to compute HEIGHT of the generic tree
107+
*/
108+
109+
public int heightcall() {
110+
return height(root) - 1;
111+
}
112+
113+
private int height(Node node) {
114+
int h = 0;
115+
for (int i = 0; i < node.child.size(); i++) {
116+
int k = height(node.child.get(i));
117+
if (k > h)
118+
h = k;
119+
}
120+
return h + 1;
121+
}
122+
123+
/*
124+
Function to find whether a number is present in the generic tree or not
125+
*/
126+
127+
public boolean findcall(int info) {
128+
return find(root, info);
129+
}
130+
131+
private boolean find(Node node, int info) {
132+
if (node.data == info)
133+
return true;
134+
for (int i = 0; i < node.child.size(); i++) {
135+
if (find(node.child.get(i), info))
136+
return true;
137+
}
138+
return false;
139+
}
140+
141+
/*
142+
Function to calculate depth of generic tree
143+
*/
144+
public void depthcaller(int dep) {
145+
depth(root, dep);
146+
}
147+
148+
public void depth(Node node, int dep) {
149+
if (dep == 0) {
150+
System.out.println(node.data);
151+
return;
152+
}
153+
for (int i = 0; i < node.child.size(); i++)
154+
depth(node.child.get(i), dep - 1);
155+
return;
156+
}
157+
158+
/*
159+
Function to print generic tree in pre-order
160+
*/
161+
public void preordercall() {
162+
preorder(root);
163+
System.out.println(".");
164+
}
165+
166+
private void preorder(Node node) {
167+
System.out.print(node.data + " ");
168+
for (int i = 0; i < node.child.size(); i++)
169+
preorder(node.child.get(i));
170+
}
171+
172+
/*
173+
Function to print generic tree in post-order
174+
*/
175+
public void postordercall() {
176+
postorder(root);
177+
System.out.println(".");
178+
}
179+
180+
private void postorder(Node node) {
181+
for (int i = 0; i < node.child.size(); i++)
182+
postorder(node.child.get(i));
183+
System.out.print(node.data + " ");
184+
}
185+
186+
/*
187+
Function to print generic tree in level-order
188+
*/
189+
190+
public void levelorder() {
191+
LinkedList<Node> q = new LinkedList<>();
192+
q.addLast(root);
193+
while (!q.isEmpty()) {
194+
int k = q.getFirst().data;
195+
System.out.print(k + " ");
196+
197+
for (int i = 0; i < q.getFirst().child.size(); i++) {
198+
q.addLast(q.getFirst().child.get(i));
199+
}
200+
q.removeFirst();
201+
}
202+
System.out.println(".");
203+
}
204+
205+
/*
206+
Function to remove all leaves of generic tree
207+
*/
208+
public void removeleavescall() {
209+
removeleaves(root);
210+
}
211+
212+
private void removeleaves(Node node) {
213+
ArrayList<Integer> arr = new ArrayList<>();
214+
for (int i = 0; i < node.child.size(); i++) {
215+
if (node.child.get(i).child.size() == 0) {
216+
arr.add(i);
217+
// node.child.remove(i);
218+
// i--;
219+
} else
220+
removeleaves(node.child.get(i));
221+
}
222+
for (int i = arr.size() - 1; i >= 0; i--) {
223+
node.child.remove(arr.get(i) + 0);
224+
}
225+
}
226+

0 commit comments

Comments
 (0)