Perfect Tree, is Binary one !
Tree dictate how to organize data. It’s a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root.
The root node does not have a parent.
In Java class hierarchy the root is Object class.Every object in java JDK is extends from Object class.
For tree characteristics:
- Every item in the tree is a node
- The node at the top of the tree is the root
- Every no-root node has one and only one parent
- A leaf node has no children
- A singleton tree has only one node which is the root
- A path is a sequence of nodes required to go from one node to another.
Notably, we cannot cyclique paths,we cannot find a path that cross a node different times.
The Binary Tree,is the most important tree.It has this characteristics:
- Every node has 0, 1, or 2 children
- Children are referred to as left child and right child
In practice, we use binary search trees(BST).it can perform insertions, deletions, and retrievals in O(logn) time.
The left child always has a smaller value than its parent, and the right child has a larger value than its parent.This means everything to the left of the root is less than the value of the root, and everything to the right of the root is greater than the value of the root.Because of that, we can do binary search.
Importantly, binary search can be done in one of three levels (Traversal ways)
- Level — visit nodes on each level
- Pre-order — visit the root of every subtree first
- Post-order visit the root of every subtree last
In-order level visit left child, then root, then right child. The data has to be sorted.
Moreover, for deleting node with two children:
- Need to figure out what the replacement node will be
- Want minimal disruption to the existing tree structure
- Can take the replacement node from the deleted node’s left subtree or right subtree
- If taking it from the right subtree, we have to take the smallest value in the right subtree
- Choose one and stick to it
Example of Implementation:
- TreeNode class is a Node class
public class TreeNode {
// == fields ==
private int data;
private TreeNode left;
private TreeNode right;
// == constructors ==
public TreeNode(int data) {
this.data = data;
}
// == public method ==
public void insert(int value) {
if (value == data) {
return;
}
if ( value < data) {
if (left == null) {
left = new TreeNode(value);
}
else {
left.insert(value);
}
}
else {
if (right == null) {
right = new TreeNode(value);
}
else {
right.insert(value);
}
}
}
public TreeNode get(int value) {
if(value == data) {
return this;
}
if (value < data) {
if (left != null){
return left.get(value);
}
}
else {
if (right != null) {
return right.get(value);
}
}
return null;
}
public int max() {
if (right == null) {
return data;
}
else {
return right.max();
}
}
public int min() {
if (left == null) {
return data;
}
else {
return left.min();
}
}
public void traverseInOrder() {
if(left != null) {
left.traverseInOrder();
}
System.out.print(data + ",");
if (right != null) {
right.traverseInOrder();
}
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
@Override
public String toString() {
return "data=" + data;
}
}- Tree class is our custom tree implementation
public class Tree {
private TreeNode root;
public void insert(int value){
if (root == null) {
root = new TreeNode(value);
}
else {
root.insert(value);
}
}
public void traverseInOrder() {
if (root != null) {
root.traverseInOrder();
}
}
public TreeNode get(int value) {
if (root != null) {
return root.get(value);
}
return null;
}
public void delete(int value) {
root = delete(root, value);
}
private TreeNode delete(TreeNode subtreeRoot, int value) {
if (subtreeRoot == null) {
return subtreeRoot;
}
if (value < subtreeRoot.getData()) {
subtreeRoot.setLeft(delete(subtreeRoot.getLeft(), value));
}
else if (value > subtreeRoot.getData()) {
subtreeRoot.setRight(delete(subtreeRoot.getRight(), value));
}
else {
// == Case 0 and 1 = node to delete has 0 or 1 child(ren)
if (subtreeRoot.getLeft() == null) {
return subtreeRoot.getRight();
}
else if (subtreeRoot.getRight() == null) {
return subtreeRoot.getLeft();
}
// case 3 : node to delete has 2 children
subtreeRoot.setData(subtreeRoot.getRight().min());
subtreeRoot.setRight(delete(subtreeRoot.getRight(), subtreeRoot.getData()));
}
return subtreeRoot;
}
public int max() {
if (root == null) {
return Integer.MAX_VALUE;
}
else {
return root.max();
}
}
public int min() {
if (root == null) {
return Integer.MIN_VALUE;
}
else {
return root.min();
}
}
}- Main class for testing :
public class Main {
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(25);
tree.insert(20);
tree.insert(15);
tree.insert(27);
tree.insert(30);
tree.insert(29);
tree.insert(26);
tree.insert(22);
tree.insert(32);
tree.traverseInOrder();
System.out.println();
System.out.println(tree.get(30));
System.out.println(tree.get(1000));
System.out.println(tree.min());
System.out.println(tree.max());
System.out.println("Delete from the tree");
tree.delete(32);
tree.traverseInOrder();
System.out.println();
}
}- The console output :
15,20,22,25,26,27,29,30,32,
data=30
null
15
32
Delete from the tree
15,20,22,25,26,27,29,30,
Conclusion:
As a conclusion, By searching in java JDK,to see what their is for trees,I found TreeMap class, is a binary search.
it’s implementation provides guaranteed log(n) time cost for containsKey,get, put and remove operations.
