Answer the question
In order to leave comments, you need to log in
How to implement rotation from node AA of the tree?
Asked to help with the implementation of AA-Tree. There are a lot of ready-made algorithms on the Internet, but there is a condition that the node itself should not be transferred to this or that method, and the method should be called from the node itself.
And here's something I sat down ... How, for example, to implement the skew and split functions in this style?
public class AATree<T extends Comparable<? super T>> {
public BinaryNode root;
public int rotationCount;
private BinaryNode lastNode;
private BinaryNode deletedNode;
private int size;
public AATree() {
}
public int size() {
return size;
}
public boolean insert(T element) {
if (element == null) throw new NullPointerException();
if (root == null) {
root = new BinaryNode(element);
size++;
return true;
}
return root.insert(element);
}
public class BinaryNode {
private T element;
private BinaryNode leftChild;
private BinaryNode rightChild;
private int level;
public BinaryNode(T element) {
this.element = element;
this.leftChild = null;
this.rightChild = null;
this.level = 1;
}
public T getElement() {
return this.element;
}
public int getLevel() {
return this.level;
}
public boolean insert(T element) {
int v = element.compareTo(this.element);
if (v < 0) {
if (leftChild != null) return leftChild.insert(element);
leftChild = new BinaryNode(element);
size++;
}
if (v > 0) {
if (rightChild != null) return rightChild.insert(element);
rightChild = new BinaryNode(element);
size++;
} else {
return false;
}
skew();
split();
return true;
}
private void split() {
if (rightChild != null && rightChild.rightChild != null && rightChild.level == this.level) {
this.level++;
BinaryNode swap = this.rightChild;
this.rightChild = swap.leftChild;
swap.leftChild = this;
// this = temp; - тут бред
}
}
private void skew() {
if (leftChild != null && leftChild.level >= level) {
BinaryNode swap = this.leftChild;
this.leftChild = swap.rightChild;
swap.rightChild = this;
// this = swap; - тут бред
}
}
}
}
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question