Korzyści z drzewa binarnego
Jaka jest zaleta przechowywania danych w postaci drzewa wyszukiwania binarnego? Wyobraź sobie, że mamy 100-stronicowy podręcznik i musimy znaleźć konkretną stronę, która będzie zawierać potrzebne nam dane. Z treści wiemy też, jakiej konkretnej strony potrzebujemy. Jeśli pójdziemy zwykłą ścieżką, będziemy musieli przewracać jedną stronę na raz, aż dotrzemy do tej, której potrzebujemy. Oznacza to, że przejdziemy od 1 do 100 stron, aż znajdziemy się we właściwym miejscu. Na przykład, jeśli potrzebujemy strony 77, będziemy mieli 77 wyszukiwań. Jeśli mówimy o złożoności czasowej, to będzie to O(N) . Ale można to zrobić skuteczniej, prawda? Spróbujmy zrobić to samo, ale używając wyszukiwania binarnego :- Katalog dzielimy na dwie części, pierwsza - od 1 do 50, druga - 51-100. Wiemy dokładnie, w której z tych części znajduje się nasza strona: jeśli ponownie weźmiemy stronę 77, będzie to druga część książki.
- Następnie rozważamy drugą część i dzielimy ją na dwie - od 51 do 75, od 76 do 100. W tym przypadku nasza strona ponownie znajdzie się w drugiej połowie, w przedziale 76-100.
- Następnie dzielimy ten przedział przez 2 i otrzymujemy 76-88 i 89-100. Strona mieści się w pierwszą lukę, więc drugą odrzucamy.
- Następne są przedziały: 76-81 i 82-88, weź pierwszy.
- 76-78 i 79-81, weź pierwszy.
- 76 i 77-78, weź drugi.
- 77 i 78, weź pierwszy i zdobądź naszą stronę - 77.
Zasady konstruowania drzewa poszukiwań binarnych
Drzewo wyszukiwania binarnego budowane jest według pewnych zasad:- każdy węzeł ma co najwyżej dwoje dzieci;
- każda wartość mniejsza niż wartość węzła staje się lewym dzieckiem lub dzieckiem lewego dziecka;
- każda wartość większa lub równa wartości węzła staje się właściwym dzieckiem lub dzieckiem odpowiedniego dziecka.
- wszystkie węzły mają nie więcej niż dwóch spadkobierców, pierwszy warunek jest spełniony;
- jeśli weźmiemy pod uwagę na przykład węzeł o wartości 7 (lub jakikolwiek inny), zobaczymy, że wszystkie wartości elementów w lewym poddrzewie będą mniejsze, a w prawym - większe. Oznacza to, że spełnione są warunki 2 i 3.
Wyszukaj element
Szukając elementu o podanej wartości zaczynamy od elementu głównego:- Jeśli jest równy żądanej wartości, element główny jest pożądany, jeśli nie, porównujemy wartości pierwiastka i pożądanego.
- Jeśli szukany element jest większy, przechodzimy do prawego dziecka, jeśli nie, przechodzimy do lewego dziecka.
- Jeśli element nie zostanie znaleziony, wykonaj kroki 1 i 2, ale do dziecka (prawego lub lewego), aż element zostanie znaleziony.
- porównujemy go z elementem głównym, widzimy, że element główny jest większy, więc przechodzimy do lewego dziecka, które ma wartość 3;
- porównujemy ten, którego szukamy, z elementem o wartości 3, widzimy, że ten, którego szukamy, jest większy, więc potrzebny jest prawy potomek danego elementu, czyli elementu o wartości 5;
- Porównujemy tego potomka z tym, którego szukamy i widzimy, że wartości są równe – element zostaje znaleziony.
Wstawianie elementu
Algorytm wstawiania jest również bardzo, bardzo prosty:-
Porównujemy nowy element z pierwotnym (jeśli nie istnieje, nowym elementem jest element główny).
-
Jeżeli nowy element:
- jest mniejsza, to przechodzimy do lewego spadkobiercy, jeśli go nie ma, nowy element zajmuje miejsce lewego spadkobiercy i algorytm jest zakończony;
- jest większa lub równa pierwiastkowi, wówczas przechodzimy do prawego spadkobiercy. I podobnie, jeśli tego elementu nie ma, to nowy element zajmie miejsce prawidłowego elementu i algorytm zostanie zakończony.
-
W przypadku nowego elementu, który w poprzednim kroku był prawy lub lewy, powtarzaj kroki 1 i 2, aż wstawiony element znajdzie się na swoim miejscu.
Jako przykład będziemy chcieli wstawić do rozważanego powyżej drzewa element o wartości 11:
- porównujemy z elementem głównym 7 i widzimy, że element główny jest mniejszy, więc przechodzimy do prawego spadkobiercy;
- następny rozważany element ma wartość 9, czyli mniej niż nowe 11, więc przechodzimy do prawego spadkobiercy;
- prawy spadkobierca ma wartość 10, czyli znowu mniej, więc przechodzimy do pierwszego elementu, a ponieważ go nie ma, w tym miejscu umieszczany jest nowy element o wartości 11.
↓
Usuwanie elementu
Być może ze wszystkich operacji na drzewach wyszukiwania binarnego usuwanie jest najtrudniejsze. W pierwszej kolejności następuje wyszukiwanie elementu do usunięcia, po czym następuje etap, który może mieć trzy warianty:-
Węzeł do usunięcia jest węzłem liścia (nie ma dzieci).
Być może najprostszy. Wszystko sprowadza się do tego, że po prostu odcinamy go od drzewa, bez zbędnych manipulacji. Przykładowo z naszego drzewa usuwamy węzeł o wartości 8:
↓ -
Usuwany węzeł ma jedno dziecko.
W tym przypadku usuwamy wybrany węzeł i umieszczamy na jego miejscu jego potomka (w zasadzie po prostu wycinamy wybrany węzeł z łańcucha). Przykładowo usuńmy z drzewa węzeł o wartości 9:
↓ -
Usuwany węzeł ma dwoje dzieci.
Najciekawsza część. W końcu, jeśli usuwany węzeł ma dwoje dzieci na raz, nie można go po prostu zastąpić jednym z tych dzieci (zwłaszcza jeśli dziecko ma własne dzieci).
Przykład: który węzeł w powyższym drzewie powinien być lewym dzieckiem węzła 3?
Jeśli się nad tym trochę zastanowić, staje się oczywiste, że powinien to być węzeł o wartości 4. Ale co, jeśli drzewo nie jest takie proste? Jeśli zawiera setki wartości, czy łatwo będzie ustalić, kto będzie następcą?
To jasne, że nie. Dlatego potrzebujemy własnego algorytmu wyszukiwania małego odbiornika:
- Najpierw musimy udać się do prawego dziecka wybranego węzła, którego wartość musi być większa od wartości węzła.
- Następnie przechodzimy do lewego dziecka prawego dziecka (jeśli takie istnieje), następnie do lewego dziecka lewego dziecka itd., podążając w dół łańcucha lewych dzieci.
- W związku z tym ostatnie lewe dziecko na tej ścieżce będzie następcą pierwotnego węzła.
Uogólnijmy trochę ten mały algorytm: w poddrzewie prawego dziecka węzła źródłowego wszystkie węzły są większe niż ten, który jest usuwany, co można zrozumieć z podstawowych zasad drzewa wyszukiwania binarnego. W tym poddrzewie szukamy najmniejszej wartości.
Innymi słowy, szukamy najmniejszego węzła w zbiorze węzłów większym niż węzeł pierwotny. Ten najmniejszy węzeł spośród większych będzie najodpowiedniejszym następcą.
Jak będzie wyglądać drzewo po usunięciu węzła o wartości 3:
↓
class Node {
private int value; // ключ узла
private Node leftChild; // Левый узел потомок
private Node rightChild; // Правый узел потомок
public void printNode() { // Вывод значения узла в консоль
System.out.println(" Выбранный узел имеет oznaczający :" + value);
}
public int getValue() {
return this.value;
}
public void setValue(final int value) {
this.value = value;
}
public Node getLeftChild() {
return this.leftChild;
}
public void setLeftChild(final Node leftChild) {
this.leftChild = leftChild;
}
public Node getRightChild() {
return this.rightChild;
}
public void setRightChild(final Node rightChild) {
this.rightChild = rightChild;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
", leftChild=" + leftChild +
", rightChild=" + rightChild +
'}';
}
}
Nic zbyt skomplikowanego: każdy element ma link do swojego lewego i prawego dziecka. A teraz być może najważniejszą klasą jest klasa drzewa:
class Tree {
private Node rootNode; // корневой узел
public Tree() { // Пустое дерево
rootNode = null;
}
public Node findNodeByValue(int value) { // поиск узла по значению
Node currentNode = rootNode; // начинаем поиск с корневого узла
while (currentNode.getValue() != value) { // поиск покуда не будет найден элемент Lub не будут перебраны все
if (value < currentNode.getValue()) { // движение влево?
currentNode = currentNode.getLeftChild();
} else { //движение вправо
currentNode = currentNode.getRightChild();
}
if (currentNode == null) { // если потомка нет,
return null; // возвращаем null
}
}
return currentNode; // возвращаем найденный элемент
}
public void insertNode(int value) { // метод вставки нового element
Node newNode = new Node(); // создание нового узла
newNode.setValue(value); // вставка данных
if (rootNode == null) { // если корневой узел не существует
rootNode = newNode;// то новый элемент и есть корневой узел
}
else { // корневой узел занят
Node currentNode = rootNode; // начинаем с корневого узла
Node parentNode;
while (true) // мы имеем внутренний выход из цикла
{
parentNode = currentNode;
if(value == currentNode.getValue()) { // если такой элемент в дереве уже есть, не сохраняем его
return; // просто выходим из метода
}
else if (value < currentNode.getValue()) { // движение влево?
currentNode = currentNode.getLeftChild();
if (currentNode == null){ // если был достигнут конец цепочки,
parentNode.setLeftChild(newNode); // то вставить слева и выйти из методы
return;
}
}
else { // Или направо?
currentNode = currentNode.getRightChild();
if (currentNode == null) { // если был достигнут конец цепочки,
parentNode.setRightChild(newNode); //то вставить справа
return; // и выйти
}
}
}
}
}
public boolean deleteNode(int value) // Удаление узла с заданным ключом
{
Node currentNode = rootNode;
Node parentNode = rootNode;
boolean isLeftChild = true;
while (currentNode.getValue() != value) { // начинаем поиск узла
parentNode = currentNode;
if (value < currentNode.getValue()) { // Определяем, нужно ли движение влево?
isLeftChild = true;
currentNode = currentNode.getLeftChild();
}
else { // Lub движение вправо?
isLeftChild = false;
currentNode = currentNode.getRightChild();
}
if (currentNode == null)
return false; // yзел не найден
}
if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { // узел просто удаляется, если не имеет потомков
if (currentNode == rootNode) // если узел - корень, то дерево очищается
rootNode = null;
else if (isLeftChild)
parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя
else
parentNode.setRightChild(null);
}
else if (currentNode.getRightChild() == null) { // узел заменяется левым поддеревом, если правого потомка нет
if (currentNode == rootNode)
rootNode = currentNode.getLeftChild();
else if (isLeftChild)
parentNode.setLeftChild(currentNode.getLeftChild());
else
parentNode.setRightChild(currentNode.getLeftChild());
}
else if (currentNode.getLeftChild() == null) { // узел заменяется правым поддеревом, если левого потомка нет
if (currentNode == rootNode)
rootNode = currentNode.getRightChild();
else if (isLeftChild)
parentNode.setLeftChild(currentNode.getRightChild());
else
parentNode.setRightChild(currentNode.getRightChild());
}
else { // если есть два потомка, узел заменяется преемником
Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла
if (currentNode == rootNode)
rootNode = heir;
else if (isLeftChild)
parentNode.setLeftChild(heir);
else
parentNode.setRightChild(heir);
}
return true; // элемент успешно удалён
}
// метод возвращает узел со следующим oznaczającyм после передаваемого аргументом.
// для этого он сначала переходим к правому потомку, а затем
// отслеживаем цепочку левых потомков этого узла.
private Node receiveHeir(Node node) {
Node parentNode = node;
Node heirNode = node;
Node currentNode = node.getRightChild(); // Переход к правому потомку
while (currentNode != null) // Пока остаются левые потомки
{
parentNode = heirNode;// потомка задаём Jak текущий узел
heirNode = currentNode;
currentNode = currentNode.getLeftChild(); // переход к левому потомку
}
// Если преемник не является
if (heirNode != node.getRightChild()) // правым потомком,
{ // создать связи между узлами
parentNode.setLeftChild(heirNode.getRightChild());
heirNode.setRightChild(node.getRightChild());
}
return heirNode;// возвращаем приемника
}
public void printTree() { // метод для вывода дерева в консоль
Stack globalStack = new Stack(); // общий стек для значений дерева
globalStack.push(rootNode);
int gaps = 32; // начальное oznaczający расстояния между elementми
boolean isRowEmpty = false;
String separator = "-----------------------------------------------------------------";
System.out.println(separator);// черта для указания начала нового дерева
while (isRowEmpty == false) {
Stack localStack = new Stack(); // локальный стек для задания потомков element
isRowEmpty = true;
for (int j = 0; j < gaps; j++)
System.out.print(' ');
while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека
if (temp != null) {
System.out.print(temp.getValue()); // выводим его oznaczający в консоли
localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего element
localStack.push(temp.getRightChild());
if (temp.getLeftChild() != null ||
temp.getRightChild() != null)
isRowEmpty = false;
}
else {
System.out.print("__");// - если элемент пустой
localStack.push(null);
localStack.push(null);
}
for (int j = 0; j < gaps * 2 - 2; j++)
System.out.print(' ');
}
System.out.println();
gaps /= 2;// при переходе на следующий уровень расстояние между elementми каждый раз уменьшается
while (localStack.isEmpty() == false)
globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
}
System.out.println(separator);// подводим черту
}
}
Powtórzę: nic zbyt skomplikowanego. Dostępne są opisane wcześniej operacje na drzewie wyszukiwania binarnego, a także metoda wyświetlania drzewa w konsoli. Cóż, teraz przyjrzyjmy się drzewu w akcji:
public class Application {
public static void main(String[] args) {
Tree tree = new Tree();
// вставляем узлы в дерево:
tree.insertNode(6);
tree.insertNode(8);
tree.insertNode(5);
tree.insertNode(8);
tree.insertNode(2);
tree.insertNode(9);
tree.insertNode(7);
tree.insertNode(4);
tree.insertNode(10);
tree.insertNode(3);
tree.insertNode(1);
// отображение дерева:
tree.printTree();
// удаляем один узел и выводим оставшееся дерево в консоли
tree.deleteNode(5);
tree.printTree();
// находим узел по значению и выводим его в консоли
Node foundNode = tree.findNodeByValue(7);
foundNode.printNode();
}
}
Operacje wyszukiwania/wstawiania/usuwania w drzewie wyszukiwania binarnego mają złożoność czasową O(log(N)) . Ale to najlepszy scenariusz. Ogólnie rzecz biorąc, złożoność czasowa operacji waha się od O(log(N)) do O(N) . Zależy to od stopnia degeneracji drzewa.
GO TO FULL VERSION