Նախերգանք
Այս հոդվածը երկուական որոնման ծառերի մասին է: Վերջերս ես հոդված գրեցի դրա մասին Այնտեղ ես իսկապես ուշադրություն չէի դարձնում երկուական ծառերին, քանի որ որոնման, տեղադրելու, ջնջելու մեթոդները տեղին չէին։ Հիմա որոշեցի հոդված գրել ծառերի մասին։ Երևի կսկսենք։
Ծառը տվյալների կառուցվածք է, որը բաղկացած է եզրերով միացված հանգույցներից: Կարելի է ասել, որ ծառը գրաֆիկի հատուկ դեպք է։ Ահա մի ծառի օրինակ.
Սա երկուական որոնման ծառ չէ: Ամեն ինչ կտրվածքի տակ է:
Տերմինոլոգիա
արմատ
Ծառի արմատը ամենավերին հանգույցն է: Օրինակում սա A հանգույցն է: Ծառի մեջ միայն մեկ ճանապարհ կարող է տանել արմատից ցանկացած այլ հանգույց: Իրականում ցանկացած հանգույց կարելի է համարել որպես այս հանգույցին համապատասխան ենթածառի արմատ։
Ծնողներ/զավակ
Բոլոր հանգույցները, բացի արմատից, ունեն ուղիղ մեկ եզր, որը տանում է դեպի մեկ այլ հանգույց: Ընթացիկ հանգույցից վերեւ գտնվող հանգույցը կոչվում է ծնող այս հանգույցը. Կոչվում է հանգույցը, որը գտնվում է ընթացիկի տակ և միացված է դրան ժառանգ այս հանգույցը. Օրինակ բերենք. Վերցրեք B հանգույցը, այնուհետև դրա ծնողը կլինի A հանգույցը, իսկ երեխաները կլինեն D, E և F հանգույցները:
Թերթիկը
Այն հանգույցը, որը երեխաներ չունի, կոչվում է ծառի տերեւ: Օրինակում D, E, F, G, I, J, K հանգույցները կլինեն տերևներ:
Սա հիմնական տերմինաբանությունն է: Այլ հասկացությունները կքննարկվեն ավելի ուշ: Այսպիսով, երկուական ծառը ծառ է, որում յուրաքանչյուր հանգույց կունենա ոչ ավելի, քան երկու երեխա: Ինչպես կռահեցիք, օրինակի ծառը երկուական չի լինի, քանի որ B և H հանգույցներն ունեն ավելի քան երկու երեխա: Ահա երկուական ծառի օրինակ.
Ծառի հանգույցները կարող են պարունակել ցանկացած տեղեկատվություն։ Երկուական որոնման ծառը երկուական ծառ է, որն ունի հետևյալ հատկությունները.
- Ե՛վ ձախ, և՛ աջ ենթածառերը երկուական որոնման ծառեր են:
- Կամայական X հանգույցի ձախ ենթածառի բոլոր հանգույցներն ունեն տվյալների բանալու արժեքներ ավելի քիչ, քան հենց X հանգույցի տվյալների բանալու արժեքը:
- Կամայական X հանգույցի աջ ենթածառի բոլոր հանգույցներն ունեն տվյալների բանալու արժեքներ ավելի մեծ կամ հավասար են հենց X հանգույցի տվյալների բանալու արժեքին:
Բանալին - հանգույցի որոշ բնութագրեր (օրինակ, թիվ): Բանալին անհրաժեշտ է, որպեսզի կարողանանք գտնել ծառի այն տարրը, որին համապատասխանում է այս բանալին: Երկուական որոնման ծառի օրինակ.
ծառի տեսք
Մինչ ես շարունակեմ, ես կներառեմ կոդի որոշ (գուցե թերի) կտորներ՝ ձեր հասկացողությունը բարելավելու համար: Ամբողջական կոդը կլինի հոդվածի վերջում։
Ծառը կազմված է հանգույցներից։ Հանգույցի կառուցվածքը:
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;
}
//...остальные методы узла
}
Յուրաքանչյուր հանգույց ունի երկու երեխա (միանգամայն հնարավոր է, որ leftChild և/կամ rightChild երեխաները զրոյական լինեն): Հավանաբար հասկացաք, որ այս դեպքում թվային տվյալները հանգույցում պահվող տվյալներն են; բանալին - հանգույցի բանալի:
Մենք պարզեցինք հանգույցը, հիմա եկեք խոսենք ծառերի հրատապ խնդիրների մասին: Այսուհետ «ծառ» բառը կնշանակի երկուական որոնման ծառ հասկացությունը: Երկուական ծառի կառուցվածք.
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Որպես դասի դաշտ՝ մեզ անհրաժեշտ է միայն ծառի արմատը, քանի որ արմատից, օգտագործելով getLeftChild() և getRightChild() մեթոդները, կարող եք հասնել ծառի ցանկացած հանգույց։
Ծառի ալգորիթմներ
Որոնել
Ենթադրենք, դուք կառուցված ծառ ունեք: Ինչպե՞ս գտնել տարրը բանալիով: Դուք պետք է հաջորդաբար շարժվեք արմատից դեպի ծառը և համեմատեք բանալու արժեքը հաջորդ հանգույցի բանալին. դեպի աջ, եթե ստեղները հավասար են, ցանկալի հանգույցը գտնված է: Համապատասխան կոդը:
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;
}
Եթե հոսանքը դառնում է զրոյական, ապա կրկնությունը հասել է ծառի վերջին (կոնցեպտուալ մակարդակում դուք գտնվում եք ծառի գոյություն չունեցող տեղում՝ տերևի երեխա):
Դիտարկենք որոնման ալգորիթմի արդյունավետությունը հավասարակշռված ծառի վրա (ծառ, որում հանգույցները քիչ թե շատ հավասարաչափ բաշխված են): Այնուհետև որոնման արդյունավետությունը կլինի O(log(n)), իսկ բազային 2 լոգարիթմը: Տես՝ եթե հավասարակշռված ծառում կա n տարր, ապա դա նշանակում է, որ ծառի log(n) բազային 2 մակարդակները կլինեն: Իսկ որոնումների ընթացքում ցիկլի մեկ քայլի համար դուք իջնում եք մեկ մակարդակ:
տեղադրել
Եթե դուք ըմբռնել եք որոնման էությունը, ապա ձեզ համար դժվար չի լինի հասկանալ ներդրումը։ Պարզապես պետք է իջնել ծառի տերևի մոտ (ըստ որոնման մեջ նկարագրված ծագման կանոնների) և դառնալ նրա հետնորդը՝ աջ կամ ձախ՝ կախված բանալիից։ Իրականացում:
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;
}
}
}
}
}
Այս դեպքում, բացի ընթացիկ հանգույցից, անհրաժեշտ է պահպանել ընթացիկ հանգույցի ծնողի մասին տեղեկատվություն: Երբ ընթացիկը դառնում է զրոյական, մայր փոփոխականը կպարունակի մեզ անհրաժեշտ թերթիկը:
Տեղադրման արդյունավետությունը ակնհայտորեն նույնն է, ինչ որոնումը - O(log(n)):
Հեռացում
Ջնջումը ամենաբարդ գործողությունն է, որը պետք է կատարվի ծառի հետ: Հասկանալի է, որ նախ անհրաժեշտ կլինի գտնել այն տարրը, որը մենք պատրաստվում ենք հեռացնել։ Բայց հետո ի՞նչ։ Եթե մենք պարզապես սահմանենք դրա հղումը null, ապա մենք կկորցնենք տեղեկատվությունը այն ենթածառի մասին, որի արմատը այս հանգույցն է: Ծառերի հեռացման մեթոդները բաժանված են երեք դեպքերի.
Առաջին դեպք. Հեռացվող հանգույցը երեխաներ չունի:
Եթե ջնջվող հանգույցը երեխաներ չունի, նշանակում է, որ այն տերեւ է։ Հետևաբար, դուք կարող եք պարզապես զրոյական դարձնել նրա ծնողի leftChild կամ rightChild դաշտերը:
Երկրորդ դեպք. Հեռացվող հանգույցն ունի մեկ երեխա
Այս դեպքը նույնպես շատ դժվար չէ։ Վերադառնանք մեր օրինակին։ Ենթադրենք, որ մենք պետք է ջնջենք 14-րդ բանալի ունեցող տարրը: Համաձայնեք, որ քանի որ այն 10-րդ ստեղնով հանգույցի ճիշտ զավակն է, ապա նրա ժառանգներից որևէ մեկը (այս դեպքում՝ ճիշտը) կունենա 10-ից մեծ բանալի, այնպես որ դուք կարող է հեշտությամբ «կտրել» այն ծառից և ծնողին միացնել անմիջապես ջնջվող հանգույցի երեխային, այսինքն. հանգույցը միացրեք 10-րդ ստեղնով 13-րդ հանգույցին: Իրավիճակը նման կլիներ, եթե մենք ստիպված լինեինք ջնջել մի հանգույց, որն իր ծնողի ձախ երեխան է: Մտածեք դրա մասին ինքներդ՝ ճշգրիտ անալոգիա:
Երրորդ դեպք. Հանգույցը երկու երեխա ունի
Ամենադժվար դեպքը. Եկեք նայենք նոր օրինակին:
Որոնել իրավահաջորդի
Ենթադրենք, մենք պետք է հեռացնենք հանգույցը 25 բանալիով: Ո՞ւմ դնենք դրա տեղը: Նրա հետևորդներից մեկը (հետնորդները կամ հետնորդները) պետք է դառնա իրավահաջորդ(նա, ով կզբաղեցնի հեռացված հանգույցի տեղը):
Ինչպե՞ս գիտեք, թե ով պետք է լինի իրավահաջորդը: Ինտուիտիվորեն սա ծառի այն հանգույցն է, որի բանալին հաջորդ ամենամեծն է հանվող հանգույցից: Ալգորիթմը հետևյալն է. Դուք պետք է գնաք նրա աջ երեխայի մոտ (միշտ աջ, քանի որ արդեն ասվել էր, որ իրավահաջորդի բանալին ավելի մեծ է, քան ջնջվող հանգույցի բանալին), այնուհետև անցեք այս աջ ձախ երեխաների շղթայով։ երեխա. Օրինակում մենք պետք է գնանք դեպի հանգույցը 35-րդ բանալիով, այնուհետև իջնենք նրա ձախ երեխաների շղթայով դեպի տերևը. այս դեպքում այս շղթան բաղկացած է միայն 30-րդ բանալիով հանգույցից: Խստորեն ասած՝ մենք փնտրում ենք. ցանկալի հանգույցից ավելի մեծ հանգույցների հավաքածուի ամենափոքր հանգույցը:
Հետնորդի որոնման մեթոդի կոդը.
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;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная 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;
}
Բարդությունը կարելի է մոտավորել O(log(n)):
Ծառի մեջ առավելագույն/նվազագույնը գտնելը
Ակնհայտ է, թե ինչպես գտնել ծառի նվազագույն / առավելագույն արժեքը - դուք պետք է հաջորդաբար անցնեք ծառի ձախ / աջ տարրերի շղթայի միջով, համապատասխանաբար. երբ հասնեք տերևին, դա կլինի նվազագույն/առավելագույն տարրը:
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;
}
Բարդություն - O(log(n))
Սիմետրիկ շրջանցում
Տրավերսալը այցելություն է ծառի յուրաքանչյուր հանգույց՝ դրա հետ ինչ-որ բան անելու համար:
Ռեկուրսիվ սիմետրիկ անցման ալգորիթմ.
- Կատարեք գործողություն ձախ երեխայի վրա
- Գործողություն արեք ինքներդ ձեզ հետ
- Գործողություն արեք ճիշտ երեխայի վրա
Կոդ `
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Ամփոփում
Վերջապես! Եթե ինչ-որ բան չեմ բացատրել կամ որևէ մեկնաբանություն չունեմ, ապա սպասում եմ մեկնաբանություններում։ Ինչպես խոստացել էինք, ահա ամբողջական կոդը։
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
Դեգեներացիա դեպի O(n)
Ձեզանից շատերը կարող են նկատել. իսկ եթե դուք ստիպեք ծառին անհավասարակշիռ դառնալ: Օրինակ՝ ծառի մեջ տեղադրեք հանգույցներ՝ աճող ստեղներով՝ 1,2,3,4,5,6... Այնուհետև ծառը որոշակիորեն կհիշեցնի կապակցված ցուցակը։ Եվ այո, ծառը կկորցնի իր ծառի կառուցվածքը և հետևաբար տվյալների հասանելիության արդյունավետությունը: Որոնման, տեղադրման և ջնջման գործողությունների բարդությունը կդառնա նույնը, ինչ կապակցված ցուցակում. O(n): Սա երկուական ծառերի ամենակարևոր, իմ կարծիքով, թերություններից մեկն է:
Հարցմանը կարող են մասնակցել միայն գրանցված օգտվողները։ , խնդրում եմ:
Ես բավականին երկար ժամանակ է, ինչ Habré-ում չեմ եղել, և կցանկանայի իմանալ, թե ինչ թեմաներով ինչ հոդվածներ կցանկանայիք ավելի շատ տեսնել:
-
Տվյալների կառուցվածքներ
-
Ալգորիթմներ (DP, ռեկուրսիա, տվյալների սեղմում և այլն)
-
Տվյալների կառուցվածքների և ալգորիթմների կիրառում իրական կյանքում
-
Android հավելվածների ծրագրավորում Java-ում
-
Java վեբ հավելվածների ծրագրավորում
Քվեարկել է 2 օգտատեր։ 1 օգտատեր ձեռնպահ է մնացել։
Աղբյուրը` www.habr.com