Last active
November 28, 2016 12:38
-
-
Save amitsaurav/4612f0cf3770ea55bc37265b61a5eaf1 to your computer and use it in GitHub Desktop.
A balanced tree with minimal rebalances.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package trees; | |
import java.util.LinkedList; | |
import java.util.Queue; | |
/** | |
* There are bugs around odd and even array length and last element being not added but this is the | |
* general structure of the code. | |
* | |
* @author amitsaurav | |
* | |
*/ | |
public class MinimalBalancedTree { | |
/** | |
* Inserts a sorted array into a tree and returns the head | |
* | |
* @param array | |
* @return Head of the BST | |
*/ | |
public Node insert(int[] array) { | |
Queue<NodeRangeWrapper> q = new LinkedList<>(); | |
NodeRangeWrapper initialRange = new NodeRangeWrapper(0, array.length, array); | |
q.add(initialRange); | |
while (!q.isEmpty()) { | |
NodeRangeWrapper currentRange = q.remove(); | |
if (currentRange.low < currentRange.mid - 1) { | |
NodeRangeWrapper temp = new NodeRangeWrapper(currentRange.low, currentRange.mid, array); | |
currentRange.node.left = temp.node; | |
q.add(temp); | |
} | |
if (currentRange.mid < currentRange.high - 1) { | |
NodeRangeWrapper temp = new NodeRangeWrapper(currentRange.mid, currentRange.high, array); | |
currentRange.node.right = temp.node; | |
q.add(temp); | |
} | |
} | |
return initialRange.node; | |
} | |
/** | |
* Prints the tree in level-order (for debugging purposes only) | |
* | |
* @param head | |
*/ | |
public static void printTree(Node head) { | |
Queue<Node> queue = new LinkedList<Node>(); | |
queue.add(head); | |
while (!queue.isEmpty()) { | |
Node n = queue.remove(); | |
System.out.println(n.value); | |
if (n.left != null) | |
queue.add(n.left); | |
if (n.right != null) | |
queue.add(n.right); | |
} | |
} | |
public static void main(String[] args) { | |
MinimalBalancedTree tree = new MinimalBalancedTree(); | |
Node root = tree.insert(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }); | |
printTree(root); | |
} | |
private static class NodeRangeWrapper { | |
final int low; | |
final int high; | |
final int mid; | |
final Node node; | |
public NodeRangeWrapper(int l, int h, int [] array) { | |
low = l; | |
high = h; | |
mid = (l + h) / 2; | |
node = new Node(array[mid]); | |
} | |
} | |
private static class Node { | |
Node left; | |
Node right; | |
int value; | |
public Node(int v) { | |
value = v; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment