Aðdragandi
Þessi grein fjallar um tvíleitartré. Ég skrifaði nýlega grein um Þarna tók ég ekki alveg eftir tvíundartré, því aðferðirnar við að leita, setja inn, eyða áttu ekki við. Nú ákvað ég að skrifa grein um tré. Kannski byrjum við.
Tré er gagnabygging sem samanstendur af hnútum tengdum með brúnum. Við getum sagt að tré sé sértilfelli af línuriti. Hér er dæmi um tré:
Þetta er ekki tvíleitartré! Allt er undir högg að sækja!
Terminology
Rót
Rót trjáa er efsti hnúturinn. Í dæminu er þetta hnútur A. Í trénu getur aðeins ein leið leitt frá rótinni að öðrum hnút! Í raun er hægt að líta á hvaða hnút sem er sem rót undirtrésins sem samsvarar þessum hnút.
Foreldrar/afkvæmi
Allir hnútar nema rótin hafa nákvæmlega eina brún sem leiðir upp að öðrum hnút. Hnúturinn fyrir ofan núverandi hnút er kallaður foreldri þennan hnút. Hnútur sem staðsettur er fyrir neðan núverandi og tengdur við hann er kallaður afkomandi þennan hnút. Tökum dæmi. Taktu hnút B, þá verður foreldri hans hnútur A og börn hans verða hnútar D, E og F.
Blað
Hnútur sem hefur engin börn er kallað lauf trésins. Í dæminu verða hnútar D, E, F, G, I, J, K laufblöð.
Þetta er grunnhugtökin. Önnur hugtök verða rædd síðar. Svo, tvöfaldur tré er tré þar sem hver hnút mun ekki hafa fleiri en tvö börn. Eins og þú giskaðir á, verður tréð úr dæminu ekki tvöfalt, vegna þess að hnútar B og H eiga fleiri en tvö börn. Hér er dæmi um tvíundartré:
Hnútar trésins geta innihaldið hvaða upplýsingar sem er. Tvíundarleitartré er tvíundartré sem hefur eftirfarandi eiginleika:
- Bæði vinstri og hægri undirtré eru tvíleitartré.
- Allir hnútar í vinstra undirtrénu í handahófskenndum hnút X hafa gagnalykilgildi sem eru lægri en gagnalykilgildi hnútsins X sjálfs.
- Allir hnútar hægra undirtrésins í handahófskenndum hnút X eru með gagnalyklagildi sem eru stærri en eða jöfn gildi gagnalykils hnútsins X sjálfs.
Lykill - einhver einkenni hnútsins (til dæmis tala). Lykillinn er nauðsynlegur til að geta fundið frumefni trésins sem þessi lykill samsvarar. Dæmi um tvíleitarleit:
tré útsýni
Þegar ég fer áfram mun ég láta nokkur (kannski ófullkomin) kóða stykki fylgja með til að bæta skilning þinn. Kóðinn í heild sinni verður í lok greinarinnar.
Tréð er byggt upp úr hnútum. Uppbygging hnúta:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...остальные методы узла
}
Hver hnút hefur tvö börn (það er alveg mögulegt að leftChild og/eða rightChild börnin verði núll). Þú hefur líklega skilið að í þessu tilfelli eru tölugögnin gögnin sem eru geymd í hnútnum; lykill - hnútalykill.
Við komumst að hnútnum, nú skulum við tala um brýn vandamál varðandi tré. Hér og fyrir neðan mun orðið „tré“ þýða hugtakið tvíleitartré. Tvöfaldur tré uppbygging:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Sem bekkjarreitur þurfum við aðeins rót trésins, því frá rótinni, með því að nota getLeftChild() og getRightChild() aðferðir, geturðu komist að hvaða hnút sem er í trénu.
Trjáalgrím
leita
Segjum að þú sért með byggt tré. Hvernig á að finna frumefni með lykillykli? Þú þarft að færa í röð frá rótinni niður í tréð og bera saman gildi lykils við lykil næsta hnút: ef lykill er minni en lykill næsta hnút, farðu þá í vinstri afkvæmi hnútsins, ef meira - til hægri, ef lyklarnir eru jafnir - hnúturinn sem óskað er eftir finnst! Viðeigandi kóði:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
Ef straumur verður að engu, þá hefur endurtekning náð endanum á trénu (á hugmyndalegu stigi ertu á stað sem ekki er til í trénu - barn af laufblaði).
Íhugaðu skilvirkni leitarreikniritsins á jafnvægistré (tré þar sem hnútum er dreift meira eða minna jafnt). Þá verður leitarvirknin O(log(n)), og logaritminn 2. Sjá: ef það eru n þættir í jafnvægistré, þá þýðir það að það verða log(n) grunn 2 stig af trénu. Og í leitinni, að einu skrefi í hringrásinni, ferðu niður um eitt stig.
setja
Ef þú hefur skilið kjarna leitarinnar, þá mun það ekki vera erfitt fyrir þig að skilja innsetninguna. Þú þarft bara að fara niður að laufblaði trésins (samkvæmt reglum um uppruna sem lýst er í leitinni) og verða afkomandi þess - vinstri eða hægri, allt eftir lyklinum. Framkvæmd:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
Í þessu tilviki, til viðbótar við núverandi hnút, er nauðsynlegt að geyma upplýsingar um foreldri núverandi hnút. Þegar núverandi verður núll, mun foreldrabreytan innihalda blaðið sem við þurfum.
Skilvirkni innsetningar verður augljóslega sú sama og leitin - O(log(n)).
Eyða
Eyðing er flóknasta aðgerðin sem þarf að gera með tré. Það er ljóst að fyrst verður að finna þáttinn sem við ætlum að fjarlægja. En hvað þá? Ef við einfaldlega stillum tilvísun þess á núll, þá munum við missa upplýsingar um undirtréð sem hefur rót þessa hnút. Aðferðum til að fjarlægja trjáa er skipt í þrjú tilvik.
Fyrsta málið. Hnúturinn sem á að fjarlægja á engin börn.
Ef hnúturinn sem á að eyða hefur engin börn þýðir það að það sé laufblað. Þess vegna geturðu einfaldlega stillt leftChild eða rightChild reiti foreldris þess á núll.
Annað mál. Hnúturinn sem á að fjarlægja hefur eitt barn
Þetta mál er heldur ekki mjög erfitt. Förum aftur að dæminu okkar. Segjum sem svo að við þurfum að eyða einingu með lykli 14. Sammála því að þar sem það er rétt barn hnútsins með lykli 10, þá mun einhver af afkomendum hans (í þessu tilfelli, sá rétti) hafa lykil sem er stærri en 10, svo þú getur auðveldlega „klippt“ það úr trénu, og tengt foreldrið beint við barn hnútsins sem verið er að eyða, þ.e. tengja hnútinn með lykli 10 við hnút 13. Ástandið væri svipað ef við þyrftum að eyða hnút sem er vinstra barn foreldris þess. Hugsaðu um það sjálfur - nákvæm líking.
Þriðja mál. Node á tvö börn
Erfiðasta málið. Lítum á nýtt dæmi.
Leitaðu að eftirmanni
Segjum að við þurfum að fjarlægja hnútinn með lyklinum 25. Hvern eigum við að setja í staðinn? Einn af fylgjendum hans (niðjar eða afkomendur afkomenda) verður að verða eftirmaður(sá sem mun koma í stað fjarlægða hnútsins).
Hvernig veistu hver ætti að vera arftaki? Innsæi er þetta hnúturinn í trénu þar sem lykillinn er næststærstur frá hnútnum sem verið er að fjarlægja. Reikniritið er sem hér segir. Þú þarft að fara til hægri barnsins þess (alltaf til hægri, því það var þegar sagt að lykillinn að arftakanum væri stærri en lykillinn á hnútnum sem verið er að eyða) og fara síðan í gegnum keðjuna af vinstri börnum þessa hægri. barn. Í dæminu verðum við að fara í hnútinn með lykli 35 og fara síðan niður keðju vinstri barna hans að laufblaðinu - í þessu tilfelli samanstendur þessi keðja aðeins af hnútnum með lykli 30. Strangt til tekið erum við að leita að minnsti hnúturinn í mengi hnúta stærri en æskilegur hnútur.
Kóði eftirleitaraðferðar:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//родитель преемника
Node<T> successor = deleteNode;//преемник
Node<T> current = successor.getRightChild();//просто "пробегающий" узел
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//на выходе из цикла имеем преемника и родителя преемника
if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
}
return successor;
}
Heildarkóði eyðingaraðferðarinnar:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//второй случай
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//третий случай
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
Flækjustigið má nálgast við O(log(n)).
Að finna hámark/lágmark í tré
Augljóslega, hvernig á að finna lágmark / hámarksgildi í trénu - þú þarft að fara í röð í gegnum keðju vinstri / hægri þátta trésins, í sömu röð; þegar þú kemur að laufinu verður það lágmark/hámark þáttur.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
Flækjustig - O(log(n))
Samhverf hjáleið
Traversal er að heimsækja hvern hnút trésins til að gera eitthvað við það.
Endurkvæmt samhverft yfirferðaralgrím:
- Gerðu aðgerð á vinstra barnið
- Gerðu aðgerð með sjálfum þér
- Gerðu aðgerð á rétta barnið
Code:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Ályktun
Loksins! Ef ég útskýrði ekki eitthvað eða hef einhverjar athugasemdir, þá bíð ég í athugasemdunum. Eins og lofað var, hér er heill kóðinn.
Node.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
Hörnun í O(n)
Mörg ykkar hafa kannski tekið eftir: hvað ef þú gerir tréð í ójafnvægi? Til dæmis, settu hnúta í tréð með stækkandi lyklum: 1,2,3,4,5,6... Þá mun tréð minna nokkuð á tengdan lista. Og já, tréð mun missa trébygginguna og þar með skilvirkni gagnaaðgangs. Flækjustig leitar-, innsetningar- og eyðingaraðgerða verður sú sama og tengds lista: O(n). Þetta er einn mikilvægasti, að mínu mati, ókostur tvíundirtrjáa.
Aðeins skráðir notendur geta tekið þátt í könnuninni. , takk.
Ég hef ekki verið á Habré í langan tíma og mig langar að vita hvaða greinar um hvaða efni myndir þú vilja sjá meira?
-
Gagnauppbyggingar
-
Reiknirit (DP, endurtekning, gagnaþjöppun osfrv.)
-
Notkun gagnabygginga og reiknirita í raunveruleikanum
-
Forritun Android forrit í Java
-
Java vefforritun
2 notendur kusu. 1 notandi sat hjá.
Heimild: www.habr.com