From Wikipedia, the free encyclopedia
Дърво (или дървовидна структура) в програмирането е рекурсивна структура от данни, която се състои от върхове, които са свързани помежду си с ребра. За дърветата са в сила твърденията:
В практиката често се налага да работа със съвкупност от обекти (данни). Данните, организирани в т. нар. структура от данни, позволяват обработване, така че това да доведе до подобрение качеството на работа с тях. Понякога се добавят елементи, понякога се премахват, друг могат да бъдат подредени по специфичен начин. В програмирането дървото е често използвана структура от данни, която изобразява по естествен начин всякакви йерархии от обекти и тяхната взаимосвързаност.[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;
}
Съществуват три типа обхождане на двоични дървета:
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;
}
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
