Prelude
Бұл мақала екілік іздеу ағаштары туралы. Мен жақында мақала жаздым Онда мен екілік ағаштарға көп мән бермедім, өйткені іздеу, кірістіру және жою әдістері маңызды болмады. Енді мен ағаштар туралы мақала жазуды шештім. Бастайық.
Ағаш - жиектермен қосылған түйіндерден тұратын деректер құрылымы. Ағашты графиктің ерекше жағдайы деп айта аламыз. Міне мысал ағаш:
Бұл екілік іздеу ағашы емес! Барлығы кесілген!
Терминология
Түбір
Ағаш тамыры - бұл оның ең жоғарғы түйіні. Мысалда бұл А түйіні. Ағашта тек бір жол түбірден кез келген басқа түйінге апара алады! Іс жүзінде кез келген түйінді осы түйінге сәйкес келетін ішкі ағаштың түбірі ретінде қарастыруға болады.
Ата-ана/ұрпақ
Түбірден басқа барлық түйіндердің басқа түйінге апаратын дәл бір жиегі бар. Ағымдағыдан жоғары орналасқан түйін шақырылады ата-ана бұл түйін. Ағымдағыдан төмен орналасқан және оған қосылған түйін деп аталады ұрпақ бұл түйін. Мысал келтірейік. В түйінін алайық, онда оның ата-анасы А түйіні, ал оның балалары 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;
}
//...остальные методы узла
}
Әрбір түйінде екі еншілес болады (lelaChild және/немесе 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 элемент болса, онда бұл негізгі 2 деңгейге log(n) болатынын білдіреді. ағаш. Ал іздеуде, циклдің бір қадамында сіз бір деңгейге түсесіз.
қондыру
Егер сіз іздеудің мәнін түсінсеңіз, онда кірістіруді түсіну сізге қиын болмайды. Сізге ағаштың жапырағына (іздеуде сипатталған түсіру ережелеріне сәйкес) түсіп, оның ұрпағы болу керек - кілтке байланысты солға немесе оңға. Іске асыру:
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)).
Жою
Жою - ағашта жасалуы керек ең қиын операция. Алдымен біз жойылатын элементті табуымыз керек екені анық. Бірақ сонда ше? Егер біз оның сілтемесін нөлге жай ғана орнатсақ, біз бұл түйін түбір болып табылатын ішкі ағаш туралы ақпаратты жоғалтамыз. Ағаштарды жою әдістері үш жағдайға бөлінеді.
Бірінші жағдай. Жойылатын түйіннің еншілестері жоқ
Егер жойылатын түйінде балалар болмаса, бұл оның жапырақ екенін білдіреді. Сондықтан, оның ата-анасының 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). Бұл екілік ағаштардың ең маңызды, менің ойымша, кемшіліктерінің бірі.
Сауалнамаға тек тіркелген пайдаланушылар қатыса алады. , өтінемін.
Мен хабта көптен бері болған жоқпын және қандай тақырыптардағы қандай мақалаларды көбірек көргіңіз келетінін білгім келеді?
-
Мәліметтер құрылымдары
-
Алгоритмдер (DP, рекурсия, деректерді қысу және т.б.)
-
Мәліметтер құрылымдары мен алгоритмдерін өмірде қолдану
-
Java тілінде Android қолданбаларын бағдарламалау
-
Java тілінде веб-қосымшаларды бағдарламалау
2 пайдаланушы дауыс берді. 1 пайдаланушы қалыс қалды.
Дереккөз: www.habr.com