E
E
egor_spk2016-02-06 13:11:32
Java
egor_spk, 2016-02-06 13:11:32

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 question

Ask a Question

731 491 924 answers to any question