Preliwd
Mae'r erthygl hon yn ymwneud Γ’ choed chwilio deuaidd. Yn ddiweddar gwnes i erthygl am Yno ni wnes i dalu llawer o sylw i goed deuaidd, oherwydd nid oedd y dulliau chwilio, mewnosod a dileu yn berthnasol. Nawr penderfynais ysgrifennu erthygl am goed. Gadewch i ni ddechrau.
Mae coeden yn strwythur data sy'n cynnwys nodau wedi'u cysylltu gan ymylon. Gallwn ddweud bod coeden yn achos arbennig o graff. Dyma goeden enghreifftiol:
Nid coeden chwilio ddeuaidd yw hon! Mae popeth wedi'i dorri!
Terminoleg
Root
Gwreiddyn coed β dyma ei nΓ΄d uchaf. Yn yr enghraifft, dyma nod A. Mewn coeden, dim ond un llwybr all arwain o'r gwreiddyn i unrhyw nod arall! Mewn gwirionedd, gellir ystyried unrhyw nod fel gwraidd yr is-goeden sy'n cyfateb i'r nod hwn.
Rhieni/disgynyddion
Mae gan bob nod ac eithrio'r gwraidd un ymyl yn union yn arwain at nod arall. Gelwir y nod sydd wedi'i leoli uwchben yr un presennol rhiant y nod hwn. Gelwir nod sydd wedi'i leoli o dan yr un presennol ac sy'n gysylltiedig ag ef disgynnydd y nod hwn. Gadewch i ni ddefnyddio enghraifft. Gadewch i ni gymryd nod B, yna bydd ei riant yn nod A, a'i blant fydd nodau D, E ac F.
ΠΠΈΡΡ
Bydd nod heb blant yn cael ei alw'n ddeilen y goeden. Yn yr enghraifft, nodau D, E, F, G, I, J, K fydd y dail.
Dyma'r derminoleg sylfaenol. Bydd cysyniadau eraill yn cael eu trafod ymhellach. Felly, coeden ddeuaidd yw coeden lle na fydd gan bob nod fwy na dau o blant. Fel y gwnaethoch chi ddyfalu, ni fydd y goeden o'r enghraifft yn ddeuaidd, oherwydd mae gan nodau B a H fwy na dau o blant. Dyma enghraifft o goeden ddeuaidd:
Gall nodau'r goeden gynnwys unrhyw wybodaeth. Mae coeden chwilio ddeuaidd yn goeden ddeuaidd sydd Γ’'r priodweddau canlynol:
- Mae is-goed chwith a dde yn goed chwilio deuaidd.
- Mae gan bob nod o is-goeden chwith nod mympwyol X werthoedd allwedd data sy'n llai na gwerth allwedd data nod X ei hun.
- Mae gan bob nod yn is-goeden dde nod mympwyol X werthoedd allwedd data sy'n fwy neu'n hafal i werth allwedd data nod X ei hun.
Allwedd β unrhyw nodwedd o'r nod (er enghraifft, rhif). Mae angen yr allwedd fel y gallwch ddod o hyd i'r elfen goeden y mae'r allwedd hon yn cyfateb iddi. Enghraifft o goeden chwilio ddeuaidd:
Golygfa coed
Wrth i ni symud ymlaen, byddaf yn darparu rhai darnau o god (anghyflawn o bosibl) i wella'ch dealltwriaeth. Bydd y cod llawn ar ddiwedd yr erthygl.
Mae coeden yn cynnwys nodau. Strwythur nod:
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;
}
//...ΠΎΡΡΠ°Π»ΡΠ½ΡΠ΅ ΠΌΠ΅ΡΠΎΠ΄Ρ ΡΠ·Π»Π°
}
Mae gan bob nod ddau o blant (mae'n ddigon posibl y bydd y plentyn chwith a/neu'r plant Plentyn ar y dde yn cynnwys gwerth null). Mae'n debyg eich bod wedi sylweddoli yn yr achos hwn mai'r data rhif yw'r data sydd wedi'i storio yn y nod; allwedd β allwedd nod.
Rydyn ni wedi datrys y cwlwm, nawr gadewch i ni siarad am broblemau dybryd am goed. O hyn ymlaen, wrth y gair βcoedenβ byddaf yn golygu'r cysyniad o goeden chwilio ddeuaidd. Strwythur coed deuaidd:
public class BinaryTree<T> {
private Node<T> root;
//ΠΌΠ΅ΡΠΎΠ΄Ρ Π΄Π΅ΡΠ΅Π²Π°
}
Dim ond gwraidd y goeden sydd ei angen arnom fel maes dosbarth, oherwydd o'r gwraidd, gan ddefnyddio'r dulliau getLeftChild() a getRightChild(), gallwch gyrraedd unrhyw nod yn y goeden.
Algorithmau mewn coeden
Chwilio
Gadewch i ni ddweud bod gennych goeden wedi'i hadeiladu. Sut i ddod o hyd i elfen gyda'r allwedd allweddol? Mae angen i chi symud yn ddilyniannol o'r gwreiddyn i lawr y goeden a chymharu gwerth y cywair ag allwedd y nod nesaf: os yw'r allwedd yn llai nag allwedd y nod nesaf, yna ewch i ddisgynnydd chwith y nod, os yw mwy, i'r un iawn, os yw'r allweddi yn gyfartal, mae'r nod dymunol yn dod o hyd! Cod perthnasol:
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;
}
Os yw'r cerrynt yn dod yn null, yna mae'r chwiliad wedi cyrraedd diwedd y goeden (ar lefel gysyniadol, rydych chi mewn man nad yw'n bodoli yn y goeden - disgynnydd deilen).
Gadewch i ni ystyried effeithiolrwydd yr algorithm chwilio ar goeden gytbwys (coeden lle mae nodau'n cael eu dosbarthu'n fwy neu'n llai cyfartal). Yna bydd yr effeithlonrwydd chwilio yn O(log(n)), a'r logarithm yw sylfaen 2. Edrychwch: os oes n elfen mewn coeden gytbwys, mae hyn yn golygu y bydd log(n) i sylfaen 2 lefel y coeden. Ac wrth chwilio, mewn un cam o'r cylch, rydych chi'n mynd i lawr un lefel.
mewnosod
Os ydych chi'n deall hanfod y chwiliad, yna ni fydd deall y mewnosodiad yn anodd i chi. Does ond angen i chi fynd i lawr i ddeilen y goeden (yn Γ΄l y rheolau disgyniad a ddisgrifir yn y chwiliad) a dod yn ddisgynnydd iddo - i'r chwith neu'r dde, yn dibynnu ar yr allwedd. Gweithredu:
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;
}
}
}
}
}
Yn yr achos hwn, yn ychwanegol at y nod cyfredol, mae angen storio gwybodaeth am riant y nod cyfredol. Pan ddaw cerrynt yn hafal i nwl, bydd y newidyn rhiant yn cynnwys y ddalen sydd ei hangen arnom.
Mae'n amlwg y bydd effeithlonrwydd mewnosod yr un fath ag effeithlonrwydd chwilio - O(log(n)).
Tynnu
Tynnu yw'r llawdriniaeth anoddaf y bydd angen ei chyflawni ar goeden. Maeβn amlwg yn gyntaf y bydd angen inni ddod o hyd iβr elfen yr ydym yn mynd iβw dileu. Ond beth felly? Os byddwn yn syml yn gosod ei gyfeiriad at nwl, byddwn yn colli gwybodaeth am yr is-goeden y mae'r nod hwn yn wraidd iddi. Rhennir dulliau tynnu coed yn dri achos.
Achos cyntaf. Nid oes gan y nod sy'n cael ei ddileu unrhyw blant
Os nad oes gan y nod sy'n cael ei ddileu unrhyw blant, yna mae hyn yn golygu ei fod yn ddeilen. Felly, gallwch chi osod meysydd leftChild neu rightChild ei riant i null.
Ail achos. Mae gan y nod sydd i'w ddileu un plentyn
Nid yw'r achos hwn yn gymhleth iawn ychwaith. Gadewch i ni ddychwelyd at ein hesiampl. Gadewch i ni ddweud bod angen i ni ddileu elfen gydag allwedd 14. Cytuno, gan ei fod yn ddisgynnydd cywir nod ag allwedd 10, y bydd gan unrhyw un o'i ddisgynyddion (yr un iawn yn yr achos hwn) allwedd sy'n fwy na 10, felly chi yn gallu ei βdorriβ allan oβr goeden yn hawdd, a chysylltuβr rhiant yn uniongyrchol Γ’ phlentyn y nod syβn cael ei ddileu, h.y. cysylltu'r nod ag allwedd 10 i nod 13. Byddai'r sefyllfa'n debyg pe bai angen dileu nod sy'n blentyn chwith i'w riant. Meddyliwch am y peth eich hun - cyfatebiaeth union.
Trydydd achos. Mae gan nod ddau o blant
Yr achos anoddaf. Gadewch i ni edrych ar enghraifft newydd.
Chwilio am olynydd
Gadewch i ni ddweud bod angen i ni ddileu nod ag allwedd 25. Pwy ddylem ni ei roi yn ei le? Rhaid i un o'i ddilynwyr (disgynyddion neu ddisgynyddion disgynyddion) ddod olynydd(yr un a gymmer le y nΓ΄d yn cael ei symud).
Sut i ddeall pwy ddylai ddod yn olynydd? Yn reddfol, mae hwn yn nod yn y goeden a'i allwedd yw'r mwyaf nesaf o'r nod sy'n cael ei ddileu. Mae'r algorithm fel a ganlyn. Mae angen i chi fynd at ei ddisgynnydd dde (bob amser i'r un dde, oherwydd dywedwyd eisoes bod allwedd yr olynydd yn fwy na'r allwedd y nod sy'n cael ei ddileu), ac yna mynd trwy'r gadwyn o ddisgynyddion chwith y disgynnydd dde hwn . Yn yr enghraifft, byddem yn mynd i'r nod gydag allwedd 35, ac yna'n mynd i lawr i'r ddeilen trwy gadwyn ei blant chwith - yn yr achos hwn, mae'r gadwyn hon yn cynnwys y nod gydag allwedd 30 yn unig. A siarad yn fanwl, rydym yn edrych ar gyfer y nod lleiaf yn y set o nodau sy'n fwy na'r un yr ydym yn chwilio amdano.
Cod dull chwilio olynol:
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;
}
Cod llawn ar gyfer y dull dileu:
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;
}
Gellir brasamcanu'r cymhlethdod i O(log(n)).
Dod o hyd i uchafswm/lleiafswm mewn coeden
Mae'n amlwg sut i ddarganfod y gwerth lleiaf/uchaf mewn coeden - mae angen i chi symud yn ddilyniannol ar hyd y gadwyn o elfennau chwith/dde y goeden, yn y drefn honno; pan fyddwch chi'n cyrraedd y ddalen, dyma fydd yr elfen leiaf/uchaf.
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;
}
Cymhlethdod - O(log(n))
Ffordd osgoi cymesur
Mae Traversal yn ymweld Γ’ phob nod o'r goeden er mwyn gwneud rhywfaint o weithredu ag ef.
Algorithm croesi cymesurol dychweliadol:
- Gwnewch weithred ar y plentyn chwith
- Gwnewch weithred gyda chi'ch hun
- Gwnewch weithred ar y plentyn iawn
CΓ΄d:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//ΠΠ΄Π΅ΡΡ ΠΌΠΎΠΆΠ΅Ρ Π±ΡΡΡ Π²ΡΠ΅, ΡΡΠΎ ΡΠ³ΠΎΠ΄Π½ΠΎ
inOrder(current.getRightChild());
}
}
Casgliad
O'r diwedd! Os nad wyf wedi egluro unrhyw beth neu os oes gennyf unrhyw sylwadau, gadewch nhw yn y sylwadau. Fel yr addawyd, rwy'n darparu'r cod cyflawn.
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
Dirywiad i O(n)
Efallai bod llawer ohonoch wedi sylwi: beth os gwnewch y goeden yn anghytbwys? Er enghraifft, rhowch nodau ag allweddi cynyddol mewn coeden: 1,2,3,4,5,6... Yna bydd y goeden braidd yn debyg i restr gysylltiedig. Ac ie, bydd y goeden yn colli ei strwythur coed, ac felly effeithlonrwydd mynediad data. Bydd cymhlethdod gweithrediadau chwilio, mewnosod a dileu yn dod yr un fath Γ’ rhai rhestr gysylltiedig: O(n). Dyma un o'r anfanteision pwysicaf, yn fy marn i, o goed deuaidd.
Dim ond defnyddwyr cofrestredig all gymryd rhan yn yr arolwg. os gwelwch yn dda.
Nid wyf wedi bod ar y canolbwynt ers amser maith, a hoffwn wybod pa erthyglau ar ba bynciau yr hoffech chi weld mwy ohonynt?
-
Strwythurau Data
-
Algorithmau (DP, dychweliad, cywasgu data, ac ati)
-
Cymhwyso strwythurau data ac algorithmau mewn bywyd go iawn
-
Rhaglennu Cymwysiadau Android yn Java
-
Rhaglennu cymwysiadau gwe yn Java
Pleidleisiodd 2 ddefnyddiwr. Ymatalodd 1 defnyddiwr.
Ffynhonnell: www.habr.com