(Updated September 4, 2024)
Table of contents
Overview
The tree data structure provides a means of implementing sorted data in the form of a modified linked list such that traversals are far less expensive and approach O(log2n).
We say they approach because the tree is not balanced, and we will have issues in the traversal. The first tree algorithm is an essential tree model that performs no specific balancing to improve performance.
Later, we will examine balanced tree algorithms and move from binary (two children) to n-ary (many children).
Basic Tree
The premise of the tree is to provide organized data in which each data node has at most two children. The organization of the data is irrelevant in a basic binary tree.
A binary search tree will have the data nodes arranged in sorted form. Branches to the left contain data that are less than the current node, while branches to the right are greater than the current node.
Each node of a binary tree has two possible children. Since each node can contain data and two possible paths to the additional data, we say that a node with no children is a leaf while a node with one or more children is a branch.
The sorted array is below:
0 1 2 3 4 5 6 7 8 9 ------------------------------------------------- | 3 | 6 | 13 | 24 | 56 | 76 | 78 | 88 | 92 | 99 | ------------------------------------------------- Sorted array of values.
Could be arranged in a tree such as:
1 76
/ \
/ \
/ \
/ \
2 13 88
/ \ / \
3 6 24 78 92
/ \ \
4 3 56 99
A nearly balanced tree with a height of 4.
We say could because it will depend on the order in which the values were added. As we add values to the tree, we descend the current tree arrangement to determine the position to place the new value.
Given the tree view, we could say the values were added in the order:
76, 13, 88, 6, 24, 78, 92, 3, 56 and 99
or they could have been added:
76, 13, 24, 6, 56, 3, 88, 92, 99 and 78
or, even:
76, 88, 78, 13, 24, 92, 6, 99, 56 and 3
Any of the above sequences (and a few others) would produce that tree. Note that the value of 76 is the first added in all cases. The first entry into a tree will always be the root (until otherwise acted upon). This is how we get the root value of 76.
To draw the tree with any of the value lists:
- Start with the root being the first value.
- When adding a new value after the root, follow the path:
- Left, if the value being added is less than the current position.
- Right, if greater.
- When you reach a leaf, stop.
- If the value is less than the current node, hang it on the left.
- If the value is greater than the current node, hang it on the right.
The next bit of code
import java.util.*;
public class IntTree {
Node root;
// Node to implement two paths: left and right
private class Node {
int data;
Node left, right;
public Node (int item) {
data = item;
left = null;
right = null;
}
}
// insert item into a tree root.
public void insert(int item) {
Node n, p, back;
n = new Node(item);
p = root;
back = null;
while (p != null) {
back = p;
if (p.data > item)
p = p.left;
else
p = p.right;
}
if (back == null )
root = n;
else {
if (back.data > item)
back.left = n;
else
back.right = n;
}
}
// delete item from a tree
public void delete(int item) {
Node tdb, tbdback = null, back = null, p = root, temp;
// find the node to delete.
while ( p != null ) {
if ( p.data == item )
break;
back = p;
if (p.data > item)
p = p.left;
else
p = p.right;
}
// not found - nothing to do
if ( p == null )
throw new NoSuchElementException();
// save our place
tbdback = back;
tdb = p;
// Case of 0 or 1 child
if ( p.right == null )
p = p.left;
else if ( p.left == null )
p = p.right;
// two children
else {
temp = p.left;
back = p;
// find largest value less than one being deleted
while ( temp.right != null ) {
back = temp;
temp = temp.right;
}
// move the data
p.data = temp.data;
// relink tree removing the node used for replacement
if ( back == p )
back.left = temp.left;
else
back.right = temp.left;
}
// were we deleting the root?
if ( tdb == root )
root = p;
else if (tbdback.left == tdb)
tbdback.left = p;
else
tbdback.right = p;
}
public boolean search(int item) {
Node p = root;
while (p != null) {
if (p.data == item) {
return true;
} else if (p.data > item)
p = p.left;
else p = p.right;
}
return false;
}
public void prettytree() {
prettytree2(root, 0);
}
private void prettytree2(Node r, int i) {
String s = "";
if ( r == null && i == 0 )
System.out.println("EMPTY");
if ( r != null ) {
prettytree2(r.right, i + 4);
for (int x = 0; x < i; x++)
s = s + " ";
System.out.print(s);
System.out.println(r.data);
prettytree2(r.left, i + 4);
}
}
public void inorder() {
inorder2(root);
}
public static void inorder2(Node r) {
if ( r != null ) {
inorder2(r.left);
System.out.print(r.data + " ");
inorder2(r.right);
}
}
public void preorder() {
preorder2(root);
}
private void preorder2(Node r) {
if ( r != null ) {
System.out.print(r.data + " ");
preorder2(r.left);
preorder2(r.right);
}
System.out.println();
}
public void postorder() {
postorder2(root);
}
private void postorder2(Node r) {
if ( r != null ) {
postorder2(r.left);
postorder2(r.right);
System.out.print(r.data + " ");
}
}
public static void main(String[] args) {
int x;
IntTree tree = new IntTree();
int[] in = {9,3,5,7,11,1,75,68,70};
int[] out = {7,68,75,3,9,11};
/*
* The data sets up a tree to test removal of nodes with
* no children (7), one child right (68), one child left (75),
* two children (3) and the root (9).
*/
for (x = 0; x < in.length; x++) {
tree.insert(in[x]);
tree.prettytree();
System.out.println("==========");
}
System.out.println("\nSearching for 75 : " + tree.search(75));
System.out.println("Searching for 100 : " + tree.search(100) + "\n");
System.out.println("==========");
for (x = 0; x < out.length; x++) {
tree.delete(out[x]);
tree.prettytree();
System.out.println("==========");
}
}
}
The output is shown below and has been broken up into sections with commentary on what event occurred to produce the output.
9
==========
9
3
==========
9
5
3
==========
9
7
5
3
==========
11
9
7
5
3
==========
11
9
7
5
3
1
==========
75
11
9
7
5
3
1
==========
75
68
11
9
7
5
3
1
==========
75
70
68
11
9
7
5
3
1
==========
Searching for 75 : true
Searching for 100 : false
==========
75
70
68
11
9
5
3
1
==========
75
70
11
9
5
3
1
==========
70
11
9
5
3
1
==========
70
11
9
5
1
==========
70
11
5
1
==========
70
5
1
==========
Red-Black Tree
AVL Tree
public class AVLTree {
public class Node {
int data;
int height;
Node left;
Node right;
Node(int data) {
this.data = data;
}
}
private Node root;
public Node find(int data) {
Node current = root;
while (current != null) {
if (current.data == data) {
break;
}
current = current.data < data ? current.right : current.left;
}
return current;
}
public void insert(int data) {
root = insert(root, data);
}
public void delete(int data) {
root = delete(root, data);
}
public Node getRoot() {
return root;
}
public int height() {
return root == null ? -1 : root.height;
}
private Node insert(Node node, int data) {
if (node == null) {
return new Node(data);
} else if (node.data > data) {
node.left = insert(node.left, data);
} else if (node.data < data) {
node.right = insert(node.right, data);
} else {
throw new RuntimeException("duplicate data!");
}
return rebalance(node);
}
private Node delete(Node node, int data) {
if (node == null) {
return node;
} else if (node.data > data) {
node.left = delete(node.left, data);
} else if (node.data < data) {
node.right = delete(node.right, data);
} else {
if (node.left == null || node.right == null) {
node = (node.left == null) ? node.right : node.left;
} else {
Node mostLeftChild = mostLeftChild(node.right);
node.data = mostLeftChild.data;
node.right = delete(node.right, node.data);
}
}
if (node != null) {
node = rebalance(node);
}
return node;
}
private Node mostLeftChild(Node node) {
Node current = node;
/* loop down to find the leftmost leaf */
while (current.left != null) {
current = current.left;
}
return current;
}
private Node rebalance(Node z) {
updateHeight(z);
int balance = getBalance(z);
if (balance > 1) {
if (height(z.right.right) > height(z.right.left)) {
z = rotateLeft(z);
} else {
z.right = rotateRight(z.right);
z = rotateLeft(z);
}
} else if (balance < -1) {
if (height(z.left.left) > height(z.left.right)) {
z = rotateRight(z);
} else {
z.left = rotateLeft(z.left);
z = rotateRight(z);
}
}
return z;
}
private Node rotateRight(Node y) {
Node x = y.left;
Node z = x.right;
x.right = y;
y.left = z;
updateHeight(y);
updateHeight(x);
return x;
}
private Node rotateLeft(Node y) {
Node x = y.right;
Node z = x.left;
x.left = y;
y.right = z;
updateHeight(y);
updateHeight(x);
return x;
}
private void updateHeight(Node n) {
n.height = 1 + Math.max(height(n.left), height(n.right));
}
private int height(Node n) {
return n == null ? -1 : n.height;
}
public int getBalance(Node n) {
return (n == null) ? 0 : height(n.right) - height(n.left);
}
}
B-Tree
Special-Purpose Trees
In this section, we will look at a special-purpose tree implementation. This was developed to help examine how a directory structure might be implemented using trees.
This also addresses a need to intentionally violate the standard premise of all details being hidden from the user. When using a real API for filesystems, the details are front and center, allowing the user to glean a great deal of information about the implementation, but perhaps not all of it.
We begin with the Node class. Note that the Node class implements a List for the children. This is the simplest to implement since making an ArrayList of all the children is incredibly simple to maintain.
If you were to implement your own linked list model, consider all possible places where new bugs may be introduced. This often becomes a "use what is already available" decision.
Note as well that the parent is maintained in this code. This allows for a good deal of flexibility in determining the location of an object in the tree. Consider the complexities of a filesystem and how you may have many objects of the same name occurring at many levels. This allows us to determine the fully qualified path of a filesystem object by following parent links to the root.
Finally, a boolean value, dir, is included to determine if an object is a branch (directory) or a leaf (file).
import java.util.ArrayList;
import java.util.List;
public class DirNode {
private String name;
private boolean dir;
private boolean symlink;
private String linkTarget;
private List<DirNode> children;
private DirNode parent;
public DirNode(String name, boolean dir) {
this.name = name;
this.dir = dir;
if ( dir )
this.children = new ArrayList<DirNode>();
}
public boolean addDir(String value) {
return addChild(value, true);
}
public boolean addFile(String value) {
return addChild(value, false);
}
private boolean addChild(String value, boolean dir) {
if (!hasChild(value)) {
DirNode n = new DirNode(value, dir);
n.setParent(this);
children.add(n);
return true;
}
return false;
}
private void setSymLink(String target) {
symlink = true;
linkTarget = target;
}
public boolean addSymLink(String target, String value) {
if (!hasChild(value)) {
DirNode n = new DirNode(value, false);
n.setParent(this);
n.setSymLink(target);
children.add(n);
return true;
}
return false;
}
public boolean removeFile(String value) {
return removeChild(value, false);
}
public boolean removeDir(String value) {
return removeChild(value, true);
}
private boolean removeChild(String value, boolean dir) {
List<DirNode> list = getChildren();
for (DirNode n : list)
if (n.getName().equals(value)) {
// remove a file
if (!dir && !n.isDir())
return list.remove(n);
else if (dir) {
// remove an empty directory
if ( n.isDir() && n.children.size() == 0)
return list.remove(n);
}
}
// would really like more than boolean...
return false;
}
public boolean hasChild(String value) {
List<DirNode> list = getChildren();
for (DirNode n : list)
if (n.getName().equals(value))
return true;
return false;
}
public String getName() {
return this.name;
}
public void setName(String name) {
this.name = name;
}
public DirNode getParent() {
return this.parent;
}
public String getTarget() {
return linkTarget;
}
public void setDir() {
this.dir = true;
}
public void setParent(DirNode parent) {
this.parent = parent;
}
public List getChildren() {
return this.children;
}
public DirNode getChild(String value) {
List<DirNode> list = getChildren();
for (int i = 0; i < list.size(); i++) {
DirNode n = list.get(i);
if (n.getName().equals(value))
return n;
}
return null;
}
@Override
public boolean equals(Object obj) {
if (null == obj)
return false;
if (obj instanceof DirNode) {
if (((DirNode)obj).getName().equals(this.name))
return true;
}
return false;
}
public boolean isDir() {
return dir;
}
public boolean isSymLink() {
return symlink;
}
public String fullPath() {
DirNode p = this;
String path="";
if ( p.parent == null)
return "/";
while (p != null) {
if (path.length() == 0)
path = p.getName() + "";
else
path = p.getName() + "/" + path;
p = p.getParent();
}
return path;
}
}
The actual tree code is relatively sparse since the tree is being used more as an anchor than the de-facto content manager.
import java.util.List;
public class NAryTree {
private DirNode root;
// Tree constructor
public NAryTree(DirNode root) {
this.root = root;
root.setDir();
}
public DirNode getRoot() {
return root;
}
public boolean isEmpty() {
return root == null;
}
public void printTree() {
System.out.println("/");
printTree(root, 1);
}
private void printTree(DirNode n, int l) {
List<DirNode> list = n.getChildren();
for (DirNode o : list) {
if (l >0) {
for ( int x = 0; x < l; x++)
System.out.print(" ");
}
//System.out.println("isSymlink()" + o.isSymLink());
if ( o.isSymLink() )
System.out.println(o.getName() + " -> " + o.getTarget());
else
System.out.println(o.getName() + (o.isDir() ? " (DIR)" : " (FILE)"));
if (o.isDir())
printTree(o, l+1);
}
}
}
The Directories class is a program that exercises the directory tree implementation by creating a command line interface to run some basic tools for exercising the code paths of Node.
import java.util.Scanner;
public class Directories {
static Scanner kb = new Scanner(System.in);
public static void main(String[] args) {
DirNode root = new DirNode("", true);
NAryTree fs = new NAryTree(root);
DirNode cwd = fs.getRoot();
System.out.print("cmd> ");
while (kb.hasNext()) {
// get the command
String line = kb.nextLine(), dst;
// get parts
String[] parts = line.split("\\s+");
if (parts.length > 0) {
String cmd = parts[0];
switch (cmd) {
case "mkdir":
//if parts
dst = parts[1];
if (!cwd.addDir(dst))
System.out.println("Object \"" + cwd.getChild(dst).fullPath() + "\" exists.");
break;
case "rmdir":
dst = parts[1];
// determine if we can remove
DirNode c = cwd.getChild(dst);
if ( c == null )
System.out.println("Object \"" + dst + "\" does not exist.");
else if (!c.isDir())
System.out.println("Object \"" + dst + "\" is not a directory.");
else if (!cwd.removeDir(dst))
System.out.println("Directory \"" + dst + "\" is not empty.");
break;
case "ln":
String path = parts[1];
dst = parts[2];
cwd.addSymLink(path, dst);
break;
case "rm":
dst = parts[1];
if (!cwd.removeFile(dst))
System.out.println("Object \"" + dst + "\" does not exist.");
case "rmpath":
break;
case "tree":
fs.printTree();
break;
case "touch":
dst = parts[1];
if (!cwd.addFile(dst))
System.out.println("Object \"" + cwd.getChild(dst).fullPath() + "\" exists.");
break;
//case "up":
case "cd":
if (parts.length == 1)
cwd = fs.getRoot();
else if ( parts[1].equals("..")) {
cwd = cwd.getParent();
}
else {
dst = parts[1];
if ( cwd.hasChild(dst)) {
DirNode d = cwd.getChild(dst);
if (d.isDir())
cwd = d;
else {
System.out.println(dst + " is not a directory.");
}
} else {
System.out.println("The directory \"" + dst + "\" does not exist.");
}
}
break;
case "pwd":
System.out.println(cwd.fullPath());
break;
case "quit":
System.exit(0);
break;
default:
System.out.println("Unknown command: \"" + cmd);
break;
}
}
System.out.print("cmd> ");
}
}
}