Skip to content

Commit cae420b

Browse files
author
Lord-of-Algorithms
committed
Implement BST, AVL, and Red-Black Trees with basic operations and traversal methods
1 parent 46cc239 commit cae420b

18 files changed

+1938
-0
lines changed

‎src/binarytree/BinaryTreePrinter.java

Lines changed: 309 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,309 @@
1+
/*
2+
* Copyright 2019 (C) github.com/Lord-of-Algorithms
3+
*
4+
* Licensed under the Apache License, Version 2.0 (the "License");
5+
* you may not use this file except in compliance with the License.
6+
* You may obtain a copy of the License at
7+
*
8+
* http://www.apache.org/licenses/LICENSE-2.0
9+
*
10+
* Unless required by applicable law or agreed to in writing, software
11+
* distributed under the License is distributed on an "AS IS" BASIS,
12+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13+
* See the License for the specific language governing permissions and
14+
* limitations under the License.
15+
*/
16+
17+
package binarytree;
18+
19+
import java.util.*;
20+
21+
enum NumberDigit {
22+
DoubleDigit(2),
23+
ThreeDigit(3),
24+
FourDigit(4);
25+
26+
int digit;
27+
28+
NumberDigit(int digit) {
29+
this.digit = digit;
30+
}
31+
}
32+
33+
public final class BinaryTreePrinter {
34+
35+
private final static int MaxLevel = 6;
36+
private final static String Blank = " ";
37+
private final static int MinNodeKeyValue = 0;
38+
39+
private static int maxNodeKeyValue;
40+
private static int keyNodeValueDigits;
41+
42+
private BinaryTreePrinter() {
43+
// prevent initializing
44+
}
45+
46+
/**
47+
* Prints the binary tree
48+
*
49+
* @param root The root of the tree
50+
*/
51+
public static void print(INode root) {
52+
print(root, NumberDigit.DoubleDigit, MaxLevel);
53+
}
54+
55+
/**
56+
* Prints the binary tree
57+
*
58+
* @param root The root of the tree
59+
* @param keyNumberDigit The number digit of the key
60+
* @param maxTreeLevel The max tree level
61+
*/
62+
public static void print(INode root, NumberDigit keyNumberDigit, int maxTreeLevel) {
63+
if (root == null) {
64+
System.out.println("The tree is empty.");
65+
return;
66+
}
67+
keyNodeValueDigits = keyNumberDigit.digit;
68+
calculateValidMaxNodeKeyValue(keyNumberDigit);
69+
70+
int maxLevel = getTreeMaxLevel(root);
71+
if (maxLevel > maxTreeLevel) {
72+
throw new RuntimeException(
73+
"\n\n\n" +
74+
"==========================================" +
75+
"\nMax level of the binary tree that can be printed is "
76+
+ maxTreeLevel + ". Current level is " + maxLevel +
77+
".\n==========================================\n\n\n");
78+
}
79+
if (maxLevel == maxTreeLevel) {
80+
// We reduce the length of edges connecting the nodes. It doesn't change the structure of the tree,
81+
// but makes the printed tree smaller. We do it only for edge case, when level of tree equals to maxTreeLevel.
82+
maxLevel -= 1;
83+
}
84+
85+
var levelMap = new LinkedHashMap<INode, Integer>(); // position plays a role
86+
int level = 0;
87+
fillLevelMap(root, level, levelMap);
88+
89+
var nodeStartMarginMap = new HashMap<INode, Integer>();
90+
fillNodeStartMarginMap(root, levelMap, true, 0, false, nodeStartMarginMap, maxLevel - 1);
91+
System.out.println();
92+
printBinaryTree(root, maxLevel - 1, nodeStartMarginMap, levelMap);
93+
System.out.println("\n");
94+
}
95+
96+
private static void calculateValidMaxNodeKeyValue(NumberDigit keyNumberDigit) {
97+
switch (keyNumberDigit) {
98+
case ThreeDigit:
99+
maxNodeKeyValue = 999;
100+
break;
101+
case FourDigit:
102+
maxNodeKeyValue = 9999;
103+
break;
104+
default:
105+
maxNodeKeyValue = 99;
106+
}
107+
}
108+
109+
private static int getTreeMaxLevel(INode node) {
110+
if (node == null)
111+
return 0;
112+
return Math.max(getTreeMaxLevel(node.getLeft()), getTreeMaxLevel(node.getRight())) + 1;
113+
}
114+
115+
/**
116+
* Associates each node with its level in the binary tree.
117+
*/
118+
private static void fillLevelMap(
119+
INode root,
120+
int level,
121+
Map<INode, Integer> levelMap
122+
) {
123+
if (root != null) {
124+
125+
if (root.getKey() < MinNodeKeyValue || root.getKey() > maxNodeKeyValue) {
126+
throw new RuntimeException("\n\n\n" +
127+
"==========================================" +
128+
"\nThe key of the node must be >= "
129+
+ MinNodeKeyValue + " and <= " + maxNodeKeyValue +
130+
"\n==========================================\n\n\n");
131+
}
132+
fillLevelMap(root.getLeft(), level + 1, levelMap);
133+
levelMap.put(root, level);
134+
fillLevelMap(root.getRight(), level + 1, levelMap);
135+
}
136+
}
137+
138+
/**
139+
* Calculates startMargin for each node (in pre-order way) and associate this value
140+
* with this node by using a map. Later these margins will be used
141+
* for printing.
142+
*
143+
* @param startMargin start - means from the left (to not mix with left child. There is no connection between these terms).
144+
*/
145+
private static void fillNodeStartMarginMap(
146+
INode root,
147+
Map<INode, Integer> nodeLevelMap,
148+
boolean isRoot,
149+
int startMargin,
150+
boolean isLeftChild,
151+
Map<INode, Integer> nodeStartMarginMap,
152+
int maxLevel) {
153+
154+
if (root != null) {
155+
int nodeLevel = nodeLevelMap.get(root);
156+
// Each level has its own space between nodes
157+
int spaceBetweenNodes = keyNodeValueDigits * ((int) Math.pow(2, (maxLevel - nodeLevel + 1)) - 1);
158+
159+
if (isRoot) {
160+
startMargin = keyNodeValueDigits * ((int) Math.pow(2, (maxLevel - nodeLevel)) - 1);
161+
} else if (isLeftChild) {
162+
// for left child the margin is smaller
163+
startMargin = startMargin - spaceBetweenNodes / keyNodeValueDigits - keyNodeValueDigits / 2;
164+
} else {
165+
// for right child the margin is bigger
166+
startMargin = startMargin + spaceBetweenNodes / keyNodeValueDigits + keyNodeValueDigits / 2;
167+
}
168+
169+
nodeStartMarginMap.put(root, startMargin);
170+
171+
fillNodeStartMarginMap(root.getLeft(), nodeLevelMap, false, startMargin, true, nodeStartMarginMap, maxLevel);
172+
fillNodeStartMarginMap(root.getRight(), nodeLevelMap, false, startMargin, false, nodeStartMarginMap, maxLevel);
173+
}
174+
}
175+
176+
/**
177+
* Uses breadth-first traversal to print the nodes
178+
*/
179+
private static void printBinaryTree(
180+
INode root,
181+
int maxLevel,
182+
Map<INode, Integer> startMarginMap,
183+
Map<INode, Integer> levelMap
184+
) {
185+
186+
if (root != null) {
187+
Queue<INode> queue = new LinkedList<>();
188+
queue.add(root);
189+
var currentLevel = 0;
190+
var currentPosition = 0;
191+
192+
while (!queue.isEmpty()) {
193+
INode node = queue.remove();
194+
195+
// Get the level and margin from the maps for given node.
196+
int startMargin = startMarginMap.get(node);
197+
var level = levelMap.get(node);
198+
199+
if (currentLevel != level) {
200+
// New level - go to next line
201+
System.out.println();
202+
203+
var edgeHeight = Math.pow(2, maxLevel - currentLevel) - 1;
204+
for (int i = 0; i < edgeHeight; i++) {
205+
printEdges(currentLevel, startMarginMap, levelMap, i);
206+
}
207+
208+
currentLevel = level;
209+
currentPosition = 0;
210+
}
211+
212+
// Because each node in the level is printed not from 0 position
213+
// we need to subtract node's startMargin with current position.
214+
int spacesBetweenNodes = startMargin - currentPosition;
215+
for (int i = 0; i < spacesBetweenNodes; i++) {
216+
System.out.print(Blank);
217+
currentPosition++;
218+
}
219+
printNode(node);
220+
// Remember that each number occupies keyNodeValueDigits digits. So
221+
// we need to increase the current position on this value.
222+
currentPosition += keyNodeValueDigits;
223+
224+
if (node.getLeft() != null) {
225+
queue.add(node.getLeft());
226+
}
227+
228+
if (node.getRight() != null) {
229+
queue.add(node.getRight());
230+
}
231+
}
232+
}
233+
}
234+
235+
/**
236+
* Prints the value of the node's key.
237+
* <p>
238+
* Here we adjust the "x-position" of the value to get the good looking view.
239+
*/
240+
private static void printNode(INode node) {
241+
var key = node.getKey();
242+
if (keyNodeValueDigits == NumberDigit.DoubleDigit.digit) {
243+
if (key < 10) {
244+
System.out.print(Blank + node);
245+
} else {
246+
System.out.print(node);
247+
}
248+
} else if (keyNodeValueDigits == NumberDigit.ThreeDigit.digit) {
249+
if (key < 10) {
250+
System.out.print(Blank + node + Blank);
251+
} else if (key < 100) {
252+
System.out.print(node + Blank);
253+
} else {
254+
System.out.print(node);
255+
}
256+
} else if (keyNodeValueDigits == NumberDigit.FourDigit.digit) {
257+
if (key < 10) {
258+
System.out.print(Blank + node + Blank + Blank);
259+
} else if (key < 100) {
260+
System.out.print(Blank + node + Blank);
261+
} else if (key < 1000) {
262+
System.out.print(node + Blank);
263+
} else {
264+
System.out.print(node);
265+
}
266+
}
267+
}
268+
269+
private static void printEdges(
270+
int currentLevel,
271+
Map<INode, Integer> startMarginMap,
272+
Map<INode, Integer> levelMap,
273+
int iteration
274+
) {
275+
// Get the list of nodes for each currentLevel
276+
var levelNodeKeys = new ArrayList<INode>();
277+
for (Map.Entry<INode, Integer> entry : levelMap.entrySet()) {
278+
var nodeKey = entry.getKey();
279+
var level = entry.getValue();
280+
if (level == currentLevel) {
281+
levelNodeKeys.add(nodeKey);
282+
}
283+
}
284+
285+
var spaceBetweenSlashAndBackSlash = new StringBuilder();
286+
// The space between slash and backslash increases on two positions each iteration
287+
spaceBetweenSlashAndBackSlash.append(Blank.repeat(Math.max(0, 2 * iteration)));
288+
289+
int currentPosition = 0;
290+
for (INode node : levelNodeKeys) {
291+
int startMargin = startMarginMap.get(node);
292+
int slashPosition = startMargin - currentPosition - iteration + (keyNodeValueDigits / 2 - 1);
293+
294+
// Starting from the left border we print the blanks
295+
for (int i = 0; i < slashPosition; i++) {
296+
System.out.print(Blank);
297+
currentPosition++;
298+
}
299+
300+
// If the node doesn't have a child, we replace the child's place with a blank.
301+
String slash = node.getLeft() != null ? "/" : Blank;
302+
var backSlash = node.getRight() != null ? "\\" : Blank;
303+
304+
System.out.print(slash + spaceBetweenSlashAndBackSlash + backSlash);
305+
currentPosition += 2 * (iteration + 1);
306+
}
307+
System.out.println();
308+
}
309+
}

‎src/binarytree/INode.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package binarytree;
2+
3+
/**
4+
* Interface defining the basic structure and functionality of a node in a binary tree.
5+
*/
6+
public interface INode {
7+
8+
/**
9+
* Gets the key value of this node.
10+
*/
11+
int getKey();
12+
13+
/**
14+
* Gets the left child of this node.
15+
*
16+
* @return The left child node.
17+
*/
18+
INode getLeft();
19+
20+
/**
21+
* Gets the right child of this node.
22+
*
23+
* @return The right child node.
24+
*/
25+
INode getRight();
26+
27+
/**
28+
* Processes or visits the current node.
29+
*/
30+
void visit();
31+
}

0 commit comments

Comments
 (0)