Skip to content

Instantly share code, notes, and snippets.

@chouclee
Created July 14, 2014 16:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save chouclee/a9ff7a74f7768b217319 to your computer and use it in GitHub Desktop.
Save chouclee/a9ff7a74f7768b217319 to your computer and use it in GitHub Desktop.
[CC150][4.6] Write an algorithm to find the ‘next’ node (i e , in-order successor) of a given node in a binary search tree where each node has a link to its parent.
// if current node has right subtree, return most left node of the right child.
// else trace back to its parent, if the parent is smaller than current node, then consider parent's parent...
// until parent node is bigger than current node.
public class findNextNode<Key extends Comparable<Key>> {
private Node root;
private class Node {
private Key key;
private Node left, right;
private Node parent;
public Node(Key key, Node parent) {
this.key = key;
this.parent = parent;
}
}
public findNextNode(Key[] keys) {
for (Key key : keys)
root = put(root, key, null);
}
public Key findNext(Key key) {
Node curr = find(root, key);
Node next;
if (curr.right != null) {
next = curr.right;
while (next.left != null)
next = next.left;
}
else {
next = curr.parent;
while (next.key.compareTo(key) < 0)
next = next.parent;
}
return next.key;
}
private Node find(Node x, Key key) {
if (x == null)
return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return find(x.left, key);
else if (cmp > 0) return find(x.right, key);
else return x;
}
private Node put(Node x, Key key, Node parent) {
if (x == null)
return new Node(key, parent);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, x);
if (cmp > 0) x.right = put(x.right, key, x);
return x;
}
public static void main(String[] args) {
int N = 20;
Integer[] data = new Integer[N];
for (int i = 0; i < N; i++) data[i] = i;
findNextNode<Integer> test = new findNextNode<Integer>(data);
for (int i = 0; i < N - 1; i++)
System.out.println("next to " + i + ": " + test.findNext(i));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment