🥇Бинардык дарак же бинардык издөө дарагын кантип даярдоо керек

башталышы

Бул макалада бинардык издөө дарактары жөнүндө. Мен жакында эле макала жаздым Хаффман ыкмасын колдонуу менен маалыматтарды кысуу. Ал жерде мен бинардык дарактарга көп көңүл бурган жокмун, анткени издөө, киргизүү жана жок кылуу ыкмалары тиешелүү эмес. Эми мен дарактар жөнүндө макала жазууну чечтим. Келиңиз баштайлы.

Дарак - бул четтери менен байланышкан түйүндөрдөн турган маалымат структурасы. Даракты графиктин өзгөчө учуру деп айта алабыз. Бул жерде мисал дарак болуп саналат:

Бул бинардык издөө дарагы эмес! Баары кесилген!

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

тамыр

Дарактын тамыры - бул анын эң жогорку түйүнү. Мисалда бул А түйүнү. Даракта тамырдан башка түйүнгө бир гана жол алып барышы мүмкүн! Чындыгында, ар кандай түйүн ушул түйүнгө туура келген ички дарактын тамыры катары каралышы мүмкүн.

Ата-энелер/тукумдар

Тамырдан башка бардык түйүндөр башка түйүнгө алып баруучу так бир четине ээ. Учурдагыдан жогору жайгашкан түйүн деп аталат ата-эне бул түйүн. Учурдагыдан төмөн жайгашкан жана ага туташкан түйүн деп аталат тукуму бул түйүн. Келгиле, мисал келтирели. В түйүнүн алалы, анда анын ата-энеси А түйүнү, ал эми анын балдары 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;
    }
//...остальные методы узла
}

Ар бир түйүндө эки бала бар (lecChild жана/же 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

Binary Tree же бинардык издөө дарагын кантип даярдоо керек