Дърво (структура от данни)
Дървото (или дървовидна структура) в програмирането е рекурсивна структура от данни, която се състои от върхове, които са свързани помежду си с ребра. За дърветата са в сила твърденията:
- Всеки връх може да има 0 или повече преки наследници (деца).
- Всеки връх има най-много един баща. Съществува точно един специален връх, който няма предшественици – коренът (ако дървото не е празно).
- Всички върхове са достижими от корена, т.е. съществува път от корена до всички тях.
В практиката често се налага да работа със съвкупност от обекти (данни). Данните, организирани в т. нар. структура от данни, позволяват обработване, така че това да доведе до подобрение качеството на работа с тях. Понякога се добавят елементи, понякога се премахват, друг могат да бъдат подредени по специфичен начин. В програмирането дървото е често използвана структура от данни, която изобразява по естествен начин всякакви йерархии от обекти и тяхната взаимосвързаност. [1]
Терминология[редактиране | редактиране на кода]
- Корен – Най-важния връх в дървото. Няма предшественици.
- Родител – предшественик на наследник.
- Братя – върхове с общ родител.
- Непряк наследник – връх който не е пряк наследник.
- Дете – пряк наследник.
- Прародител – връх, който е непряк родител.
- Вътрешен връх – връх, който има и родител, и дете.
- Външен връх (или листо) – връх, който няма наследници.
- Ребро – пряка връзка между два върха.
- Път – поредица от ребра между върховете.
- Дължина на път – броя на ребрата свързващи върховете.
- Дълбочина на връх – дължината на пътя от корена до върха.
- Височина на дърво – максималната дълбочина.
- Гора – съвкупност от несвързани дървета.
Описание[редактиране | редактиране на кода]
Дървото се състои от върхове, а линиите посредством които са свързани се наричат ребра. Върхът, който има наследници (деца), но няма родители (предшестеници) се нарича корен (root). Всеки друг връх може да има родител, както и 0 или повече деца. Коренът може да достигне всеки един връх. Абстрактното разстояние от корена до всяко едно разклонение и всеки връх се нарича път. Един връх не може да има повече от един родител. Следователно в едно дърво не може да има затворен кръг.[1]
Тип на данните срещу структура на данните[редактиране | редактиране на кода]
Съществува разлика между едно дърво като абстрактен тип данни и като конкретна структура от данни, аналогично на разграничението между списък и свързан списък. Като тип данни, дървото има стойност и деца, като и самите деца са дървета; стойността и децата на дървото се интерпретират като стойността на коренът и на поддървета на синовете на коренът. За да се даде възможност на крайните дървета, списъкът на децата трябва да бъде празен (в този случай дърветата може да не бъдат празни), или дърветата да бъдат празни, в този случай списъкът на децата може да бъде с определени размери, каквито пожелаем.
Като структура от данни, свързано дърво е група от възли (върхове), където всеки възел има стойност и списък с препратки към други възли (наследници). Тази структура данни определя насочена графика,[a], защото може да има цикли или няколко препратки към един и същи възел, както свързания списък може да има цикъл. Следователно не може две препратки да сочат към един и същи възел (всеки възел има точно по 1 родител с изключение на корена) и дърво което нарушава това е „корумпирано“.
Поради използването на препратки към дървета в свързано дърво-структура от данни. Дърветата са често имплицитно обсъждани, приемайки се, че те са представлявани от препратки към корена, тъй като това е често прилагана практика. Например, вместо празно дърво, може да няма препратки:дървото никога не е празно, но препратките към него могат да не съществуват.[1]
Двоично дърво[редактиране | редактиране на кода]
Дърво, в което броят на наследниците на върховете е 0, 1 или 2 се нарича двоично дърво. Преките наследници на всеки връх са два в този случай, затова единият се нарича ляв наследник, а другият – десен наследник (може и празно множество). Те, от своя страна, са корени съответно на лявото поддърво и на дясното поддърво на техния родител.
Има няколко основни операции при двоичните дървета: добавяне, изтриване, търсене, обхождане. Примерите по-долу са написани на Java.[1]
Двоичното дърво в Java изглежда по този начин:
public class Node {
private int data;
private Node left;
private Node right;
private Node parent;
public int getData() {
return this.data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return this.left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return this.right;
}
public void setRight(Node right) {
this.right = right;
}
public Node getParent() {
return this.parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
}
Добавяне[редактиране | редактиране на кода]
Добавянето на елемент в двоично дърво е операция, която има логаритмична сложност по отношение на размера на дървото. Всеки елемент в двоичното дърво има добре определена позиция, затова първо трябва да намерим къде трябва да го поставим, а после и да го направим. Следва и примера за добавяне:
public void insert(int data) {
root = insert(root, data, null);
}
private Node insert(Node current, int data, Node parent) {
if (current == null) {
current = new Node();
current.setData(data);
current.setLeft(null);
current.setRight(null);
current.setParent(parent);
} else if (data < current.getData()) {
current.setLeft(insert(current.getLeft(), data, current));
} else {
current.setRight(insert(current.getRight(), data, current));
}
return current;
}
Търсене[редактиране | редактиране на кода]
Търсенето изглежда като добавянето и отнема логаритмично време (logn).
public Node find(int data) {
return find(root, data);
}
private Node find(Node current, int data) {
if (current == null) {
return null;
}
if (current.getData() == data) {
return current;
}
return find(data < current.getData() ? current.getLeft() : current.getRight(), data);
}
Двоичното дърво има някои интересни характеристики, позволяващи ни да намерим специални елементи много лесно. Например минималният и максималният елемент. Най-малката стойност е тази, която се намира най-вляво, а максималната – най-вдясно.
public Node findMin() {
Node min = root;
if (min == null) {
return null;
}
while (min.getLeft() != null) {
min = min.getLeft();
}
return min;
}
Изтриване[редактиране | редактиране на кода]
Изтриването на елемент от дърво е най-трудната операция. Тя също отнема logn време. Има няколко специални ситуации, които трябва да бъдат овладени:
- Изтриване на елемент без деца – просто освобождаваме паметта.
- Изтриване на елемент само с едно дете – промяна на указателите на родителя да сочат директно към детето на изтривания елемент и освобождаване на паметта.
- Изтриване на елемент само с едно дете и това е КОРЕНЪТ – преместване на детето на мястото на корена и освобождаване на паметта.
- Изтриване на елемент с две деца – това е най-сложната операция. Най-добрият начин за изпълнение е да бъдат разменени стойностите на изтривания елемент и максималната стойност на лявото поддърво или минималната на дясното поддърво (защото това ще запази характеристиките на дървото) и тогава да изтрием елемент без или с едно дете.
public void delete(int data) {
root = delete(root, data);
}
private Node delete(Node startNode, int data) {
Node element = find(startNode, data);
if (element == null) {
return startNode;
}
boolean hasParent = element.getParent() != null;
boolean isLeft = hasParent && element.getData() < element.getParent().getData();
if (element.getLeft() == null && element.getRight() == null) {
if (hasParent) {
if (isLeft) {
element.getParent().setLeft(null);
} else {
element.getParent().setRight(null);
}
}
} else if (element.getLeft() != null && element.getRight() == null) {
if (hasParent) {
if (isLeft) {
element.getParent().setLeft(element.getLeft());
} else {
element.getParent().setRight(element.getLeft());
}
} else {
startNode = element.getLeft();
}
} else if (element.getLeft() == null && element.getRight() != null) {
if (hasParent) {
if (isLeft) {
element.getParent().setLeft(element.getRight());
} else {
element.getParent().setRight(element.getRight());
}
} else {
startNode = element.getRight();
}
} else {
Node rightMin = findMin(element.getRight());
element.setData(rightMin.getData());
return delete(rightMin, rightMin.getData());
}
element = null;
return startNode;
}
Обхождане на дърво[редактиране | редактиране на кода]
Съществуват три типа обхождане на двоични дървета:
- Inorder – посещаване на лявото поддърво, корена и дясното поддърво.
- Preorder – посещаване на корена, лявото поддърво и дясното поддърво.
- Postorder – посещаване на лявото поддърво, дясното поддърво и корена.
public void traverseTree(TraverseType traverseType) {
traverseTree(root, traverseType);
System.out.println();
}
private void traverseTree(Node current, TraverseType traverseType) {
if (current == null) {
return;
}
switch (traverseType) {
case INORDER:
traverseTree(current.getLeft(), traverseType);
processNode(current);
traverseTree(current.getRight(), traverseType);
break;
case PREORDER:
processNode(current);
traverseTree(current.getLeft(), traverseType);
traverseTree(current.getRight(), traverseType);
break;
case POSTORDER:
traverseTree(current.getLeft(), traverseType);
traverseTree(current.getRight(), traverseType);
processNode(current);
break;
}
}
Вижте също[редактиране | редактиране на кода]
Източници[редактиране | редактиране на кода]
- ↑ а б в г Наков, Светлин. Въведение в програмирането с Java. София, 2017. ISBN 978-954-400-055-4. с. 561-594.
