Prelude
Ushbu maqola ikkilik qidiruv daraxtlari haqida. Men yaqinda haqida maqola yozdim U erda men binar daraxtlarga e'tibor bermadim, chunki qidirish, kiritish, o'chirish usullari tegishli emas edi. Endi men daraxtlar haqida maqola yozishga qaror qildim. Balki boshlaymiz.
Daraxt - bu qirralar bilan bog'langan tugunlardan tashkil topgan ma'lumotlar strukturasi. Aytishimiz mumkinki, daraxt grafikning maxsus holatidir. Mana misol daraxt:
Bu ikkilik qidiruv daraxti emas! Hamma narsa kesilgan ostida!
Terminologiya
Ildiz
Daraxt ildizi eng yuqori tugun hisoblanadi. Misolda, bu tugun A. Daraxtda faqat bitta yo'l ildizdan boshqa tugunga olib kelishi mumkin! Aslida, har qanday tugunni ushbu tugunga mos keladigan pastki daraxtning ildizi deb hisoblash mumkin.
Ota-onalar / avlodlar
Ildizdan tashqari barcha tugunlar boshqa tugunga olib boradigan aniq bir chekkaga ega. Joriy tugun ustidagi tugun chaqiriladi ota-ona bu tugun. Joriydan pastda joylashgan va unga ulangan tugun deyiladi avlod bu tugun. Keling, bir misol keltiraylik. B tugunni oling, keyin uning ota-onasi A tugun bo'ladi va uning bolalari D, E va F tugunlari bo'ladi.
Sheet
Bolalari bo'lmagan tugun daraxtning bargi deb ataladi. Misolda D, E, F, G, I, J, K tugunlari barglar bo'ladi.
Bu asosiy terminologiya. Boshqa tushunchalar keyinroq muhokama qilinadi. Shunday qilib, ikkilik daraxt - bu har bir tugunning ikkitadan ortiq bolasi bo'lmagan daraxt. Siz taxmin qilganingizdek, misoldagi daraxt ikkilik bo'lmaydi, chunki B va H tugunlarida ikkitadan ortiq bola bor. Ikkilik daraxtga misol:
Daraxtning tugunlari har qanday ma'lumotni o'z ichiga olishi mumkin. Ikkilik qidiruv daraxti ikkilik daraxt bo'lib, quyidagi xususiyatlarga ega:
- Chap va o'ng pastki daraxtlar ikkilik qidiruv daraxtlaridir.
- Ixtiyoriy X tugunining chap pastki daraxtining barcha tugunlari X tugunining ma'lumotlar kaliti qiymatidan kamroq ma'lumotlar kaliti qiymatlariga ega.
- Ixtiyoriy X tugunining o'ng pastki daraxtining barcha tugunlari ma'lumotlar kaliti qiymatlariga X tugunining ma'lumotlar kalitining qiymatidan kattaroq yoki tengdir.
Kalit - tugunning ba'zi xarakteristikalari (masalan, raqam). Ushbu kalitga mos keladigan daraxt elementini topish uchun kalit kerak. Ikkilik qidiruv daraxtiga misol:
daraxt ko'rinishi
Men davom etar ekanman, tushunishingizni yaxshilash uchun ba'zi (ehtimol to'liq bo'lmagan) kod qismlarini qo'shaman. To'liq kod maqolaning oxirida bo'ladi.
Daraxt tugunlardan iborat. Tugun tuzilishi:
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;
}
//...остальные методы узла
}
Har bir tugunning ikkita bolasi bor (solChild va/yoki rightChild bolalari null bo'lishi mumkin). Ehtimol, bu holda raqam ma'lumotlari tugunda saqlangan ma'lumotlar ekanligini tushungansiz; kalit - tugun kaliti.
Biz tugunni aniqladik, endi daraxtlar bilan bog'liq dolzarb muammolar haqida gapiraylik. Bu erda va pastda "daraxt" so'zi ikkilik qidiruv daraxti tushunchasini anglatadi. Ikkilik daraxt tuzilishi:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Sinf maydoni sifatida bizga faqat daraxtning ildizi kerak, chunki ildizdan getLeftChild() va getRightChild() usullaridan foydalanib, daraxtning istalgan tuguniga kirishingiz mumkin.
Daraxt algoritmlari
Поиск
Aytaylik, sizda qurilgan daraxt bor. Kalit kalit bilan elementni qanday topish mumkin? Siz ketma-ket ildizdan daraxtga o'tishingiz va kalit qiymatini keyingi tugunning kaliti bilan solishtirishingiz kerak: agar kalit keyingi tugunning kalitidan kichik bo'lsa, tugunning chap avlodiga o'ting, agar ko'p bo'lsa - o'ngga, agar kalitlar teng bo'lsa - kerakli tugun topildi! Tegishli kod:
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;
}
Agar oqim nol bo'lsa, unda iteratsiya daraxtning oxiriga yetdi (kontseptual darajada, siz daraxtda mavjud bo'lmagan joydasiz - barg bolasi).
Qidiruv algoritmining muvozanatli daraxtda (tugunlar ko'proq yoki kamroq taqsimlangan daraxt) samaradorligini ko'rib chiqing. Shunda qidiruv samaradorligi O(log(n)) va asos 2 logarifm bo'ladi Qarang: agar muvozanatli daraxtda n ta element bo'lsa, bu daraxtning log(n) tayanch 2 darajasi bo'lishini bildiradi. Va qidiruvda, tsiklning bir bosqichi uchun siz bir darajaga tushasiz.
joylashtiring
Agar siz qidiruvning mohiyatini tushungan bo'lsangiz, unda qo'shimchani tushunish siz uchun qiyin bo'lmaydi. Siz shunchaki daraxtning bargiga tushishingiz kerak (qidiruvda tasvirlangan nasl qoidalariga muvofiq) va uning avlodiga aylanishingiz kerak - kalitga qarab chap yoki o'ng. Amalga oshirish:
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;
}
}
}
}
}
Bunday holda, joriy tugunga qo'shimcha ravishda, joriy tugunning ota-onasi haqidagi ma'lumotlarni saqlash kerak. Joriy null bo'lganda, ota-o'zgaruvchi bizga kerak bo'lgan varaqni o'z ichiga oladi.
Qo'shish samaradorligi aniq qidiruv bilan bir xil bo'ladi - O(log(n)).
O'chir
O'chirish - bu daraxt bilan bajarilishi kerak bo'lgan eng murakkab operatsiya. Avvalo biz olib tashlaydigan elementni topishimiz kerakligi aniq. Ammo keyin nima? Agar biz shunchaki uning havolasini null ga o'rnatsak, u holda ildizi ushbu tugun bo'lgan pastki daraxt haqidagi ma'lumotni yo'qotamiz. Daraxtlarni olib tashlash usullari uchta holatga bo'linadi.
Birinchi holat. O'chiriladigan tugunning bolalari yo'q.
Agar o'chiriladigan tugunning bolalari bo'lmasa, bu uning barg ekanligini anglatadi. Shuning uchun, siz shunchaki ota-onasining leftChild yoki rightChild maydonlarini null qilib belgilashingiz mumkin.
Ikkinchi holat. Olib tashlanadigan tugunning bitta bolasi bor
Bu holat ham juda qiyin emas. Keling, misolimizga qaytaylik. Aytaylik, biz 14-kalitli elementni o'chirishimiz kerak. Bu 10-kalitli tugunning to'g'ri bolasi bo'lganligi sababli, uning avlodlaridan birida (bu holda, o'ngda) 10 dan katta kalit bo'ladi, deylik. uni daraxtdan osongina "kesib qo'yishi" mumkin va ota-onani to'g'ridan-to'g'ri o'chirilayotgan tugunning bolasiga ulashi mumkin, ya'ni. tugunni 10-kalit bilan 13-tugunga ulang. Agar ota-onasining chap bolasi bo'lgan tugunni o'chirish kerak bo'lsa, vaziyat shunga o'xshash bo'lar edi. O'zingiz o'ylab ko'ring - aniq o'xshatish.
Uchinchi holat. Nodening ikki farzandi bor
Eng qiyin holat. Keling, yangi misolni ko'rib chiqaylik.
Voris qidiring
Aytaylik, 25-kalit bilan tugunni olib tashlashimiz kerak. Uning o'rniga kimni qo'yamiz? Uning izdoshlaridan biri (avlodlari yoki avlodlari) bo'lishi kerak vorisi(olib tashlangan tugunning o'rnini egallagan kishi).
Voris kim bo'lishi kerakligini qanday bilasiz? Intuitiv ravishda, bu kaliti olib tashlangan tugundan keyingi eng katta bo'lgan daraxtdagi tugundir. Algoritm quyidagicha. Siz uning o'ng bolasiga borishingiz kerak (har doim o'ng tomonda, chunki merosxo'rning kaliti o'chirilayotgan tugunning kalitidan kattaroq ekanligi aytilgan edi) va keyin ushbu huquqning chap bolalari zanjiridan o'ting. bola. Misolda, biz 35-kalit bilan tugunga o'tishimiz kerak, so'ngra uning chap bolalari zanjiri bo'ylab bargga tushishimiz kerak - bu holda, bu zanjir faqat 30-kalitli tugundan iborat. To'g'ri aytganda, biz qidirmoqdamiz. kerakli tugundan kattaroq tugunlar to'plamidagi eng kichik tugun.
Voris qidirish usuli kodi:
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;
}
O'chirish usulining to'liq kodi:
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;
}
Murakkablikni O(log(n)) ga yaqinlashtirish mumkin.
Daraxtda maksimal/minimalni topish
Shubhasiz, daraxtdagi minimal / maksimal qiymatni qanday topish mumkin - navbati bilan daraxtning chap / o'ng elementlari zanjiridan o'tishingiz kerak; bargga kirganingizda, u minimal/maksimal element bo'ladi.
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;
}
Murakkablik - O(log(n))
Simmetrik aylanib o'tish
Traversal - bu daraxtning har bir tuguniga u bilan biror narsa qilish uchun tashrif buyurish.
Rekursiv simmetrik o'tish algoritmi:
- Chap bolaga harakat qiling
- O'zingiz bilan harakat qiling
- To'g'ri bolaga harakat qiling
Kod:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
xulosa
Nihoyat! Agar biror narsani tushuntirmagan bo'lsam yoki sharhlarim bo'lsa, sharhlarda kutaman. Va'da qilinganidek, bu erda to'liq kod.
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) ga degeneratsiya
Ko'pchiligingiz payqagan bo'lishingiz mumkin: agar siz daraxtning muvozanatini buzsangiz nima bo'ladi? Misol uchun, daraxtga o'sib borayotgan tugmachalar bilan tugunlarni qo'ying: 1,2,3,4,5,6... Keyin daraxt bog'langan ro'yxatni biroz eslatib turadi. Va ha, daraxt o'zining daraxt tuzilishini va shuning uchun ma'lumotlarga kirish samaradorligini yo'qotadi. Qidiruv, qo'shish va o'chirish operatsiyalarining murakkabligi bog'langan ro'yxat bilan bir xil bo'ladi: O(n). Bu mening fikrimcha, ikkilik daraxtlarning eng muhim kamchiliklaridan biridir.
So'rovda faqat ro'yxatdan o'tgan foydalanuvchilar ishtirok etishlari mumkin. iltimos.
Men Habré-ga anchadan beri kirmaganman va bilmoqchimanki, qaysi mavzularda qaysi maqolalarni ko'proq ko'rishni xohlaysiz?
Ma'lumotlar tuzilmalari
Algoritmlar (DP, rekursiya, ma'lumotlarni siqish va boshqalar)
Ma'lumotlar tuzilmalari va algoritmlarini hayotda qo'llash
Java-da android ilovalarini dasturlash
Java veb-ilovalarni dasturlash
2 ta foydalanuvchi ovoz berdi. 1 foydalanuvchi betaraf qoldi.
Manba: www.habr.com
