Implementacja drzewa BST w Javie

by Red 9 kwietnia 2020

Przykładowa implementacja drzewa poszukiwań binarnych (BST) w Javie

Nasza implementacja drzewa BST składa się z dwóch klas.

Wezel – jest klasą wewnętrzną. Reprezentuje pojedynczy węzeł w drzewie. Przechowywanym kluczem jest wartość int.
Drzewo – zawiera algorytmy dodawania, usuwania, wyświetlania elementów, odnajdywania poprzednika i następnika węzła oraz przechowuje korzeń. Jest klasą zewnętrzną.

Drzewa BST są ważną strukturą danych. Pozwalają o wiele skrócić czas wyszukiwania elementów, co jest szczególnie zauważalne przy dużych zbiorach. Oczywiście zakładając, że drzewo jest zrównoważone – w przeciwnym wypadku liczba operacji może wzrosnąć do poziomu zwykłej listy. Dużo lepszą wydajność zapewnią drzewa AVL lub drzewa czerwono-czarne. Te struktury poprzez rotacje potrafią zapewnić zrównoważenie poziomu obu poddrzew korzenia. Aby jednak je poznać warto najpierw poznać dokładnie drzewa BST, gdyż ta wiedza jest niezbędna, aby potem stosować dodatkowe zasady umieszczania węzłów.

Teoretyczna część znajduje się w naszym artykule odnośnie drzew BST. Tutaj skupimy się na praktycznej implementacji podanych tam algorytmów.

Klasa Drzewo

package pl.programistajava.Drzewo;
public class Drzewo {
private Wezel root;
class Wezel {
private Wezel left;
private Wezel right;
private Wezel parent;
private int key;
public Wezel(int key) {
this.key = key;
this.right = null;
this.left = null;
this.parent = null;
}
public Wezel getParent() {
return parent;
}
public void setParent(Wezel parent) {
this.parent = parent;
}
public Wezel getLeft() {
return left;
}
public void setLeft(Wezel left) {
this.left = left;
}
public Wezel getRight() {
return right;
}
public void setRight(Wezel right) {
this.right = right;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
}
public static void main(String[] args) {	
Drzewo tree = new Drzewo();
tree.addWezel(10);
tree.addWezel(5);	
tree.addWezel(20);
tree.addWezel(2);
tree.addWezel(8);
tree.addWezel(15);
System.out.println("Wezel o wartości 10: " + tree.getWezel(10).getKey());
System.out.println("Maksymalna wartość w drzewie: " + tree.getMax(tree.getRoot()).getKey());
System.out.println("Minimalna wartość w drzewie: " + tree.getMin(tree.getRoot()).getKey());
System.out.println("Następnik korzenia: " + tree.successor(tree.getRoot()).getKey());
System.out.println("Poprzednik korzenia: " + tree.predecessor(tree.getRoot()).getKey());
System.out.println("Wartość korzenia: " + tree.getRoot().getKey());
System.out.println("Usuwam aktualny korzeń - klucz " + tree.getRoot().getKey());
tree.removeWezel(10);
System.out.println("Wartość korzenia: " +tree.getRoot().getKey());
System.out.println("Rekurencyjne wyszukiwaie: " + tree.getWezel(tree.getRoot(), 5).getKey());
}
public Wezel getWezel(int key) {
Wezel current = getRoot();
while(current != null && current.getKey() != key) {
if(key > current.getKey()) {
current = current.getRight();
}else {
current = current.getLeft();
}
}
if(current == null) {
throw new NullPointerException("Nie znaleziono węzła z kluczem " + key);
}
return current;
}
public Wezel getWezel(Wezel node, int key) {
if (key > node.getKey()){
return getWezel(node.getRight(), key);
}else if(key < node.getKey()) {
return getWezel(node.getLeft(), key);
}else {
return node;
}
}
public boolean addWezel(int key){
Wezel parent = null;
Wezel current = getRoot();
while(current != null) {
parent = current;
if(current.getKey() == key) {
return false;
}
if(key > current.getKey()) {
current = current.getRight();
}else if(key < current.getKey()) {
current = current.getLeft();
}		
}
Wezel tmp = new Wezel(key);
if(parent == null) {
setRoot(tmp);
}else if(key > parent.getKey()) {
parent.setRight(tmp);
tmp.setParent(parent);
}else if(key < parent.getKey()) {
parent.setLeft(tmp);
tmp.setParent(parent);
}
return true;
}
public void removeWezel(int key) {
Wezel toDelete = getWezel(key);
Wezel tmp,pred = null;
if(toDelete.getLeft() == null || toDelete.getRight() == null) {
//usuwamy liść lub element z jednym poddrzewem
tmp = toDelete;
}else {
//usuwamy węzeł, z dwoma potomkami - szukamy następnika
//można też znalezc poprzednik
tmp = successor(toDelete);
}
if(tmp.getLeft() != null) {
pred = tmp.getLeft();
}else {
pred = tmp.getRight();
}
if(pred != null) {
pred.setParent(tmp.getParent());
}
if(tmp.getParent() == null) {
setRoot(pred);
}else {
if(tmp == tmp.getParent().getLeft()) {
tmp.getParent().setLeft(pred);
}else {
tmp.getParent().setRight(pred);
}
}
if(tmp.getKey() != toDelete.getKey()) {
toDelete.setKey(tmp.getKey());
}
}
public Wezel predecessor(Wezel w) {
if(w.getLeft() != null) {
return getMax(w.getLeft());
}
Wezel tmp = w.getParent();
while(w != null && w.getRight().getKey() != tmp.getKey()) {
tmp = w;
w = w.getRight();
}
return w;
}
public Wezel successor(Wezel w) {
if(w.getRight() != null) {
return getMin(w.getRight());
}
Wezel tmp = w.getParent();
while(w != null && w.getLeft().getKey() != tmp.getKey()) {
tmp = w;
w = w.getLeft();
}
return w;
}
public Wezel getMin(Wezel w) {
Wezel current = w;
while(current.getLeft() != null) {
current = current.getLeft();
}
return current;
}
public Wezel getMax(Wezel w) {
Wezel current = w;
while(current.getRight() != null) {
current = current.getRight();
}
return current;
}
public Wezel getRoot() {
return root;
}
public void setRoot(Wezel root) {
this.root = root;
}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

package pl.programistajava.Drzewo;

public class Drzewo {

private Wezel root;

class Wezel {

private Wezel left;

private Wezel right;

private Wezel parent;

private int key;

public Wezel(int key) {

this.key = key;

this.right = null;

this.left = null;

this.parent = null;

}

public Wezel getParent() {

return parent;

}

public void setParent(Wezel parent) {

this.parent = parent;

}

public Wezel getLeft() {

return left;

}

public void setLeft(Wezel left) {

this.left = left;

}

public Wezel getRight() {

return right;

}

public void setRight(Wezel right) {

this.right = right;

}

public int getKey() {

return key;

}

public void setKey(int key) {

this.key = key;

}

public static void main(String[] args) {

Drzewo tree = new Drzewo();

tree.addWezel(10);

tree.addWezel(5);

tree.addWezel(20);

tree.addWezel(2);

tree.addWezel(8);

tree.addWezel(15);

System.out.println("Wezel o wartości 10: " + tree.getWezel(10).getKey());

System.out.println("Maksymalna wartość w drzewie: " + tree.getMax(tree.getRoot()).getKey());

System.out.println("Minimalna wartość w drzewie: " + tree.getMin(tree.getRoot()).getKey());

System.out.println("Następnik korzenia: " + tree.successor(tree.getRoot()).getKey());

System.out.println("Poprzednik korzenia: " + tree.predecessor(tree.getRoot()).getKey());

System.out.println("Wartość korzenia: " + tree.getRoot().getKey());

System.out.println("Usuwam aktualny korzeń - klucz " + tree.getRoot().getKey());

tree.removeWezel(10);

System.out.println("Wartość korzenia: " +tree.getRoot().getKey());

System.out.println("Rekurencyjne wyszukiwaie: " + tree.getWezel(tree.getRoot(), 5).getKey());

}

public Wezel getWezel(int key) {

Wezel current = getRoot();

while(current != null && current.getKey() != key) {

if(key > current.getKey()) {

current = current.getRight();

}else {

current = current.getLeft();

}

if(current == null) {

throw new NullPointerException("Nie znaleziono węzła z kluczem " + key);

}

return current;

}

public Wezel getWezel(Wezel node, int key) {

if (key > node.getKey()){

return getWezel(node.getRight(), key);

}else if(key < node.getKey()) {

return getWezel(node.getLeft(), key);

}else {

return node;

}

public boolean addWezel(int key){

Wezel parent = null;

Wezel current = getRoot();

while(current != null) {

parent = current;

if(current.getKey() == key) {

return false;

}

if(key > current.getKey()) {

current = current.getRight();

}else if(key < current.getKey()) {

current = current.getLeft();

}

Wezel tmp = new Wezel(key);

if(parent == null) {

setRoot(tmp);

}else if(key > parent.getKey()) {

parent.setRight(tmp);

tmp.setParent(parent);

}else if(key < parent.getKey()) {

parent.setLeft(tmp);

tmp.setParent(parent);

}

return true;

}

public void removeWezel(int key) {

Wezel toDelete = getWezel(key);

Wezel tmp,pred = null;

if(toDelete.getLeft() == null || toDelete.getRight() == null) {

//usuwamy liść lub element z jednym poddrzewem

tmp = toDelete;

}else {

//usuwamy węzeł, z dwoma potomkami - szukamy następnika

//można też znalezc poprzednik

tmp = successor(toDelete);

}

if(tmp.getLeft() != null) {

pred = tmp.getLeft();

}else {

pred = tmp.getRight();

}

if(pred != null) {

pred.setParent(tmp.getParent());

}

if(tmp.getParent() == null) {

setRoot(pred);

}else {

if(tmp == tmp.getParent().getLeft()) {

tmp.getParent().setLeft(pred);

}else {

tmp.getParent().setRight(pred);

}

if(tmp.getKey() != toDelete.getKey()) {

toDelete.setKey(tmp.getKey());

}

public Wezel predecessor(Wezel w) {

if(w.getLeft() != null) {

return getMax(w.getLeft());

}

Wezel tmp = w.getParent();

while(w != null && w.getRight().getKey() != tmp.getKey()) {

tmp = w;

w = w.getRight();

}

return w;

}

public Wezel successor(Wezel w) {

if(w.getRight() != null) {

return getMin(w.getRight());

}

Wezel tmp = w.getParent();

while(w != null && w.getLeft().getKey() != tmp.getKey()) {

tmp = w;

w = w.getLeft();

}

return w;

}

public Wezel getMin(Wezel w) {

Wezel current = w;

while(current.getLeft() != null) {

current = current.getLeft();

}

return current;

}

public Wezel getMax(Wezel w) {

Wezel current = w;

while(current.getRight() != null) {

current = current.getRight();

}

return current;

}

public Wezel getRoot() {

return root;

}

public void setRoot(Wezel root) {

this.root = root;

}

Wewnętrzna klasa Wezel

Klasa Wezel przechowuje informację o dwóch potomkach, o rodzicu oraz klucz. Ze względu na to, że ta struktura danych jest mało elastyczna umieściliśmy ją wewnątrz klasy Drzewo, gdyż i tak nie wykorzystamy jej nigdzie indziej.

Pola

Obiekt klasy Wezel zawiera trzy referencje:

do lewego potomka,
do prawego potomka,
oraz do rodzica.

Dodatkowym polem jest przechowywana wartość czyli zmienna key.

Konstruktor

Inicjuje dane – referencje do innych węzłów na null, a pole z danymi uzupełnia wartością przekazaną w argumencie.

Zewnętrzna klasa Drzewo

Obiekt klasy Drzewo przechowuje referencję do korzenia (ang. root). Zawiera również niezbędne algorytmy, takie jak:

dodawanie elementów do drzewa,
usuwanie elementów z drzewa,
szukanie elementu o konkretnej wartości,
znalezienie największej wartości w drzewie,
znalezienie najmniejszej wartości w drzewie,
wskazanie następnika węzła,
wskazanie poprzednika węzła.

Wykonanie metody main() spowoduje wyświetlenie następujących komunikatów w konsoli.

Wezel o wartości 10: 10
Maksymalna wartość w drzewie: 20
Minimalna wartość w drzewie: 2
Następnik korzenia: 15
Poprzednik korzenia: 8
Wartość korzenia: 10
Usuwam aktualny korzeń - klucz 10
Wartość korzenia: 15

Wezel o wartości 10: 10

Maksymalna wartość w drzewie: 20

Minimalna wartość w drzewie: 2

Następnik korzenia: 15

Poprzednik korzenia: 8

Wartość korzenia: 10

Usuwam aktualny korzeń - klucz 10

Wartość korzenia: 15

System zbierania nieużytków (ang. Garbage collector)

W Javie nie ma potrzeby ręcznego czyszczenia pamięci. Wystarczy odłączyć usuwany obiekt od struktury drzewa.

Implementacje, Java, Kolekcje, Lista

Implementacja listy wiązanej dwukierunkowej

by Red 25 marca 2020

Struktura listy dwukierunkowej

Nasza lista jest zbudowana z dwóch klas.

Wezel – klasa wewnętrzna – reprezentuje pojedynczy węzeł na liście.
Lista – klasa zewnętrzna – zawiera algorytmy dodawania, usuwania oraz wyświetlania elementów oraz przechowuje pierwszy element listy.

Lista ta powstała w celu dydaktycznym, aby pokazać jak wygląda własne opracowanie algorytmu. W związku z tym nie implementujemy żadnych interfejsów, takich jak Comparable, który mógłby posłużyć do sortowania elementów. Z tego samego powodu nie jest to również klasa generyczna, dlatego nie można w tej kolekcji przechowywać żadnych typów własnych, ani innych typów prostych niż int.

Naszym celem było napisanie jak najprostszego algorytmu, aby skupić się na działaniu tej konkretnej struktury danych. Tak, aby w praktyczny sposób przekazać wiedzę z naszego teoretycznego wstępu odnośnie list dwukierunkowych.

Typem danych do przechowywania jest int. Aby uruchomić poniższy kod należy skopiować kod, a następnie skompilować.

package pl.programistajava.lista;
public class Lista {
private Wezel head;
class Wezel {
private Wezel next;
private Wezel prev;
private int data;
public Wezel(int d){
next = null;
prev = null;
data = d;
}
}
public Lista() {
this.head = null;
}
public static void main(String[] args){
Lista list = new Lista();
list.addWezel(1);
list.addWezel(2);
list.addWezel(3);
list.wypiszListe();
System.out.println();
list.removeWezel(1);
list.wypiszListe();
}
public void wypiszListe() {
Wezel w = this.head;
System.out.print("[ ");
while(w != null) {
System.out.print(w.data + " ");
w = w.next;
}
System.out.print("]");
}
public Wezel getWezel(int n) throws IndexOutOfBoundsException{
if(n < 0) {
throw new IndexOutOfBoundsException("Nie można podać ujemnego argumentu");
}
int i = 0;
Wezel w = this.head;
while(w != null && i++ < n) {
w = w.next;
}
if (w == null) {
throw new IndexOutOfBoundsException("Nie istnieje obiekt o podanym argumencie.");
}
return w;
}
public void addWezel(int s) {
Wezel w = head;
Wezel last = null;
Wezel tmp = new Wezel(s);
while(w != null) {
last = w;
w = w.next;
}
if(last == null) {
this.head = tmp;
}else {
last.next = tmp;
tmp.prev = last;
}			
}
public void removeWezel(int n) {
Wezel w = getWezel(n);
if(w.prev == null) {
//gdy usuwamy głowę
this.head = w.next;
this.head.prev = null;
}	
else if(w.next == null) {
//gdy usuwamy ogon
w = w.prev;
w.next = null;
}	
else {
//gdy usuwamy środek
w.prev.next = w.next;
w.next.prev = w.prev;
}			
}
}

package pl.programistajava.lista;

public class Lista {

private Wezel head;

class Wezel {

private Wezel next;

private Wezel prev;

private int data;

public Wezel(int d){

next = null;

prev = null;

data = d;

}

public Lista() {

this.head = null;

}

public static void main(String[] args){

Lista list = new Lista();

list.addWezel(1);

list.addWezel(2);

list.addWezel(3);

list.wypiszListe();

System.out.println();

list.removeWezel(1);

list.wypiszListe();

}

public void wypiszListe() {

Wezel w = this.head;

System.out.print("[ ");

while(w != null) {

System.out.print(w.data + " ");

w = w.next;

}

System.out.print("]");

}

public Wezel getWezel(int n) throws IndexOutOfBoundsException{

if(n < 0) {

throw new IndexOutOfBoundsException("Nie można podać ujemnego argumentu");

}

int i = 0;

Wezel w = this.head;

while(w != null && i++ < n) {

w = w.next;

}

if (w == null) {

throw new IndexOutOfBoundsException("Nie istnieje obiekt o podanym argumencie.");

}

return w;

}

public void addWezel(int s) {

Wezel w = head;

Wezel last = null;

Wezel tmp = new Wezel(s);

while(w != null) {

last = w;

w = w.next;

}

if(last == null) {

this.head = tmp;

}else {

last.next = tmp;

tmp.prev = last;

}

public void removeWezel(int n) {

Wezel w = getWezel(n);

if(w.prev == null) {

//gdy usuwamy głowę

this.head = w.next;

this.head.prev = null;

}

else if(w.next == null) {

//gdy usuwamy ogon

w = w.prev;

w.next = null;

}

else {

//gdy usuwamy środek

w.prev.next = w.next;

w.next.prev = w.prev;

}

Wewnętrzna klasa Wezel

Powyższy program można podzielić na dwie części. Pierwszą jest obiekt, który przechowuje dane i jest nią klasa Wezel. Ze względu na to, że ta struktura danych jest mało elastyczna umieściliśmy ją wewnątrz klasy Lista, gdyż i tak nie wykorzystamy jej nigdzie indziej. Takie podejście jest wygodnie, ponieważ mamy ułatwiony dostęp do pól obu klas.

Pola

Obiekt klasy Wezel zawiera dwie referencje do innych obiektów oraz zmienną przechowującą dane.

Konstruktor

Inicjuje dane – pola obiektowe czyli referencje do poprzednie i następnego obiektu ustawia na null, a pole z danymi uzupełnia wartością przekazaną w argumencie.

Zewnętrzna klasa Lista

Obiekt klasy Lista przechowuje referencję do pierwszego elementu listy, czyli głowę (ang. head). Zawiera również niezbędne algorytmy, takie jak:

dodawanie elementów do listy,
usuwanie elementów z listy,
szukanie elementu o konkretnym indeksie,
wypisanie wszystkich elementów listy.

W metodzie main() znajduje się przykładowy przebieg programu. Dane zostały dobrane w taki sposób, aby nie spowodować wyjątku. Wykonanie metody main() spowoduje wyświetlenie następujących komunikatów w konsoli.

[ 1 2 3 ]
[ 1 3 ]

1 2	[ 1 2 3 ] [ 1 3 ]

Zachęcamy do eksperymentów z kodem.

Metody

Wielokrotne wykorzystanie kodu pozytywnie wpływa na jego objętość. Lista dwukierunkowa pozwala na ponowne wykorzystanie metody getWezel() w celu znalezienia usuwanego węzła zamiast pisać ponownie kod, który robi tę samą czynność.

Wyjątek IndexOutOfBoundException

Jeżeli spróbujemy wpisać do metody szukającej indeks ujemny lub spoza naszej listy zostanie wyrzucony wyjątek.

System zbierania nieużytków (ang. Garbage collector)

Być może programiści innych języków zwrócili uwagę na to, że po usunięciu elementów nie czyścimy ręcznie pamięci. W językach z rodziny C oprócz zmiany wskaźników na odpowiednie elementy należy użyć funkcji free(), która czyści pamięć – w przeciwnym wypadku po wyjściu z funkcji usuwania elementu stracimy wskaźnik na usuwany element i nigdy już go nie będziemy w stanie usunąć – do restartu maszyny.

W Javie jeśli nie mamy dostępu do obiektu, to nie musimy z tym nic robić. System zbierania nieużytków zrobi wszystko za nas i oczyści pamięć ze zbędnych obiektów.

Polecamy również zapoznać się z implementacją listy jednokierunkowej. Pozornie obie wydają się podobne, jednakże różnią się znacznie przy samej budowie.

Kategoria Implementacje

Przykładowa implementacja drzewa poszukiwań binarnych (BST) w Javie

Klasa Drzewo

Wewnętrzna klasa Wezel

Pola

Konstruktor

Zewnętrzna klasa Drzewo

System zbierania nieużytków (ang. Garbage collector)

Struktura listy dwukierunkowej

Wewnętrzna klasa Wezel

Pola

Konstruktor

Zewnętrzna klasa Lista

Metody

Wyjątek IndexOutOfBoundException

System zbierania nieużytków (ang. Garbage collector)