@egor_spk

Как реализовать поворот из нода AA дерева?

Попросили помочь с реализацией AA-Tree. Готовых алгоритмов в интернете куча, но есть условие, что сам нод не должен передаваться тот или иной метод, а метод должен вызываться из самого нода.
И вот что-то я сел... Как в таком стиле к примеру реализовать функции skew и split?

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; - тут бред
            }
        }
    }
}
  • Вопрос задан
  • 154 просмотра
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы