View difference between Paste ID: <a href="/FXFWjLie">FXFWjLie</a> and <a href="/BT2Vm0b7">BT2Vm0b7</a>

//
1		//
2		// Created by Julio Tentor <jtentor@fi.unju.edu.ar>
3		//
4
5		public class BinarySearchTree<ELEMENT extends Comparable<ELEMENT>> extends BinaryTree<ELEMENT> {
6
7
8		public BinarySearchTree() {
9		super();
10		}
11
12
13		public void add(ELEMENT item) {
14		if (this.root == null) {
15		this.root = new BTNode<ELEMENT>(item, null, null);
16		} else {
17		BTNode<ELEMENT> temp = this.root;
18		BTNode<ELEMENT> prev = null;
19		while (temp != null ) {
20		prev = temp;
21		if (item.compareTo(temp.item) < 0) {
22		temp = temp.left;
23		} else {
24		temp = temp.right;
25		}
26		}
27		temp = new BTNode<ELEMENT>(item, null, null);
28		if (item.compareTo(prev.item) < 0) {
29		prev.left = temp;
30		} else {
31		prev.right = temp;
32		}
33		}
34		}
35
36
37		public ELEMENT remove(ELEMENT item) {
38		return removeByCopy(item);
39		//return removeByFusion(item);
40		}
41
42
43		private ELEMENT removeByCopy(ELEMENT item) {
44		BTNode<ELEMENT> find = this.root;
45		BTNode<ELEMENT> prev = null;
46		while ((find != null) && (find.item.compareTo(item) != 0)) {
47		prev = find;
48		if (item.compareTo(find.item) < 0) {
49		find = find.left;
50		} else {
51		find = find.right;
52		}
53		}
54		if (find == null) {
55		throw new RuntimeException("No existe el elemento o el árbol está vacío");
56		} // find es el nodo con el valor a extraer y prev el padre de ese nodo
57		ELEMENT save = find.item;
58		BTNode<ELEMENT> node = find;
59		if (node.right == null) { // no hay subarbol derecho
60		node = node.left; // nodo con un descendiente u hoja
61		} else {
62		if (node.left == null) { // no hay subarbol izquierdo
63		node = node.right; // nodo con un descendiente u hoja
64		} else { // dos descendientes
65		BTNode<ELEMENT> last = node;
66		BTNode<ELEMENT> temp = node.right; // a la derecha (mayores)
67		while (temp.left != null) { // busca a la izquierda el menor
68		last = temp;
69		temp = temp.left;
70		}
71		// temp es el menor de los mayores
72		node.item = temp.item; // hace la copia
73		if (last == node) {
74		last.right = temp.right;
75		} else {
76		last.left = temp.right;
77		}
78		temp.right = null;
79		}
80		}
81		// reajustar el arbol
82		if (find == this.root) {
83		this.root = node;
84		} else {
85		if (prev.left == find) {
86		prev.left = node;
87		} else {
88		prev.right = node;
89		}
90		}
91		return save;
92		}
93
94
95		private ELEMENT removeByFusion(ELEMENT item) {
96		BTNode<ELEMENT> find = this.root;
97		BTNode<ELEMENT> prev = null;
98		while ((find != null) && (find.item.compareTo(item) != 0)) {
99		prev = find;
100		if (item.compareTo(find.item) < 0) {
101		find = find.left;
102		} else {
103		find = find.right;
104		}
105		}
106		if (find == null) {
107		throw new RuntimeException("No existe el elemento o el árbol está vacío");
108		}
109		ELEMENT save = find.item;
110		BTNode<ELEMENT> node = find;
111		if (node.right == null) {
112		node = node.left;
113		} else {
114		if (node.left == null) {
115		node = node.right;
116		} else {
117		BTNode<ELEMENT> temp = node.right;
118		while (temp.left != null) {
119		temp = temp.left;
120		}
121		temp.left = node.left;
122		node = node.right;
123		}
124		}
125		if (find == this.root) {
126		this.root = node;
127		} else {
128		if (prev.left == find) {
129		prev.left = node;
130		} else {
131		prev.right = node;
132		}
133		}
134		find.left = find.right = null;
135		return save;
136		}
137
138		}
139