Reputation: 81
AVL tree, java, successor, predecessor
I need to write successor and predecessor in this implementation, but I don't know how to do this without parent.May you suggest how best to make these methods? It is my TreeNode class
public class TreeNodee<K extends Comparable<K>> {
public K data;
int counter;
public TreeNodee<K> left, right;
public int height;
public int bf;
TreeNodee parent;
public TreeNodee(K data, TreeNodee parent) {
this.data = data;
counter = 1;
this.parent = parent;
}
public TreeNodee(K data) {
this.data = data;
counter = 1;
}
}
And that AVL tree:
public class AVL<T extends Comparable<T>> {
private TreeNodee<T> root;
private int size;
public void add(T data) {
if (contains(data)){
root.counter++;
return;
}
TreeNodee<T> newNode = new TreeNodee<T>(data);
root = add(root,newNode);
size++;
}
public boolean contains(T data) {
if (isEmpty())return false;
return contains(root,data);
}
private boolean contains(TreeNodee<T> current, T n){
if(current==null)return false;
if(compare(current.data,n) == 0){
return true;
}
else{
if(contains(current.right,n)){return true;}
else if(contains(current.left,n)){return true;}
return false;
}
}
private TreeNodee<T> add(TreeNodee<T> current, TreeNodee<T> n){
if (current == null){
n.bf = 0;
n.height = 0;
return n;
}
if (compare(n.data,current.data)>0){
current.right = rotate(add(current.right,n));
}
else{
current.left = rotate(add(current.left,n));
}
current = rotate(current);
return current;
}
public T remove(T data) {
if(!contains(data)){
return null;
}
root = rotate(remove(root,data));
size--;
return data;
}
private TreeNodee<T> remove(TreeNodee<T> current, T n){
if (compare(current.data,n)==0){
if(current.right == null && current.left== null){
return null;
}
else if(current.right == null){
return rotate(current.left);
}
else if(current.left == null){
return rotate(current.right);
}
else{
TreeNodee<T> pre = current.left;
TreeNodee<T> predecessor;
if (pre.right==null){
predecessor = pre;
predecessor.right = current.right;
}
else{
while(pre.right.right!=null){
pre = pre.right;
}
predecessor = pre.right;
pre.right = predecessor.left;
predecessor.left = current.left;
predecessor.right = current.right;
}
return predecessor;
}
}
else{
if (compare(n,current.data)>0){
current.right = rotate(remove(current.right,n));
}
else{
current.left = rotate(remove(current.left,n));
}
return rotate(current);
}
}
private TreeNodee<T> updateHeightAndBF(TreeNodee<T> n) {
int left,right;
left = n.left!=null ? n.left.height : -1;
right = n.right!=null ? n.right.height : -1;
n.bf = left-right;
n.height = (right>left ? right : left) +1;
return n;
}
private TreeNodee<T> rotate(TreeNodee<T> n) {
if(n == null)return n;
n = updateHeightAndBF(n);
if(n.bf<-1){
if(n.right.bf>0){
n = rightLeft(n);
}
else{
n = left(n);
}
}
else if(n.bf>1){
if(n.left.bf<0){
n = leftRight(n);
}
else{
n = right(n);
}
}
return n;
}
private TreeNodee<T> left(TreeNodee<T> n) {
TreeNodee<T> newRoot = n.right;
TreeNodee<T> temp = n.right.left;
n.right.left = n;
n.right = temp;
n = updateHeightAndBF(n);
return newRoot;
}
private TreeNodee<T> right(TreeNodee<T> n) {
TreeNodee<T> newRoot = n.left;
TreeNodee<T> temp = n.left.right;
n.left.right = n;
n.left = temp;
n = updateHeightAndBF(n);
return newRoot;
}
private TreeNodee<T> leftRight(TreeNodee<T> n) {
n.left = left(n.left);
n = right(n);
return n;
}
private TreeNodee<T> rightLeft(TreeNodee<T> n) {
n.right = right(n.right);
n = left(n);
return n;
}
public boolean isEmpty() {
if (size==0) return true;
return false;
}
private int compare(T d1,T d2){
if (d1==null && d2 == null){
return 0;
}
else if(d1==null){
return 1;
}
else if(d2==null){
return -1;
}
else{
return d1.compareTo(d2);
}
}
}
Upvotes: 0
Views: 1703
Answers (2)
Reputation: 12246
Parent links are not needed. You just have to go down the tree until you find a leaf. The question is "Which leaf contains the successor/predecessor of this value ?"
I'll take the direct predecessor of a node, considering you found the node in the tree. Also, I'll consider that the left children is smaller and the right children is higher than the current node.
Now, You've got your node, and you want to find its predecessor. Predecessor means you want the biggest node which is smaller. We'll just go through the cases.
Case 1: I have no children
Imagine your tree is this one and you want the predecessor of 3. Easy, this is his parent: 2. You can implement that with recursion, starting at the root of the tree. You just have to keep track of the best predecessor encountered on your way down.
2
/ \
1 3
The execution looks like this:
I'm at node 2, looking for the predecessor of 3 -> go right
I'm at node 3, looking for a predecessor of 3 -> go left
There's nothing, I didn't find any predecessor -> recursion rewinds
Crap, there is no predecessor found and 3 is not a predecessor of 3 -> recursion rewinds
Still no predecessor, but 2 is a predecessor of 3 -> recursion rewinds sending 2
Recursion ends: 2 is your value.
Now, what if the node you want to find the predecessor of has no left subtree and is the left child of its parent -> look for his grandparent on your way up the recursion until you find a smaller node.
What if there is no smaller node ? Then, this node is literally the smallest of the tree and he has no predecessor.
Case 2: I have childrens
That was the tough case, hopefully. Now, the node we're looking at has a left subtree. Easy: the predecessor is hidden somewhere in the left subtree. And what's nice is that it's the biggest node in it (by definition).
So your predecessor is the biggest node in your left subtree, which is easy to find -> go right until you hit a leaf.
What about the successor ? Same, but reversed. The successor of a node is the leftmost leaf of its right subtree. Again, the edge case is the same, with a chance that you're looking for the successor of the biggest node in the tree which does not exist.
Implementation hints
For implementing this kind of operation, it is easier to completely discard the fact that you're working on an AVL tree, just consider how you would do in a standard binary tree.
When you do not have parent pointers, you can go iteratively: start at the root, and always consider the parent, current, left children and right children at those operations. In fact, this approach is generally more complicated because you have lots of nodes to keep track of at the same time. Also, you have to update the value you found at each iteration, because there is no going up without pointer.
We tend to work recursively on binary trees because the structure itself is recursive. You can have parent in recursion by passing them all the time, but there not mandatory (here they're not necessary). You just have to remember that you're the parent of the node that just returned a value to you, and act accordingly.
It requires a bit of practice, but it rather intuitive once you've grasped your head over it.
Upvotes: 1
Reputation: 3992
I need to write successor and predecessor in this implementation, but I don't know how to do this without parent.
Mmmm... what?
public class TreeNodee<K extends Comparable<K>> {
public K data;
int counter;
public TreeNodee<K> left, right;
public int height;
public int bf;
// ------------------------------------
// Why, this parent is not good enough?
// |
// V
TreeNodee parent;
Upvotes: 0
Related Questions
- AVL TREE traversal in order
- AVL Tree for Java
- Implementing an AVL tree in JAVA
- Implementing a parent node in AVL tree
- Java - AVL tree search
- How do I implement an AVL tree in java? Why does compareTo say source unknown?
- AVL Tree Implementation for Java
- Using an AVL tree in java
- Analysis of AVL tree
- AVL tree management