Skip to content

Commit 50d36da

Browse files
java4funjava4fun
committed
Initial commit
0 parents  commit 50d36da

123 files changed

Lines changed: 8365 additions & 0 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎.gitignore‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
/.metadata/

‎.idea/.gitignore‎

Lines changed: 2 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/DataStructure.iml‎

Lines changed: 9 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/misc.xml‎

Lines changed: 4 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/modules.xml‎

Lines changed: 8 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/vcs.xml‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎AVL/AVL/.classpath‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.8"/>
5+
<classpathentry kind="output" path="bin"/>
6+
</classpath>

‎AVL/AVL/.project‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectDescription>
3+
<name>AVL</name>
4+
<comment></comment>
5+
<projects>
6+
</projects>
7+
<buildSpec>
8+
<buildCommand>
9+
<name>org.eclipse.jdt.core.javabuilder</name>
10+
<arguments>
11+
</arguments>
12+
</buildCommand>
13+
</buildSpec>
14+
<natures>
15+
<nature>org.eclipse.jdt.core.javanature</nature>
16+
</natures>
17+
</projectDescription>

‎AVL/AVL/src/com/balazsholczer/avl/App.java‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package com.balazsholczer.avl;
2+
3+
public class App {
4+
5+
public static void main(String[] args) {
6+
7+
Tree avl = new AvlTree();
8+
9+
avl.insert(10);
10+
avl.insert(15);
11+
avl.insert(5);
12+
avl.insert(6);
13+
14+
avl.delete(15);
15+
16+
avl.traverse();
17+
}
18+
19+
}

‎AVL/AVL/src/com/balazsholczer/avl/AvlTree.java‎

Lines changed: 222 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,222 @@
1+
package com.balazsholczer.avl;
2+
3+
4+
public class AvlTree implements Tree {
5+
6+
private Node root;
7+
8+
@Override
9+
public void insert(int data) {
10+
root = insert(root, data);
11+
}
12+
13+
@Override
14+
public void delete(int data) {
15+
root = delete(root, data);
16+
}
17+
18+
private Node insert(Node node, int data) {
19+
20+
if (node == null) {
21+
return new Node(data);
22+
}
23+
24+
if (data < node.getData()) {
25+
node.setLeftNode(insert(node.getLeftNode(), data));
26+
} else {
27+
node.setRightNode(insert(node.getRightNode(), data));
28+
}
29+
30+
node.setHeight(Math.max(height(node.getLeftNode()), height(node.getRightNode())) + 1);
31+
32+
return settleViolation(data, node);
33+
}
34+
35+
36+
private Node delete(Node node, int data) {
37+
38+
if (node == null)
39+
return node;
40+
41+
// first we have to look for the node we want to get rid of
42+
if (data < node.getData()) { // data smaller than given node's data -> go to the left recursively
43+
node.setLeftNode(delete(node.getLeftNode(), data));
44+
} else if (data > node.getData()) { // data greater than given node's data -> go to the right recursively
45+
node.setRightNode(delete(node.getRightNode(), data));
46+
} else { // we have found the node we want to remove !!!
47+
48+
if (node.getLeftNode() == null && node.getRightNode() == null) {
49+
System.out.println("Removing a leaf node...");
50+
return null;
51+
}
52+
53+
if (node.getLeftNode() == null) {
54+
System.out.println("Removing the right child...");
55+
Node tempNode = node.getRightNode();
56+
node = null;
57+
return tempNode;
58+
} else if (node.getRightNode() == null) {
59+
System.out.println("Removing the left child...");
60+
Node tempNode = node.getLeftNode();
61+
node = null;
62+
return tempNode;
63+
}
64+
65+
// this is the node with two children case !!!
66+
System.out.println("Removing item with two children...");
67+
Node tempNode = getPredecessor(node.getLeftNode());
68+
69+
node.setData(tempNode.getData());
70+
node.setLeftNode(delete(node.getLeftNode(), tempNode.getData()));
71+
}
72+
73+
node.setHeight(Math.max(height(node.getLeftNode()), height(node.getRightNode())) + 1);
74+
75+
// have to check on every delete operation whether the tree has become unbalanced or not !!!
76+
return settleDeletion(node);
77+
}
78+
79+
private Node settleDeletion(Node node) {
80+
81+
int balance = getBalance(node);
82+
83+
// OK, we know the tree is left heavy BUT it can be left-right heavy or left-left heavy
84+
if (balance > 1) {
85+
86+
// left right heavy situation: left rotation on parent + right rotation on grandparent
87+
if (getBalance(node.getLeftNode()) < 0) {
88+
node.setLeftNode(leftRotation(node.getLeftNode()));
89+
}
90+
91+
// this is the right rotation on grandparent ( if left-left heavy, thats single right rotation is needed
92+
return rightRotation(node);
93+
}
94+
95+
// OK, we know the tree is right heavy BUT it can be left-right heavy or right-right heavy
96+
if (balance < -1) {
97+
// right - left heavy so we need a right rotation ( on parent!!! ) before left rotation
98+
if (getBalance(node.getRightNode()) > 0) {
99+
node.setRightNode(rightRotation(node.getRightNode()));
100+
}
101+
102+
// left rotation on grand parent
103+
return leftRotation(node);
104+
}
105+
106+
return node;
107+
}
108+
109+
private Node getPredecessor(Node node) {
110+
111+
Node predecessor = node;
112+
113+
while (predecessor.getRightNode() != null)
114+
predecessor = predecessor.getRightNode();
115+
116+
return predecessor;
117+
}
118+
119+
private Node settleViolation(int data, Node node) {
120+
121+
int balance = getBalance(node);
122+
123+
// this is the Case I !!!! left-left
124+
if (balance > 1 && data < node.getLeftNode().getData()) {
125+
System.out.println("Tree is left left heavy...");
126+
return rightRotation(node);
127+
}
128+
129+
// this is the Case II right-right !!!!
130+
if (balance < -1 && data > node.getRightNode().getData()) {
131+
System.out.println("Tree is right right heavy...");
132+
return leftRotation(node);
133+
}
134+
135+
// left right situation
136+
if (balance > 1 && data > node.getLeftNode().getData()) {
137+
System.out.println("Tree is left right heavy...");
138+
node.setLeftNode(leftRotation(node.getLeftNode()));
139+
return rightRotation(node);
140+
}
141+
142+
// right left situation
143+
if (balance < -1 && data < node.getRightNode().getData()) {
144+
System.out.println("Tree is right left heavy...");
145+
node.setRightNode(rightRotation(node.getRightNode()));
146+
return leftRotation(node);
147+
}
148+
149+
return node;
150+
}
151+
152+
private Node rightRotation(Node node) {
153+
154+
System.out.println("Rotating to the right on node: " + node);
155+
156+
Node tempLeftNode = node.getLeftNode();
157+
Node t = tempLeftNode.getRightNode();
158+
159+
tempLeftNode.setRightNode(node);
160+
node.setLeftNode(t);
161+
162+
node.setHeight(Math.max(height(node.getLeftNode()), height(node.getRightNode())) + 1);
163+
tempLeftNode.setHeight(Math.max(height(tempLeftNode.getLeftNode()), height(tempLeftNode.getRightNode())) + 1);
164+
165+
return tempLeftNode;
166+
}
167+
168+
private Node leftRotation(Node node) {
169+
170+
System.out.println("Rotating to the left on node:" + node);
171+
172+
Node tempRightNode = node.getRightNode();
173+
Node t = tempRightNode.getLeftNode();
174+
175+
tempRightNode.setLeftNode(node);
176+
node.setRightNode(t);
177+
178+
node.setHeight(Math.max(height(node.getLeftNode()), height(node.getRightNode())) + 1);
179+
tempRightNode
180+
.setHeight(Math.max(height(tempRightNode.getLeftNode()), height(tempRightNode.getRightNode())) + 1);
181+
182+
return tempRightNode;
183+
}
184+
185+
private int height(Node node) {
186+
187+
if (node == null) {
188+
return -1;
189+
}
190+
191+
return node.getHeight();
192+
}
193+
194+
private int getBalance(Node node) {
195+
196+
if (node == null) {
197+
return 0;
198+
}
199+
200+
return height(node.getLeftNode()) - height(node.getRightNode());
201+
}
202+
203+
@Override
204+
public void traverse() {
205+
206+
if (root == null)
207+
return;
208+
209+
inOrderTraversal(root);
210+
}
211+
212+
private void inOrderTraversal(Node node) {
213+
214+
if (node.getLeftNode() != null)
215+
inOrderTraversal(node.getLeftNode());
216+
217+
System.out.println(node);
218+
219+
if (node.getRightNode() != null)
220+
inOrderTraversal(node.getRightNode());
221+
}
222+
}

0 commit comments

Comments
 (0)