Foreplay
Tha an artaigil seo mu dheidhinn craobhan sgrùdaidh binary. Sgrìobh mi artaigil mu dheidhinn o chionn ghoirid An sin cha tug mi aire dha craobhan dà-chànanach, oir cha robh na dòighean sgrùdaidh, cuir a-steach, cuir às dha buntainneach. A-nis chuir mi romhpa artaigil a sgrìobhadh mu chraobhan. Is dòcha gun tòisich sinn.
Is e structar dàta a th’ ann an craobh anns a bheil nodan ceangailte le oirean. Faodaidh sinn a ràdh gu bheil craobh na chùis shònraichte de ghraf. Seo eisimpleir craobh:
Chan e craobh sgrùdaidh binary a tha seo! Tha a h-uile dad fon ghearradh!
Briathrachas
Freumh
Bun-chraobhan is e an nòs as àirde. Anns an eisimpleir, is e seo nód A. Anns a’ chraoibh, chan urrainn ach aon shlighe a dhol bhon fhreumh gu nód sam bith eile! Gu dearbh, faodar beachdachadh air nód sam bith mar bhunait an fho-chraobh a tha a rèir an nód seo.
Pàrantan / clann
Tha dìreach aon oir aig a h-uile nod ach am freumh a’ dol suas gu nód eile. Canar an nód os cionn an nód gnàthach pàrant an nód seo. Canar nód a tha suidhichte fon t-sruth agus ceangailte ris sliochd an nód seo. Gabhamaid eisimpleir. Gabh nód B, an uairsin bidh a phàrant na nód A, agus bidh a chlann nan nodan D, E, agus F.
Leaf
Canar duilleag na craoibhe ri nód aig nach eil clann. Anns an eisimpleir, bidh nodan D, E, F, G, I, J, K nan duilleagan.
Is e seo am briathrachas bunaiteach. Thèid bun-bheachdan eile a dheasbad nas fhaide air adhart. Mar sin, is e craobh dà-chànanach craobh anns nach bi barrachd air dithis chloinne aig gach nód. Mar a shaoileadh tu, cha bhi craobh bhon eisimpleir dà-chànanach, oir tha barrachd air dithis chloinne aig nodan B agus H. Seo eisimpleir de chraobh dàna:
Faodaidh fiosrachadh sam bith a bhith ann an nodan na craoibhe. Is e craobh dà-chànanach a th’ ann an craobh sgrùdaidh binary aig a bheil na feartan a leanas:
- Tha an dà chuid fo-chraobhan clì is deas nan craobhan sgrùdaidh dà-chànanach.
- Tha prìomh luachan dàta aig a h-uile nod den fho-chraobh chlì de nód neo-riaghailteach X na luach iuchair dàta an nód X fhèin.
- Tha prìomh luachan dàta aig a h-uile nod den fho-chraobh cheart de nód neo-riaghailteach X nas motha na no co-ionann ri luach iuchair dàta nód X fhèin.
Prìomh - cuid de fheartan an nód (mar eisimpleir, àireamh). Tha feum air an iuchair gus an lorgar an eileamaid den chraoibh ris a bheil an iuchair seo a’ freagairt. Eisimpleir craobh sgrùdaidh dà-chànanach:
sealladh craoibhe
Mar a thèid mi air adhart, bheir mi a-steach cuid de phìosan còd (is dòcha neo-choileanta) gus do thuigse adhartachadh. Bidh an còd slàn aig deireadh an artaigil.
Tha an craobh air a dhèanamh suas de nodan. Structar nòd:
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;
}
//...остальные методы узла
}
Tha dithis chloinne aig gach nód (tha e gu math comasach gum bi a’ chlann chlì agus/no a’ chlann leanabh deas null). Is dòcha gun do thuig thu sa chùis seo gur e dàta àireamh an dàta a tha air a stòradh san nód; iuchair - iuchair nod.
Dh'obraich sinn a-mach an snaidhm, a-nis bruidhnidh sinn mu na duilgheadasan èiginneach mu chraobhan. An seo às deidh sin, bidh am facal "craobh" a 'ciallachadh bun-bheachd craobh rannsachaidh dà-chànanach. Structar craobh dà-chànanach:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Mar raon clas, chan fheum sinn ach freumh na craoibhe, oir bhon fhreumh, a’ cleachdadh na dòighean getLeftChild() agus getRightChild(), gheibh thu gu nód sam bith den chraoibh.
Algorithms craobh
Поиск
Canaidh sinn gu bheil craobh thogte agad. Ciamar a lorgas tu eileamaid le prìomh iuchair? Feumaidh tu gluasad ann an sreath bhon fhreumh sìos a’ chraoibh agus coimeas a dhèanamh eadar luach an iuchrach le iuchair an ath nód: ma tha an iuchair nas lugha na iuchair an ath nód, an uairsin rachaibh gu sliochd clì an nód, ma tha barrachd - air an làimh dheis, ma tha na h-iuchraichean co-ionann - lorgar an nód a tha thu ag iarraidh! Còd iomchaidh:
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;
}
Ma dh'fhàsas an sruth neo-fhillte, tha an ath-aithris air deireadh na craoibhe a ruighinn (aig ìre bun-bheachdail, tha thu ann an àite nach eil ann sa chraoibh - leanabh le duilleach).
Beachdaich air èifeachdas an algairim sgrùdaidh air craobh cothromach (craobh anns a bheil nodan air an cuairteachadh barrachd no nas lugha). An uairsin bidh an èifeachdas sgrùdaidh O(log(n)), agus an logarithm bonn 2. Faic: ma tha n eileamaidean ann an craobh cothromach, bidh seo a’ ciallachadh gum bi log(n) bonn 2 ìre den chraoibh. Agus anns an rannsachadh, airson aon cheum den chuairt, thèid thu sìos aon ìre.
cuir a-steach
Ma tha thu air greim fhaighinn air brìgh an sgrùdaidh, cha bhith e duilich dhut an cuir a-steach a thuigsinn. Feumaidh tu dìreach a dhol sìos gu duilleag na craoibhe (a rèir riaghailtean teàrnaidh a chaidh a mhìneachadh san rannsachadh) agus a bhith na shliochd - clì no deas, a rèir an iuchair. Cur an gnìomh:
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;
}
}
}
}
}
Anns a 'chùis seo, a bharrachd air an nód làithreach, feumar fiosrachadh a stòradh mu phàrant an nód làithreach. Nuair a thig an sruth gu crìch, bidh an duilleag a tha a dhìth oirnn anns a’ chaochladair phàrant.
Tha e soilleir gum bi an èifeachdas cuir a-steach an aon rud ri èifeachdas an sgrùdaidh - O (log (n)).
Delete
Is e sguabadh às an obair as iom-fhillte a dh'fheumar a dhèanamh le craobh. Tha e soilleir gum feumar an-toiseach an eileamaid a tha sinn a’ dol a thoirt air falbh a lorg. Ach dè an uairsin? Ma tha sinn dìreach a’ suidheachadh an iomradh aige gu null, caillidh sinn fiosrachadh mun fho-chraobh aig a bheil freumh an nód seo. Tha dòighean toirt air falbh chraobhan air an roinn ann an trì cùisean.
A 'chiad chùis. Chan eil clann aig an nód a thèid a thoirt air falbh.
Mura h-eil clann aig an nód a thèid a dhubhadh às, tha e a’ ciallachadh gur e duilleag a th’ ann. Mar sin, faodaidh tu dìreach na raointean clìChild no rightChild aig a phàrant a chuir gu neo-null.
An dàrna cùis. Tha aon leanabh aig an nód a thèid a thoirt air falbh
Chan eil a 'chùis seo gu math duilich cuideachd. Rachamaid air ais chun eisimpleir againn. Osbarr feumaidh sinn eileamaid a dhubhadh às le iuchair 14. Aontaich leis gur e an leanabh ceart den nód le iuchair 10, gum bi iuchair aig gin de a shliochd (sa chùis seo, an tè cheart) nas motha na 10, mar sin bidh thu is urrainn dhaibh a “ghearradh” bhon chraoibh gu furasta, agus am pàrant a cheangal gu dìreach ri leanabh an nód a thèid a dhubhadh às, i.e. ceangail an nód le iuchair 10 gu nód 13. Bhiodh an suidheachadh coltach ris nam feumadh sinn nòta a sguabadh às a tha mar leanabh clì a phàrant. Smaoinich mu dheidhinn dhut fhèin - fìor shamhla.
An treas cùis. Tha dithis chloinne aig Node
A 'chùis as duilghe. Bheir sinn sùil air eisimpleir ùr.
Lorg neach-leantainn
Canaidh sinn gum feum sinn an nód a thoirt air falbh leis an iuchair 25. Cò a chuireas sinn na àite? Feumaidh aon de a luchd-leanmhainn (sliochd no sliochd sliochd) a bhith neach-leantainn(am fear a ghabhas àite an nòta a chaidh a thoirt air falbh).
Ciamar a tha fios agad cò a bu chòir a bhith na neach-leantainn? Gu h-iongantach, is e seo an nód anns a 'chraoibh aig a bheil an iuchair an ath rud as motha bhon nód a thèid a thoirt air falbh. Tha an algairim mar a leanas. Feumaidh tu a dhol chun leanabh ceart aige (an-còmhnaidh chun an fhear cheart, oir chaidh a ràdh mar-thà gu bheil iuchair an neach-leantainn nas motha na iuchair an nód a bhith air a dhubhadh às), agus an uairsin a dhol tron t-sreath de chlann chlì den taobh cheart seo leanabh. Anns an eisimpleir, feumaidh sinn a dhol chun nód le iuchair 35, agus an uairsin a dhol sìos slabhraidh a chlann chlì chun na duilleige - anns a 'chùis seo, chan eil anns an t-seine seo ach an nód le iuchair 30. Gu cruaidh, tha sinn a' coimhead airson an nód as lugha anns an t-seata de nodan nas motha na an nód a thathar ag iarraidh.
Còd modh sgrùdaidh an neach-leantainn:
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;
}
Còd iomlan an dòigh sguabaidh às:
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;
}
Faodar an iom-fhillteachd a thomhas gu O(log(n)).
Lorg an ìre as àirde/as ìsle ann an craobh
Gu follaiseach, mar a lorgas tu an luach as ìsle / as àirde sa chraoibh - feumaidh tu a dhol tro shreath de eileamaidean clì / deas na craoibhe, fa leth; nuair a ruigeas tu an duilleag, bidh e mar an eileamaid as ìsle / as àirde.
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;
}
Iom-fhillteachd - O(log(n))
Seach-rathad co-chothromach
Is e Traversal tadhal air gach nód den chraoibh gus rudeigin a dhèanamh leis.
Algorithm tar-chuir co-chothromach ath-chuairteach:
- Dèan gnìomh air an leanabh chlì
- Dèan gnìomh leat fhèin
- Dèan gnìomh air an leanabh cheart
Còd:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
co-dhùnadh
Mu dheireadh thall! Mura do mhìnich mi rudeigin no ma tha beachdan sam bith agam, tha mi a’ feitheamh anns na beachdan. Mar a chaidh a ghealltainn, seo an còd iomlan.
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
crìonadh gu O(n)
Is dòcha gu bheil mòran agaibh air mothachadh: dè ma bheir thu air a’ chraobh fàs neo-chothromach? Mar eisimpleir, cuir nodan anns a 'chraoibh le iuchraichean a tha a' sìor fhàs: 1,2,3,4,5,6 ... An uairsin bidh a 'chraobh rudeigin mar chuimhneachan air liosta ceangailte. Agus tha, caillidh a 'chraobh a structar craoibhe, agus mar sin èifeachdas ruigsinneachd dàta. Bidh iom-fhillteachd obair sgrùdaidh, cuir a-steach agus cuir às an aon rud ri liosta ceangailte: O(n). Is e seo aon de na h-eas-bhuannachdan as cudromaiche, nam bheachd-sa, de chraobhan binary.
Chan fhaod ach luchd-cleachdaidh clàraichte pàirt a ghabhail san sgrùdadh. , mas e do thoil e.
Chan eil mi air a bhith air Habré airson ùine mhòr, agus bu mhath leam faighinn a-mach dè na h-artaigilean air na cuspairean a bhiodh tu airson barrachd fhaicinn?
-
Structaran Dàta
-
Algorithms (DP, ath-chuairteachadh, teannachadh dàta, msaa)
-
Cur an sàs structaran dàta agus algorithms ann am fìor bheatha
-
A ' dèanamh phrògraman airson Android ann an java
-
Prògramachadh aplacaidean-lìn java
Bhòt 2 luchd-cleachdaidh. Cha do stad 1 neach-cleachdaidh.
Tobar: www.habr.com