Как реализовать поворот из нода AA дерева? Попросили помочь с реализацией AA-Tree. Готовых алгоритмов в интернете куча, но есть условие, что сам нод не должен передаваться тот или иной метод, а метод должен вызываться из самого нода.
И вот что-то я сел... Как в таком стиле к примеру реализовать функции skew и split?public class AATree> {
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 (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; - тут бред
}
}
}
}

Предыдущий
вопрос Следующий
вопрос

Чтобы реализовать поворот из нода AA-дерева, не передавая сам нод как параметр методу, можно воспользоваться следующим способом:

Создать методы skew и split внутри класса BinaryNode.Внутри этих методов обновлять ссылки на узлы и их уровни (level) без передачи текущего узла как параметра.Использовать ключевое слово this для обращения к текущему объекту (узлу) внутри методов skew и split.

Ниже приведен пример реализации методов skew и split внутри класса BinaryNode:

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;
updateReference(this, swap);
}
}
private void skew() {
if (leftChild != null && leftChild.level == this.level) {
BinaryNode swap = leftChild;
leftChild = swap.rightChild;
swap.rightChild = this;
updateReference(this, swap);
}
}
private void updateReference(BinaryNode oldNode, BinaryNode newNode) {
if (leftChild == oldNode) {
leftChild = newNode;
} else {
rightChild = newNode;
}
}
}
}

Это позволит вам реализовать повороты из узлов AA-дерева без передачи узла как параметра методу, делая вызов методов из самого узла.