View difference between Paste ID: <a href="/FWvTDESx">FWvTDESx</a> and <a href="/uf0f69aX">uf0f69aX</a>

View difference between Paste ID: FWvTDESx and uf0f69aX

SHOW: | | - or go back to the newest paste.

/*
/ Árvore AVL com Iteração e Comparação
/
/ Especialidades:
/ -Auto balanceamento;
/ -É tipável;
/ -Possui um Comparator como atributo, ou seja, você decide como os elementos serão ordenados;
/ -Caso haja uma mudança no tipo de comparação, a árvore se re-ordena pelo novo comparador;
/ -É possível fazer busca por índice de posição;
/ -É possível fazer remoção por índice de posição;
/ -Guarda o número de nós adicionados;
*/

public class Link<E> {
    private E content;
    private int balancing;
    private Link left;
    private Link right;
    private Link father;
    public Link(E content) {
        this.content = content;
        this.balancing = 0;
        this.left = null;
        this.right = null;
    }
    public E getContent() {
        return content;
    }
    public void setContent(E content) {
        this.content = content;
    }
    public int getBalancing() {
        return balancing;
    }
    public void setBalancing(int balancing) {
        this.balancing = balancing;
    }
    public Link getLeft() {
        return left;
    }
    public void setLeft(Link left) {
        this.left = left;
    }
    public Link getRight() {
        return right;
    }
    public void setRight(Link right) {
        this.right = right;
    }
    public Link getFather() {
        return father;
    }
    public void setFather(Link father) {
        this.father = father;
    }
}

public class TreeIterator implements Iterator{
    private Stack<Link> stack = new Stack<>();

    public TreeIterator(Link root) {
        push(root);
    }
    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    @Override
    public Link next() {
        Link node = stack.pop();
        push(node.getRight());
        return node;
    }
    private void push(Link node) {
        while (node != null) {
            stack.push(node);
            node = node.getLeft();
        }
    }
}

public class TreeLink<Generic> {
    private Link<Generic> root;
    private int size;
    private Comparator comparator;
    
    public TreeLink(Comparator comparator) {
        this.comparator = comparator;
    }
    public void addInTree(Generic content) {
		if(isEmpty()) addInRoot(content);
        else {
            Link<Generic> newLink = new Link<>(content);
            addInBranch(root, newLink);
        }
        size++;
    }
    public Generic removeByContent(Generic content) {
		Link<Generic> find = search(content);
        removeFoundLink(find);
        size--;
        return find.getContent();
    }
    public Generic removeByPosition(int index) {
        if(index > size || index < 0) return null;
        else {
            return removeByContent(getByPosition(index));
        }
    }
    public Link search(Generic content) {
        Link aux = root;
        if(aux != null) {
            while(aux != null) {
                if(comparator.compare(content, aux.getContent()) == 0) {
                    return aux;
                }
                else if(comparator.compare(content, aux.getContent()) > 0) aux = aux.getRight();
                else aux = aux.getLeft();
            }
        }
        return null;
    }
    public void removeAll() {
        for(int i = 0; i < size; i++) 
            removeByContent(getByPosition(i));
    }
    public Generic getByPosition(int index) {
        if(index > size || index < 0) return null;
        else {
            Iterator it = iterator();
            for(int i = 0; i < index; i++) 
                it.next();
            return (Generic) ((Link)it.next()).getContent();
        }
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public int size() {
        return size;
    }
    public Link getRoot() {
        return root;
    }
    public void display() {
        inOrder(root);
    }
    public void setComparator(Comparator comparator) {
        this.comparator = comparator;
        TreeLink newTree = new TreeLink(comparator);
        for(int i = 0; i < size; i++) 
            newTree.addInTree(removeByPosition(i));
        root = newTree.getRoot();
    }
    private void addInRoot(Generic content) {
        root = new Link<>(content);
    }
    private void addInBranch(Link current, Link newLink) {
        if(comparator.compare(newLink.getContent(), current.getContent()) < 0) {
            if(current.getLeft() == null) {
				current.setLeft(newLink);
				newLink.setFather(current);
				checkBalance(current);
            } 
            else {
                addInBranch(current.getLeft(), newLink);
            }
	} 
        else if(comparator.compare(newLink.getContent(), current.getContent()) > 0) {
            if(current.getRight() == null) {
                current.setRight(newLink);
				newLink.setFather(current);
				checkBalance(current);
            }
            else {
                addInBranch(current.getRight(), newLink);
            }
        }
    }
    private void checkBalance(Link anyLink) {
        setBalancing(anyLink);
        int balancing = anyLink.getBalancing();
        if(balancing == -2) {
            if(height(anyLink.getLeft().getLeft()) >= height(anyLink.getLeft().getRight())) {
                anyLink = singleRotationRight(anyLink);
            } 
            else {
                anyLink = doubleRotationRight(anyLink);
            }
        } 
        else if(balancing == 2) {
            if(height(anyLink.getRight().getRight()) >= height(anyLink.getRight().getLeft())) {
				anyLink = singleRotationLeft(anyLink);
            } 
            else {
                anyLink = doubleRotationLeft(anyLink);
            }
        }
        if(anyLink.getFather() != null) {
            checkBalance(anyLink.getFather());
        } 
        else {
            this.root = anyLink;
        }
    }
    private void removeFoundLink(Link find) {
        Link aux1;
        if(find.getLeft() == null || find.getRight() == null) {
            if(find.getFather() == null) {
                root = null;
                find = null;
                return;
            }
            aux1 = find;
        } 
        else {
            aux1 = nextLink(find);
            find.setContent(aux1.getContent());
		}
        Link aux2;
        if(aux1.getLeft() != null) {
            aux2 = aux1.getLeft();
		} 
        else {
            aux2 = aux1.getRight();
        }
        if(aux2 != null) {
            aux2.setFather(aux1.getFather());
		}
        if(aux1.getFather() == null) {
            root = aux2;
		} 
        else {
            if(aux1 == aux1.getFather().getLeft()) {
				aux1.getFather().setLeft(aux2);
            } 
            else {
                aux1.getFather().setRight(aux2);
            }
            checkBalance(aux1.getFather());
		}
		aux1 = null;
    }
    private Link singleRotationLeft(Link anyLink) {
        Link linkRight = anyLink.getRight();
		linkRight.setFather(anyLink.getFather());
        anyLink.setRight(linkRight.getLeft());
        if(anyLink.getRight() != null) {
            anyLink.getRight().setFather(anyLink);
		}
        linkRight.setLeft(anyLink);
        anyLink.setFather(linkRight);
        if(linkRight.getFather() != null) {
            if(linkRight.getFather().getRight() == anyLink) {
                linkRight.getFather().setRight(linkRight);
            } 
            else if(linkRight.getFather().getLeft() == anyLink) {
                linkRight.getFather().setLeft(linkRight);
            }
		}
        setBalancing(anyLink);
        setBalancing(linkRight);
        return linkRight;
    }
    private Link singleRotationRight(Link anyLink) {
        Link linkLeft = anyLink.getLeft();
        linkLeft.setFather(anyLink.getFather());
        anyLink.setLeft(linkLeft.getRight());
        if(anyLink.getLeft() != null) {
            anyLink.getLeft().setFather(anyLink);
        }
        linkLeft.setRight(anyLink);
        anyLink.setFather(linkLeft);
        if(linkLeft.getFather() != null) {
            if(linkLeft.getFather().getRight() == anyLink) {
                linkLeft.getFather().setRight(linkLeft);
            } 
            else if(linkLeft.getFather().getLeft() == anyLink) {
                linkLeft.getFather().setLeft(linkLeft);
            }
        }
        setBalancing(anyLink);
        setBalancing(linkLeft);
        return linkLeft;
    }
    private Link doubleRotationRight(Link anyLink) {
        anyLink.setLeft(singleRotationLeft(anyLink.getLeft()));
        return singleRotationRight(anyLink);
    }
    private Link doubleRotationLeft(Link anyLink) {
		anyLink.setRight(singleRotationRight(anyLink.getRight()));
		return singleRotationLeft(anyLink);
    }
    private Link nextLink(Link anyLink) {
		if (anyLink.getRight() != null) {
            Link aux = anyLink.getRight();
            while (aux.getLeft() != null) 
                aux = aux.getLeft();
            return aux;
		} 
        else {
            Link aux = anyLink.getFather();
            while (aux != null && anyLink == aux.getRight()) {
                anyLink = aux;
				aux = anyLink.getFather();
            }
            return aux;
		}
    }
    private int height(Link anyLink) {
		if (anyLink == null) {
            return -1;
		}
        if (anyLink.getLeft() == null && anyLink.getRight() == null) {
            return 0;	
		} 
        else if (anyLink.getLeft() == null) {
            return 1 + height(anyLink.getRight());
        } 
        else if (anyLink.getRight() == null) {
            return 1 + height(anyLink.getLeft());
		}
        else {
            return 1 + Math.max(height(anyLink.getLeft()), height(anyLink.getRight()));
		}
    }
    private void setBalancing(Link anyLink) {
        anyLink.setBalancing(height(anyLink.getRight()) - height(anyLink.getLeft()));
    }
    private void inOrder(Link anyLink) {
        if (anyLink == null) {
            return;
        }
        inOrder(anyLink.getLeft());
        System.out.println(anyLink.getContent());
        inOrder(anyLink.getRight());
    }
    private Iterator iterator() {
        return new TreeIterator(root);
    }
}

1		/*
2		/ Árvore AVL com Iteração e Comparação
3		/
4		/ Especialidades:
5		/ -Auto balanceamento;
6		/ -É tipável;
7		/ -Possui um Comparator como atributo, ou seja, você decide como os elementos serão ordenados;
8		/ -Caso haja uma mudança no tipo de comparação, a árvore se re-ordena pelo novo comparador;
9		/ -É possível fazer busca por índice de posição;
10		/ -É possível fazer remoção por índice de posição;
11		/ -Guarda o número de nós adicionados;
12		*/
13
14		public class Link<E> {
15		private E content;
16		private int balancing;
17		private Link left;
18		private Link right;
19		private Link father;
20		public Link(E content) {
21		this.content = content;
22		this.balancing = 0;
23		this.left = null;
24		this.right = null;
25		}
26		public E getContent() {
27		return content;
28		}
29		public void setContent(E content) {
30		this.content = content;
31		}
32		public int getBalancing() {
33		return balancing;
34		}
35		public void setBalancing(int balancing) {
36		this.balancing = balancing;
37		}
38		public Link getLeft() {
39		return left;
40		}
41		public void setLeft(Link left) {
42		this.left = left;
43		}
44		public Link getRight() {
45		return right;
46		}
47		public void setRight(Link right) {
48		this.right = right;
49		}
50		public Link getFather() {
51		return father;
52		}
53		public void setFather(Link father) {
54		this.father = father;
55		}
56		}
57
58		public class TreeIterator implements Iterator{
59		private Stack<Link> stack = new Stack<>();
60
61		public TreeIterator(Link root) {
62		push(root);
63		}
64		@Override
65		public boolean hasNext() {
66		return !stack.isEmpty();
67		}
68		@Override
69		public Link next() {
70		Link node = stack.pop();
71		push(node.getRight());
72		return node;
73		}
74		private void push(Link node) {
75		while (node != null) {
76		stack.push(node);
77		node = node.getLeft();
78		}
79		}
80		}
81
82		public class TreeLink<Generic> {
83		private Link<Generic> root;
84		private int size;
85		private Comparator comparator;
86
87		public TreeLink(Comparator comparator) {
88		this.comparator = comparator;
89		}
90		public void addInTree(Generic content) {
91		if(isEmpty()) addInRoot(content);
92		else {
93		Link<Generic> newLink = new Link<>(content);
94		addInBranch(root, newLink);
95		}
96		size++;
97		}
98		public Generic removeByContent(Generic content) {
99		Link<Generic> find = search(content);
100		removeFoundLink(find);
101		size--;
102		return find.getContent();
103		}
104		public Generic removeByPosition(int index) {
105		if(index > size \|\| index < 0) return null;
106		else {
107		return removeByContent(getByPosition(index));
108		}
109		}
110		public Link search(Generic content) {
111		Link aux = root;
112		if(aux != null) {
113		while(aux != null) {
114		if(comparator.compare(content, aux.getContent()) == 0) {
115		return aux;
116		}
117		else if(comparator.compare(content, aux.getContent()) > 0) aux = aux.getRight();
118		else aux = aux.getLeft();
119		}
120		}
121		return null;
122		}
123		public void removeAll() {
124		for(int i = 0; i < size; i++)
125		removeByContent(getByPosition(i));
126		}
127		public Generic getByPosition(int index) {
128		if(index > size \|\| index < 0) return null;
129		else {
130		Iterator it = iterator();
131		for(int i = 0; i < index; i++)
132		it.next();
133		return (Generic) ((Link)it.next()).getContent();
134		}
135		}
136		public boolean isEmpty() {
137		return size == 0;
138		}
139		public int size() {
140		return size;
141		}
142		public Link getRoot() {
143		return root;
144		}
145		public void display() {
146		inOrder(root);
147		}
148		public void setComparator(Comparator comparator) {
149		this.comparator = comparator;
150		TreeLink newTree = new TreeLink(comparator);
151		for(int i = 0; i < size; i++)
152		newTree.addInTree(removeByPosition(i));
153		root = newTree.getRoot();
154		}
155		private void addInRoot(Generic content) {
156		root = new Link<>(content);
157		}
158		private void addInBranch(Link current, Link newLink) {
159		if(comparator.compare(newLink.getContent(), current.getContent()) < 0) {
160		if(current.getLeft() == null) {
161		current.setLeft(newLink);
162		newLink.setFather(current);
163		checkBalance(current);
164		}
165		else {
166		addInBranch(current.getLeft(), newLink);
167		}
168		}
169		else if(comparator.compare(newLink.getContent(), current.getContent()) > 0) {
170		if(current.getRight() == null) {
171		current.setRight(newLink);
172		newLink.setFather(current);
173		checkBalance(current);
174		}
175		else {
176		addInBranch(current.getRight(), newLink);
177		}
178		}
179		}
180		private void checkBalance(Link anyLink) {
181		setBalancing(anyLink);
182		int balancing = anyLink.getBalancing();
183		if(balancing == -2) {
184		if(height(anyLink.getLeft().getLeft()) >= height(anyLink.getLeft().getRight())) {
185		anyLink = singleRotationRight(anyLink);
186		}
187		else {
188		anyLink = doubleRotationRight(anyLink);
189		}
190		}
191		else if(balancing == 2) {
192		if(height(anyLink.getRight().getRight()) >= height(anyLink.getRight().getLeft())) {
193		anyLink = singleRotationLeft(anyLink);
194		}
195		else {
196		anyLink = doubleRotationLeft(anyLink);
197		}
198		}
199		if(anyLink.getFather() != null) {
200		checkBalance(anyLink.getFather());
201		}
202		else {
203		this.root = anyLink;
204		}
205		}
206		private void removeFoundLink(Link find) {
207		Link aux1;
208		if(find.getLeft() == null \|\| find.getRight() == null) {
209		if(find.getFather() == null) {
210		root = null;
211		find = null;
212		return;
213		}
214		aux1 = find;
215		}
216		else {
217		aux1 = nextLink(find);
218		find.setContent(aux1.getContent());
219		}
220		Link aux2;
221		if(aux1.getLeft() != null) {
222		aux2 = aux1.getLeft();
223		}
224		else {
225		aux2 = aux1.getRight();
226		}
227		if(aux2 != null) {
228		aux2.setFather(aux1.getFather());
229		}
230		if(aux1.getFather() == null) {
231		root = aux2;
232		}
233		else {
234		if(aux1 == aux1.getFather().getLeft()) {
235		aux1.getFather().setLeft(aux2);
236		}
237		else {
238		aux1.getFather().setRight(aux2);
239		}
240		checkBalance(aux1.getFather());
241		}
242		aux1 = null;
243		}
244		private Link singleRotationLeft(Link anyLink) {
245		Link linkRight = anyLink.getRight();
246		linkRight.setFather(anyLink.getFather());
247		anyLink.setRight(linkRight.getLeft());
248		if(anyLink.getRight() != null) {
249		anyLink.getRight().setFather(anyLink);
250		}
251		linkRight.setLeft(anyLink);
252		anyLink.setFather(linkRight);
253		if(linkRight.getFather() != null) {
254		if(linkRight.getFather().getRight() == anyLink) {
255		linkRight.getFather().setRight(linkRight);
256		}
257		else if(linkRight.getFather().getLeft() == anyLink) {
258		linkRight.getFather().setLeft(linkRight);
259		}
260		}
261		setBalancing(anyLink);
262		setBalancing(linkRight);
263		return linkRight;
264		}
265		private Link singleRotationRight(Link anyLink) {
266		Link linkLeft = anyLink.getLeft();
267		linkLeft.setFather(anyLink.getFather());
268		anyLink.setLeft(linkLeft.getRight());
269		if(anyLink.getLeft() != null) {
270		anyLink.getLeft().setFather(anyLink);
271		}
272		linkLeft.setRight(anyLink);
273		anyLink.setFather(linkLeft);
274		if(linkLeft.getFather() != null) {
275		if(linkLeft.getFather().getRight() == anyLink) {
276		linkLeft.getFather().setRight(linkLeft);
277		}
278		else if(linkLeft.getFather().getLeft() == anyLink) {
279		linkLeft.getFather().setLeft(linkLeft);
280		}
281		}
282		setBalancing(anyLink);
283		setBalancing(linkLeft);
284		return linkLeft;
285		}
286		private Link doubleRotationRight(Link anyLink) {
287		anyLink.setLeft(singleRotationLeft(anyLink.getLeft()));
288		return singleRotationRight(anyLink);
289		}
290		private Link doubleRotationLeft(Link anyLink) {
291		anyLink.setRight(singleRotationRight(anyLink.getRight()));
292		return singleRotationLeft(anyLink);
293		}
294		private Link nextLink(Link anyLink) {
295		if (anyLink.getRight() != null) {
296		Link aux = anyLink.getRight();
297		while (aux.getLeft() != null)
298		aux = aux.getLeft();
299		return aux;
300		}
301		else {
302		Link aux = anyLink.getFather();
303		while (aux != null && anyLink == aux.getRight()) {
304		anyLink = aux;
305		aux = anyLink.getFather();
306		}
307		return aux;
308		}
309		}
310		private int height(Link anyLink) {
311		if (anyLink == null) {
312		return -1;
313		}
314		if (anyLink.getLeft() == null && anyLink.getRight() == null) {
315		return 0;
316		}
317		else if (anyLink.getLeft() == null) {
318		return 1 + height(anyLink.getRight());
319		}
320		else if (anyLink.getRight() == null) {
321		return 1 + height(anyLink.getLeft());
322		}
323		else {
324		return 1 + Math.max(height(anyLink.getLeft()), height(anyLink.getRight()));
325		}
326		}
327		private void setBalancing(Link anyLink) {
328		anyLink.setBalancing(height(anyLink.getRight()) - height(anyLink.getLeft()));
329		}
330		private void inOrder(Link anyLink) {
331		if (anyLink == null) {
332		return;
333		}
334		inOrder(anyLink.getLeft());
335		System.out.println(anyLink.getContent());
336		inOrder(anyLink.getRight());
337		}
338		private Iterator iterator() {
339		return new TreeIterator(root);
340		}
341		}