Kahendpuu
Definitsion
Kahendpuu on erijuht puust.
Puu
Warning
Puu levinuim definitsioon informaatikas erineb pisut graafiteoreetilisest definitsioonist
Puu on graaf, mis:
On sidus (igast tipust on võimalik leida tee mööda servi igasse teise tippu)
On tsükliteta (graafis ei leidu teed, mille esimene ja viimane tipp oleksid samad)
Omab "juurtippu", millel võib olla "lapstippusid". Lapstippudel võib olla omakorda lapstippe.
Siin on näide graafist, mis ei ole puu:
graph G {
v1
v2 -- v3
v3 -- v4
v4 -- v2
}
Ülaltoodud graaf pole ilmselgelt ei sidus ega atsükliline.
Siin on näide graafist, mis on puu:
graph T {
v1 -- v2
v1 -- v3
v1 -- v4
v2 -- v5
}
See graaf on sidus, tsükliteta, ning omab vanem-laps hierarhiat - seega on tegemist puuga.
Kahendpuu
Kahendpuu on puu, mille igal tipul on maksimaalselt kaks lapstippu.
Siin on näide kahendpuust:
graph T {
v1 -- v2
v1 -- v3
v2 -- v4
v2 -- v5
v3 -- v6
v3 -- v7
}
Kahendpuu on üks kurikuulsamaid ja olulisemaid andmestruktuure informaatikas - suures osas kindlasti seetõttu, et nende abil on võimalik luua andmestruktuure, millel on palju kasulikke omadusi.
Kahend-otsingupuud
Kahendpuu üheks levinuimaks kasutusjuhuks on kahend-otsingupuu. Kui käsitleme elemente, mis on omavahel järjestatavad, siis võime ükshaaval puusse lisada elemente nii, et vasakutpidi mööda servi alla minnes väärtused kahanevad, ning paremale minnes kasvavad:
Kusjuures, kahend-otsingupuul kehtib omadus, et mistahes vanemtipu vasakpoolne alampuu sisaldab vaid vanemtipust väiksemaid väärtusti, ning mistahes vanemtipu parempoolne alampuu sisaldab vaid vanemtipust suuremaid väärtusi.
Warning
Sõltuvalt definitsioonist võib kahend-otsingupuu kas lubada duplikaatelemente või mitte. Lihtsuse huvides eeldame, et duplikaadid pole puus lubatud.
Juhul, kui puu vasakule ja paremale poole jääb sama palju elemente, siis mistahes elementi puus on võimalik leida logaritmilise ajalise keerukusega.
Note
Logaritmiline ajaline keerukus tähendab praktikas "väga, väga kiiresti". Näiteks, 2^64 (ehk 18446744073709551616) elementi sisaldavast kahend-otsingupuust elemendi leidmine, või elemendi sinna lisamine, võtaks halvimal juhul vaid 64 iteratsiooni. Eeldades, et ühe tipu esitamine võtab 12 baiti, siis sellise puu mälus hoidmine võtaks üle 220000 petabaidi mälu.
Muidugi ei pruugi kahend-otsingupuu alati tasakaalu jääda. Vaatle:
var tree = Tree.fromRoot(5);
tree.addElementsConsecutively(List.of(6, 7, 4, 8, 9))
Sellisel juhul ei ole puu tasakaalus, ning elementide sisestamine ning leidmine on halvimal juhul lineaarse (n) ajalise keerukusega.
Õnneks on kahend-otsingupuid võimalik täiendada, et nad oleksid iseennast tasakaalustavad - s.t. nad jäävad alati tasakaalu pärast elemendi sisestamist. Levinud näited sellistest implementatsioonidest on AVL-puud ja Red-Black puud. Nõndaviisi jääb elemendi sisestamine ja otsimine alati logaritmilise ajalise keerukuse peale.
Esitamine mälus
Kahendpuu ja kahend-otsingupuu esitamine mälus on samaväärne - erineb vaid sisestamine ja otsimine. Javas võib teha seda niiviisi:
public class Node<T> {
private final T value;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T value) {
this.value = value;
}
public Node(T value, Node<T> leftChild, Node<T> rightChild) {
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
public Node<T> getLeftChild() {
return leftChild;
}
public void setLeftChild(Node<T> leftChild) {
this.leftChild = leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public void setRightChild(Node<T> rightChild) {
this.rightChild = rightChild;
}
public T getValue() {
return value;
}
}
public class BinarySearchTree<T extends Comparable<T>> {
private final Node<T> root;
public BinarySearchTree(Node<T> root) {
this.root = root;
}
}
Comparable alamtüübi kitsendus on vajalik, et kindlustada, et puus sisalduvad väärtused oleksid võrreldavad `compareTo meetodiga. Teisisõnu, kahend-otsingupuu vajab, et selles sisalduvad elemendid oleksid järjestatavad.
Kasutamine:
var root = new Node<>(
3,
new Node<>(2),
new Node<>(5,
new Node<>(4),
null
)
);
var tree = new BinarySearchTree<>(root);
Elemendi lisamine
Kui tahame säilitada kahend-otsingupuu eelmainitud omadusi, peame uusi elemente sisestama kindlat viisi:
public class BinarySearchTree<T extends Comparable<T>> {
private final Node<T> root;
// ...
public void insert(T value) {
insertSubtree(value, root); // Begin inserting at the root of the tree
}
private void insertSubtree(T value, Node<T> parent) {
if (value.compareTo(parent.getValue()) < 0)
// if the value to be inserted is less than the current node,
// insert using the 'insertLessThan' strategy
insertLessThan(value, parent);
else
// otherwise, insert using the 'insertGreaterThan' strategy
insertGreaterThan(value, parent);
}
private void insertLessThan(T value, Node<T> parent) {
if (parent.getLeftChild() == null)
// if there is no left subtree (i.e. the current node is a leaf)
// set the left child of the current node to be a new node wrapping the inserted value
parent.setLeftChild(new Node<>(value));
else
// otherwise, insert the value into the left subtree
insertSubtree(value, parent.getLeftChild());
}
private void insertGreaterThan(T value, Node<T> parent) {
if (parent.getRightChild() == null)
// if there is no right subtree (i.e. the current node is a leaf)
// set the right child of the current node to be a new node wrapping the inserted value
parent.setRightChild(new Node<>(value));
else
// otherwise, insert the value into the right subtree
insertSubtree(value, parent.getRightChild());
}
}
Näide
Ütleme, et tahame siia kahend-otsingupuusse sisestada väärtuse 83:
Element peaks jääma elemendi 85 vasakpoolseks lapseks.
Sammud:
võrdle 83 ja 100 -> väiksem -> sisesta vasakule
võrdle 83 ja 50 -> suurem -> sisesta paremale
võrdle 83 ja 75 -> suurem -> sisesta paremale
võrdle 83 ja 80 -> suurem -> sisesta paremale
võrdle 83 ja 85 -> väiksem -> sisesta vasakule
võrdle 83 ja _ -> alampuu puudub -> loo uus alampuu vasakule, kus on vaid tipp väärtusega 83
Elemendi leidmine
Puud saab sama põhimõttega läbida ka selleks, et leida elemente:
public class BinarySearchTree<T extends Comparable<T>> {
private final Node<T> root;
public boolean contains(T value) {
return containsSubtree(value, root);
}
private boolean containsSubtree(T value, Node<T> parent) {
if (parent == null)
return false;
else if (value.compareTo(parent.getValue()) == 0)
return true;
else if (value.compareTo(parent.getValue()) < 0)
return containsSubtree(value, parent.getLeftChild());
else
return containsSubtree(value, parent.getRightChild());
}
}
Sama loogikat kasutades ning meetodite tagastatud väärtusi pisut muutes võib leida ka väikseima elemendi puus, mis on suurem kui mingi väärtus X, või suurima elemendi puus, mis on väiksem kui väärtus X.
Sügavuse leidmine
Kahendotsingupuu sügavuse leidmiseks peab käima läbi kõik puu tipud. Seda võib "tõestada" triviaalselt kasutades puu definitsiooni: kui puus on ükski avastamata tipp, siis võib sellel tipu lapstipp moodustada kuistahes sügava alampuu. Seega ei saa olla puu sügavauses kindel enne, kui kõik tipud on läbi käidud.
See tähendab ka seda, et puu sügavuse leidmine on tippude arvu suhtes lineaarse ajalise keerukusega algoritm.
Sügavust võib leida mistahes algoritmiga, mis külastab kõiki tippe. Lihtsaim on levinud rekursiivne lahendus, mis on olemuselt sarnane eelnevatele koodijuppidele:
public class BinarySearchTree<T extends Comparable<T>> {
private final Node<T> root;
public BinarySearchTree(Node<T> root) {
this.root = root;
}
public int getDepth() {
return subtreeDepth(root);
}
private int subtreeDepth(Node<T> node) {
if (node == null)
return 0;
final int leftSubtreeDepth = subtreeDepth(node.getLeftChild());
final int rightSubtreeDepth = subtreeDepth(node.getRightChild());
final int greatestSubtreeDepth = Math.max(leftSubtreeDepth, rightSubtreeDepth);
return greatestSubtreeDepth + 1;
}
}
Algoritmi võib lugeda nii:
depth(T) = max(depth(T.leftSubtree), depth(T.rightSubtree)) + 1
On ilmne, et definitsioon genereerib mistahes tipu puhul õige sügavuse.
Näiteks, juurtipu T puhul: kui T vasak laps on alampuu sügavusega 7, parem laps on alampuu sügavusega 9, siis terve puu sügavus on max(7, 9) + 1 => 10.
Elementide järjestatud läbimine
Kahendotsingupuu elementide läbimiseks on mitmeid strateegiaid. Lihtsaim neist on inorder traversal, mis läbib kõik tipud elementide väärtuste järjestatuse järjekorras.
Seda võib implementeerida niiviisi:
public class BinarySearchTree<T extends Comparable<T>> {
private final Node<T> root;
public BinarySearchTree(Node<T> root) {
this.root = root;
}
public void inorderTraverse(Consumer<Node<T>> f) {
inorderTraverseSubtree(f, root);
}
private void inorderTraverseSubtree(Consumer<Node<T>> f, Node<T> node) {
if (node == null)
return;
inorderTraverseSubtree(f, node.getLeftChild());
f.accept(node);
inorderTraverseSubtree(f, node.getRightChild());
}
// ...
}
Meetodil on Consumer<Node<T>> parameeter, et tippude peal oleks võimalik järjestatult kõrvalmõjusid rakendada (nt. väärtuse välja printimine). See pole probleemi olemusega seotud, ent on vajalik, et järjestatud läbimine oleks "vaadeldav".
Meetod on üles ehitatud nii, et iga puu vasakpoolseimad alampuud läbitakse süvitsi esimesena. Alles vasakpoolse leheni jõudes hakatakse parempoolset alampuud läbima.
Funktsiooni rakendamine f.accept(node) asukoht meetodis on oluline - selline paigutus on ainus viis kuidas garanteerida, et kõrvalmõjud rakenduksid inorder järjekorras.
Näide
public class Main {
public static void main(String[] args) {
var bst = new BinarySearchTree<>(new Node<>(5));
IntStream.range(1, 5).forEach(bst::insert);
IntStream.range(6, 11).forEach(bst::insert);
bst.inorderTraverse(node -> System.out.println(node.getValue()));
}
}
Väljund:
1
2
3
4
5
6
7
8
9
10