🥇Binary Tree හෝ ද්විමය සෙවුම් ගසක් සකස් කරන්නේ කෙසේද

Foreplay

මෙම ලිපිය ද්විමය සෙවුම් ගස් ගැන වේ. මම මෑතකදී ලිපියක් කළා හෆ්මන් ක්‍රමය භාවිතා කරමින් දත්ත සම්පීඩනය. එහිදී මම ද්විමය ගස් කෙරෙහි වැඩි අවධානයක් යොමු කළේ නැත, මන්ද සෙවීම, ඇතුළත් කිරීම සහ මකා දැමීමේ ක්‍රම අදාළ නොවේ. දැන් මම ගස් ගැන ලිපියක් ලියන්න තීරණය කළා. අපි පටන් ගනිමු.

ගසක් යනු දාර මගින් සම්බන්ධ කර ඇති නෝඩ් වලින් සමන්විත දත්ත ව්‍යුහයකි. ගසක් යනු ප්‍රස්ථාරයක විශේෂ අවස්ථාවක් බව අපට පැවසිය හැකිය. මෙන්න උදාහරණයක් ගසක්:

මෙය ද්විමය සෙවුම් ගසක් නොවේ! සියල්ල කපා ඇත!

පාරිභාෂිතය

මූල

ගස් මුල - මෙය එහි ඉහළම නෝඩයයි. උදාහරණයේ, මෙය නෝඩය A. ගසක, මූලයේ සිට වෙනත් ඕනෑම නෝඩයකට ගෙන යා හැක්කේ එක් මාර්ගයකට පමණි! ඇත්ත වශයෙන්ම, ඕනෑම නෝඩයක් මෙම නෝඩයට අනුරූප වන උප වෘක්ෂයේ මූලය ලෙස සැලකිය හැකිය.

දෙමාපියන් / පැවත එන්නන්

මූල හැර අනෙකුත් සියලුම නෝඩ වලට හරියටම එක් දාරයක් තවත් නෝඩයකට යොමු වේ. වත්මන් එකට ඉහළින් පිහිටා ඇති නෝඩය ලෙස හැඳින්වේ දෙමාපියන් මෙම නෝඩය. වත්මන් එකට පහළින් පිහිටා ඇති සහ එයට සම්බන්ධ වූ නෝඩයක් ලෙස හැඳින්වේ වංශයෙන් පැවතෙන්නා මෙම නෝඩය. අපි උදාහරණයක් භාවිතා කරමු. අපි නෝඩය B ගනිමු, එවිට එහි මාපිය node A වන අතර එහි දරුවන් D, E සහ F යන නෝඩ් වේ.

කොළ

දරුවන් නොමැති නෝඩයක් ගසේ කොළයක් ලෙස හැඳින්වේ. උදාහරණයේ දී, කොළ D, E, F, G, I, J, K නෝඩ් වනු ඇත.

මෙය මූලික පාරිභාෂිතයයි. අනෙකුත් සංකල්ප තවදුරටත් සාකච්ඡා කරනු ඇත. ඉතින්, ද්විමය ගසක් යනු සෑම නෝඩයකටම දරුවන් දෙදෙනෙකුට වඩා නොසිටින ගසකි. ඔබ අනුමාන කළ පරිදි, උදාහරණයෙන් ගස ද්විමය නොවනු ඇත, මන්ද බී සහ එච් නෝඩ් වලට දරුවන් දෙදෙනෙකුට වඩා වැඩිය. ද්විමය ගසක උදාහරණයක් මෙන්න:

ගස් නෝඩ් ඕනෑම තොරතුරක් අඩංගු විය හැක. ද්විමය සෙවුම් ගසක් යනු පහත ගුණාංග ඇති ද්විමය ගසකි:

වම් සහ දකුණු උප වෘක්ෂ දෙකම ද්විමය සෙවුම් ගස් වේ.
අත්තනෝමතික නෝඩ් X හි වම් උප වෘක්ෂයේ සියලුම නෝඩ් වල දත්ත යතුරු අගයන් X node හි දත්ත යතුරේ අගයට වඩා අඩුය.
අත්තනෝමතික නෝඩය X හි දකුණු උප වෘක්ෂයේ ඇති සියලුම නෝඩ් වල දත්ත යතුරු අගයන් X node හි දත්ත යතුරේ අගයට වඩා වැඩි හෝ සමාන වේ.

ප්රධාන - නෝඩයේ ඕනෑම ලක්ෂණයක් (උදාහරණයක් ලෙස, අංකයක්). යතුර අවශ්‍ය වන අතර එමඟින් ඔබට මෙම යතුර අනුරූප වන ගස් මූලද්‍රව්‍යය සොයාගත හැකිය. ද්විමය සෙවුම් ගසක උදාහරණය:

ගස් දර්ශනය

අපි ඉදිරියට යන විට, ඔබේ අවබෝධය වැඩිදියුණු කිරීම සඳහා මම (සමහරවිට අසම්පූර්ණ) කේත කොටස් කිහිපයක් ලබා දෙන්නෙමි. සම්පූර්ණ කේතය ලිපියේ අවසානයේ ඇත.

ගසක් නෝඩ් වලින් සමන්විත වේ. නෝඩ් ව්යුහය:

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;
    }
//...остальные методы узла
}

සෑම නෝඩයකටම දරුවන් දෙදෙනෙක් සිටී (වම් දරුවා සහ/හෝ දකුණේ ළමුන්ගේ ශුන්‍ය අගයක් අඩංගු විය හැක). මෙම අවස්ථාවේදී සංඛ්‍යා දත්ත යනු නෝඩයේ ගබඩා කර ඇති දත්ත බව ඔබ බොහෝ විට තේරුම් ගෙන ඇත; යතුර - නෝඩ් යතුර.

අපි ගැටය නිරාකරණය කර ඇත්තෙමු, දැන් අපි ගස් පිළිබඳ ගැටළු ගැන කතා කරමු. මෙතැන් සිට, "ගස" යන වචනයෙන් මම ද්විමය සෙවුම් ගසක් පිළිබඳ සංකල්පය අදහස් කරමි. ද්විමය ගස් ව්යුහය:

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)).

මකන්න

ඉවත් කිරීම යනු ගසක් මත සිදු කළ යුතු වඩාත්ම දුෂ්කර මෙහෙයුමයි. මුලින්ම අපි මකා දැමීමට යන මූලද්රව්යය සොයා ගැනීමට අවශ්ය බව පැහැදිලිය. නමුත් එසේ නම්? අපි එහි යොමුව ශුන්‍ය ලෙස සකසන්නේ නම්, මෙම නෝඩය මූලය වන උප වෘක්ෂය පිළිබඳ තොරතුරු අපට අහිමි වනු ඇත. ගස් ඉවත් කිරීමේ ක්රම අවස්ථා තුනකට බෙදා ඇත.

පළමු නඩුව. මකා දමන නෝඩයට දරුවන් නොමැත

මකා දැමූ නෝඩයට දරුවන් නොමැති නම්, මෙයින් අදහස් කරන්නේ එය කොළයක් බවයි. එමනිසා, ඔබට එහි මාපියන්ගේ වම් ළමා හෝ දකුණු ළමා ක්ෂේත්‍ර ශුන්‍ය ලෙස සැකසිය හැක.

දෙවන නඩුව. මකා දැමිය යුතු නෝඩයේ එක් දරුවෙකු සිටී

මෙම නඩුව ද ඉතා සංකීර්ණ නොවේ. අපි අපේ උදාහරණයට නැවත යමු. යතුර 14 සහිත මූලද්‍රව්‍යයක් මකා දැමිය යුතු යැයි සිතමු. එය 10 යතුර සහිත නෝඩයක නිවැරදි පැවත එන බැවින්, එහි පැවත එන ඕනෑම කෙනෙකුට (මෙම අවස්ථාවෙහි හරි එක) 10 ට වඩා වැඩි යතුරක් ඇති බවට එකඟ වන්න, එබැවින් ඔබට එය පහසුවෙන් ගසෙන් "කපා" කළ හැකි අතර, මකා දමන නෝඩයේ දරුවා වෙත මාපියන් සෘජුවම සම්බන්ධ කරන්න, i.e. නෝඩය යතුර 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());
        }
    }
}

ප්රාදේශීය සභා

O(n) දක්වා පරිහානිය

ඔබගෙන් බොහෝ දෙනෙක් දැක ඇති: ඔබ ගස අසමතුලිත කළහොත් කුමක් කළ යුතුද? උදාහරණයක් ලෙස, ගසක වැඩිවන යතුරු සහිත නෝඩ් දමන්න: 1,2,3,4,5,6... එවිට ගස සම්බන්ධිත ලැයිස්තුවකට තරමක් සමාන වනු ඇත. ඔව්, ගසට එහි ගස් ව්‍යුහය අහිමි වනු ඇත, එබැවින් දත්ත ප්‍රවේශයේ කාර්යක්ෂමතාව. සෙවීම්, ඇතුළත් කිරීම් සහ මකාදැමීමේ මෙහෙයුම් වල සංකීර්ණත්වය සම්බන්ධිත ලැයිස්තුවක මෙන් ම වනු ඇත: O(n). මෙය වඩාත් වැදගත් එකකි, මගේ මතය අනුව, ද්විමය ගස්වල අවාසි.

සමීක්ෂණයට සහභාගී විය හැක්කේ ලියාපදිංචි පරිශීලකයින්ට පමණි. පුරන්නකරුණාකර.

මම දිගු කලක් කේන්ද්‍රස්ථානයේ නොසිටි අතර, ඔබ වැඩිපුර දැකීමට කැමති මාතෘකා මොනවාදැයි දැන ගැනීමට මම කැමතියි.

දත්ත ව්යුහයන්
ඇල්ගොරිතම (DP, පුනරාවර්තනය, දත්ත සම්පීඩනය, ආදිය)
සැබෑ ජීවිතයේ දත්ත ව්‍යුහයන් සහ ඇල්ගොරිතම යෙදීම
ජාවා හි ඇන්ඩ්‍රොයිඩ් යෙදුම් ක්‍රමලේඛනය කිරීම
ජාවා හි වෙබ් යෙදුම් ක්‍රමලේඛනය කිරීම

පරිශීලකයින් 2 දෙනෙක් ඡන්දය දුන්හ. 1 පරිශීලකයෙක් වැළකී සිටියේය.

මූලාශ්රය: www.habr.com

ද්විමය ගස හෝ ද්විමය සෙවුම් ගසක් සකස් කරන්නේ කෙසේද

Foreplay

පාරිභාෂිතය

මූල

දෙමාපියන් / පැවත එන්නන්

කොළ

ගස් දර්ශනය

ගසක ඇල්ගොරිතම

Поиск

ඇතුලත් කරන්න

මකන්න

පළමු නඩුව. මකා දමන නෝඩයට දරුවන් නොමැත

දෙවන නඩුව. මකා දැමිය යුතු නෝඩයේ එක් දරුවෙකු සිටී

තුන්වන නඩුව. නෝඩ් එකකට ළමයි දෙන්නෙක් ඉන්නවා

අනුප්‍රාප්තිකයෙකු සොයන්න

ගසක උපරිම/අවම සොයා ගැනීම

සමමිතික බයිපාස්

නිගමනය

ප්රාදේශීය සභා

O(n) දක්වා පරිහානිය

මම දිගු කලක් කේන්ද්‍රස්ථානයේ නොසිටි අතර, ඔබ වැඩිපුර දැකීමට කැමති මාතෘකා මොනවාදැයි දැන ගැනීමට මම කැමතියි.

අදහස් එක් කරන්න

ද්විමය ගස හෝ ද්විමය සෙවුම් ගසක් සකස් කරන්නේ කෙසේද

Foreplay

පාරිභාෂිතය

මූල

දෙමාපියන් / පැවත එන්නන්

කොළ

ගස් දර්ශනය

ගසක ඇල්ගොරිතම

Поиск

ඇතුලත් කරන්න

මකන්න

පළමු නඩුව. මකා දමන නෝඩයට දරුවන් නොමැත

දෙවන නඩුව. මකා දැමිය යුතු නෝඩයේ එක් දරුවෙකු සිටී

තුන්වන නඩුව. නෝඩ් එකකට ළමයි දෙන්නෙක් ඉන්නවා

අනුප්‍රාප්තිකයෙකු සොයන්න

ගසක උපරිම/අවම සොයා ගැනීම

සමමිතික බයිපාස්

නිගමනය

ප්රාදේශීය සභා

O(n) දක්වා පරිහානිය

මම දිගු කලක් කේන්ද්‍රස්ථානයේ නොසිටි අතර, ඔබ වැඩිපුර දැකීමට කැමති මාතෘකා මොනවාදැයි දැන ගැනීමට මම කැමතියි.

අදහස් එක් කරන්න ඊ-මේල් මගින් පිලිතුරු දෙන්න අවලංගු

අදහස් එක් කරන්න