ProHoster > Blog > Идораи > Дарахти дуӣ ё чӣ тавр тайёр кардани дарахти ҷустуҷӯи бинарӣ

Дарахти дуӣ ё чӣ тавр тайёр кардани дарахти ҷустуҷӯи бинарӣ

Аввалан

Ин мақола дар бораи дарахтони ҷустуҷӯии бинарӣ мебошад. Ман ба наздикӣ мақолае дар бораи фишурдасозии маълумот бо усули Huffman. Дар он ҷо ман ба дарахтони бинарӣ чандон аҳамият надодам, зеро усулҳои ҷустуҷӯ, воридкунӣ ва несткунӣ мувофиқ набуданд. Ҳоло ман тасмим гирифтам, ки дар бораи дарахтон мақола нависам. Биёед оғоз кунем.

Дарахт сохтори додаҳоест, ки аз гиреҳҳои бо кунҷҳо пайвастшуда иборат аст. Мо гуфта метавонем, ки дарахт як ҳолати махсуси график аст. Дар ин ҷо як дарахти намунавӣ аст:

Дарахти дуӣ ё чӣ тавр тайёр кардани дарахти ҷустуҷӯи бинарӣ

Ин дарахти ҷустуҷӯии бинарӣ нест! Ҳама чиз бурида шудааст!

Терминология

Реша

Решаи дарахт - ин гиреҳи болоии он аст. Дар мисол, ин гиреҳи А аст. Дар дарахт танҳо як роҳ метавонад аз реша ба ҳама гиреҳи дигар барад! Дар асл, ҳама гиреҳро метавон решаи зердарахти ба ин гиреҳ мувофиқ ҳисоб кард.

Падару модар/насл

Ҳама гиреҳҳо, ба истиснои реша, маҳз як канор доранд, ки ба гиреҳи дигар мебарад. Гиреде, ки дар боло ҷойгир аст, номида мешавад падару модар ин гирех. Гиреҳе, ки дар зери нуқтаи ҷорӣ ҷойгир аст ва ба он пайваст номида мешавад авлод ин гирех. Биёед мисолеро истифода барем. Гиреҳи В-ро гирем, пас волидайни он гиреҳи А ва фарзандонаш гиреҳҳои D, E ва F хоҳанд буд.

Лавҳаи

Гиреде, ки фарзанд надорад, барги дарахт номида мешавад. Дар мисол, баргҳо гиреҳҳои D, E, F, G, I, J, K хоҳанд буд.

Ин истилоҳоти асосӣ аст. Консепсияҳои дигар минбаъд баррасӣ хоҳанд шуд. Ҳамин тавр, дарахти бинарӣ дарахтест, ки дар он ҳар як гиреҳ на бештар аз ду фарзанд дорад. Тавре ки шумо тахмин кардед, дарахти мисол бинарӣ нахоҳад буд, зеро гиреҳҳои B ва H зиёда аз ду фарзанд доранд. Ин аст як мисоли дарахти бинарӣ:

Дарахти дуӣ ё чӣ тавр тайёр кардани дарахти ҷустуҷӯи бинарӣ

Гиреҳҳои дарахт метавонанд ҳама гуна маълумотро дар бар гиранд. Дарахти ҷустуҷӯи бинарӣ дарахти бинарӣ мебошад, ки дорои хосиятҳои зерин аст:

  1. Зердарахтҳои чап ва рост дарахтони ҷустуҷӯии дуӣ мебошанд.
  2. Ҳама гиреҳҳои зердарахти чапи гиреҳи ихтиёрии X дорои арзишҳои калиди маълумот аз арзиши калиди маълумоти худи гиреҳи X мебошанд.
  3. Ҳама гиреҳҳо дар зердарахти рости гиреҳи худсаронаи 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 элемент мавҷуд бошад, ин маънои онро дорад, ки дар асоси 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))

Роҳи симметрӣ

Траверсал ба ҳар гиреҳи дарахт ташриф меорад, то бо он ягон амале анҷом диҳад.

Алгоритм гузариши симметрии рекурсивӣ:

  1. Дар болои кӯдаки чап амал кунед
  2. Бо худ амале кунед
  3. Дар бораи кӯдаки рост амал кунед

Кодекси

    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, рекурсия, фишурдани маълумот ва ғ.)

  • Истифодаи сохторҳо ва алгоритмҳои додаҳо дар ҳаёти воқеӣ

  • Барномасозии барномаҳои Android дар Java

  • Барномасозии веб-барномаҳо дар Java

2 корбар овоз доданд. 1 корбар худдорӣ кард.

Манбаъ: www.habr.com

Илова Эзоҳ