Skip to content

Commit c8514ce

Browse files
eric-martineric-martin
authored
Merge pull request eugenp#8556 from maryarm/BAEL-3454
BAEL-3454: Guide to AVL trees in Java
2 parents 5d8f71a + 04139b0 commit c8514ce

File tree

2 files changed

+224
-0
lines changed
  • algorithms-miscellaneous-5/src

2 files changed

+224
-0
lines changed

‎algorithms-miscellaneous-5/src/main/java/com/baeldung/algorithms/balancedbinarytree/AVLTree.java‎

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
package com.baeldung.algorithms.balancedbinarytree;
2+
3+
public class AVLTree {
4+
5+
public class Node {
6+
int key;
7+
int height;
8+
Node left;
9+
Node right;
10+
11+
Node(int key) {
12+
this.key = key;
13+
}
14+
}
15+
16+
private Node root;
17+
18+
public Node find(int key) {
19+
Node current = root;
20+
while (current != null) {
21+
if (current.key == key) {
22+
break;
23+
}
24+
current = current.key < key ? current.right : current.left;
25+
}
26+
return current;
27+
}
28+
29+
public void insert(int key) {
30+
root = insert(root, key);
31+
}
32+
33+
public void delete(int key) {
34+
root = delete(root, key);
35+
}
36+
37+
public Node getRoot() {
38+
return root;
39+
}
40+
41+
public int height() {
42+
return root == null ? -1 : root.height;
43+
}
44+
45+
private Node insert(Node node, int key) {
46+
if (node == null) {
47+
return new Node(key);
48+
} else if (node.key > key) {
49+
node.left = insert(node.left, key);
50+
} else if (node.key < key) {
51+
node.right = insert(node.right, key);
52+
} else {
53+
throw new RuntimeException("duplicate Key!");
54+
}
55+
return rebalance(node);
56+
}
57+
58+
private Node delete(Node node, int key) {
59+
if (node == null) {
60+
return node;
61+
} else if (node.key > key) {
62+
node.left = delete(node.left, key);
63+
} else if (node.key < key) {
64+
node.right = delete(node.right, key);
65+
} else {
66+
if (node.left == null || node.right == null) {
67+
node = (node.left == null) ? node.right : node.left;
68+
} else {
69+
Node mostLeftChild = mostLeftChild(node.right);
70+
node.key = mostLeftChild.key;
71+
node.right = delete(node.right, node.key);
72+
}
73+
}
74+
if (node != null) {
75+
node = rebalance(node);
76+
}
77+
return node;
78+
}
79+
80+
private Node mostLeftChild(Node node) {
81+
Node current = node;
82+
/* loop down to find the leftmost leaf */
83+
while (current.left != null) {
84+
current = current.left;
85+
}
86+
return current;
87+
}
88+
89+
private Node rebalance(Node z) {
90+
updateHeight(z);
91+
int balance = getBalance(z);
92+
if (balance > 1) {
93+
if (height(z.right.right) > height(z.right.left)) {
94+
z = rotateLeft(z);
95+
} else {
96+
z.right = rotateRight(z.right);
97+
z = rotateLeft(z);
98+
}
99+
} else if (balance < -1) {
100+
if (height(z.left.left) > height(z.left.right)) {
101+
z = rotateRight(z);
102+
} else {
103+
z.left = rotateLeft(z.left);
104+
z = rotateRight(z);
105+
}
106+
}
107+
return z;
108+
}
109+
110+
private Node rotateRight(Node y) {
111+
Node x = y.left;
112+
Node z = x.right;
113+
x.right = y;
114+
y.left = z;
115+
updateHeight(y);
116+
updateHeight(x);
117+
return x;
118+
}
119+
120+
private Node rotateLeft(Node y) {
121+
Node x = y.right;
122+
Node z = x.left;
123+
x.left = y;
124+
y.right = z;
125+
updateHeight(y);
126+
updateHeight(x);
127+
return x;
128+
}
129+
130+
private void updateHeight(Node n) {
131+
n.height = 1 + Math.max(height(n.left), height(n.right));
132+
}
133+
134+
private int height(Node n) {
135+
return n == null ? -1 : n.height;
136+
}
137+
138+
public int getBalance(Node n) {
139+
return (n == null) ? 0 : height(n.right) - height(n.left);
140+
}
141+
}

‎algorithms-miscellaneous-5/src/test/java/com/baeldung/algorithms/balancedbinarytree/AVLTreeUnitTest.java‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
package com.baeldung.algorithms.balancedbinarytree;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
public class AVLTreeUnitTest {
7+
8+
@Test
9+
public void givenEmptyTree_whenHeightCalled_shouldReturnMinus1() {
10+
AVLTree tree = new AVLTree();
11+
Assert.assertEquals(-1, tree.height());
12+
}
13+
14+
@Test
15+
public void givenEmptyTree_whenInsertCalled_heightShouldBeZero() {
16+
AVLTree tree = new AVLTree();
17+
tree.insert(1);
18+
Assert.assertEquals(0, tree.height());
19+
}
20+
21+
@Test
22+
public void givenEmptyTree_whenInsertCalled_treeShouldBeAvl() {
23+
AVLTree tree = new AVLTree();
24+
tree.insert(1);
25+
Assert.assertTrue(isAVL(tree));
26+
}
27+
28+
@Test
29+
public void givenSampleTree_whenInsertCalled_treeShouldBeAvl() {
30+
AVLTree tree = getSampleAVLTree();
31+
int newKey = 11;
32+
tree.insert(newKey);
33+
Assert.assertTrue(isAVL(tree));
34+
}
35+
36+
@Test
37+
public void givenSampleTree_whenFindExistingKeyCalled_shouldReturnMatchedNode() {
38+
AVLTree tree = getSampleAVLTree();
39+
int existingKey = 2;
40+
AVLTree.Node result = tree.find(existingKey);
41+
Assert.assertEquals(result.key, existingKey);
42+
}
43+
44+
@Test
45+
public void givenSampleTree_whenFindNotExistingKeyCalled_shouldReturnNull() {
46+
AVLTree tree = getSampleAVLTree();
47+
int notExistingKey = 11;
48+
AVLTree.Node result = tree.find(notExistingKey);
49+
Assert.assertNull(result);
50+
}
51+
52+
@Test
53+
public void givenEmptyTree_whenDeleteCalled_treeShouldBeAvl() {
54+
AVLTree tree = new AVLTree();
55+
tree.delete(1);
56+
Assert.assertTrue(isAVL(tree));
57+
}
58+
59+
@Test
60+
public void givenSampleTree_whenDeleteCalled_treeShouldBeAvl() {
61+
AVLTree tree = getSampleAVLTree();
62+
tree.delete(1);
63+
Assert.assertTrue(isAVL(tree, tree.getRoot()));
64+
}
65+
66+
private boolean isAVL(AVLTree tree) {
67+
return isAVL(tree, tree.getRoot());
68+
}
69+
70+
private boolean isAVL(AVLTree tree, AVLTree.Node node) {
71+
if ( node == null )
72+
return true;
73+
int balance = tree.getBalance(node);
74+
return (balance <= 1 && balance >= -1) && isAVL(tree, node.left) && isAVL(tree, node.right);
75+
}
76+
77+
private AVLTree getSampleAVLTree() {
78+
AVLTree avlTree = new AVLTree();
79+
for (int i = 0; i < 10; i++)
80+
avlTree.insert(i);
81+
return avlTree;
82+
}
83+
}

0 commit comments

Comments
 (0)