બાઈનરી ટ્રી અથવા બાઈનરી સર્ચ ટ્રી કેવી રીતે તૈયાર કરવી

ફોરપ્લે

આ લેખ દ્વિસંગી શોધ વૃક્ષો વિશે છે. મેં તાજેતરમાં વિશે એક લેખ લખ્યો હતો હફમેન પદ્ધતિ દ્વારા ડેટા કમ્પ્રેશન. ત્યાં મેં ખરેખર દ્વિસંગી વૃક્ષો પર ધ્યાન આપ્યું ન હતું, કારણ કે શોધવાની, દાખલ કરવાની, કાઢી નાખવાની પદ્ધતિઓ સંબંધિત ન હતી. હવે મેં વૃક્ષો વિશે એક લેખ લખવાનું નક્કી કર્યું. કદાચ અમે શરૂ કરીશું.

વૃક્ષ એ એક ડેટા માળખું છે જેમાં ધાર દ્વારા જોડાયેલા ગાંઠોનો સમાવેશ થાય છે. આપણે કહી શકીએ કે વૃક્ષ એ આલેખનો વિશેષ કેસ છે. અહીં એક ઉદાહરણ વૃક્ષ છે:

આ દ્વિસંગી શોધ વૃક્ષ નથી! બધું કટ હેઠળ છે!

પરિભાષા

રુટ

વૃક્ષ મૂળ ટોચનો નોડ છે. ઉદાહરણમાં, આ નોડ A છે. વૃક્ષમાં, ફક્ત એક જ રસ્તો મૂળમાંથી અન્ય નોડ તરફ લઈ જઈ શકે છે! હકીકતમાં, કોઈપણ નોડને આ નોડને અનુરૂપ સબટ્રીના મૂળ તરીકે ગણી શકાય.

માતાપિતા/સંતાન

રુટ સિવાયના તમામ ગાંઠોમાં બરાબર એક ધાર હોય છે જે બીજા નોડ તરફ દોરી જાય છે. વર્તમાન નોડની ઉપરનો નોડ કહેવાય છે પિતૃ આ નોડ. વર્તમાનની નીચે સ્થિત અને તેની સાથે જોડાયેલ નોડ કહેવાય છે વંશજ આ નોડ. ચાલો એક ઉદાહરણ લઈએ. નોડ B લો, પછી તેના માતાપિતા નોડ A હશે, અને તેના બાળકો ગાંઠો 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;
    }
//...остальные методы узла
}

દરેક નોડમાં બે બાળકો હોય છે (તે તદ્દન શક્ય છે કે લેફ્ટ ચાઇલ્ડ અને/અથવા રાઇટ ચાઇલ્ડ બાળકો નલ હશે). તમે કદાચ સમજી ગયા છો કે આ કિસ્સામાં નંબર ડેટા નોડમાં સંગ્રહિત ડેટા છે; કી - નોડ કી.

અમે ગાંઠ શોધી કાઢી છે, હવે ચાલો વૃક્ષો વિશેની સમસ્યાઓ વિશે વાત કરીએ. અહીં અને નીચે, "વૃક્ષ" શબ્દનો અર્થ દ્વિસંગી શોધ વૃક્ષનો ખ્યાલ હશે. દ્વિસંગી વૃક્ષની રચના:

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 તત્વો હોય, તો તેનો અર્થ એ કે વૃક્ષના log(n) આધાર 2 સ્તરો હશે. અને શોધમાં, ચક્રના એક પગલા માટે, તમે એક સ્તર નીચે જાઓ છો.

સામેલ

જો તમે શોધનો સાર સમજી લીધો હોય, તો તમારા માટે નિવેશને સમજવું મુશ્કેલ નહીં હોય. તમારે ફક્ત ઝાડના પાંદડા પર જવાની જરૂર છે (શોધમાં વર્ણવેલ વંશના નિયમો અનુસાર) અને તેના વંશજ બનવાની જરૂર છે - ડાબે અથવા જમણે, કીના આધારે. અમલીકરણ:

   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. નોડને કી 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, રિકર્ઝન, ડેટા કમ્પ્રેશન, વગેરે)

• વાસ્તવિક જીવનમાં ડેટા સ્ટ્રક્ચર્સ અને અલ્ગોરિધમનો ઉપયોગ

• જાવામાં એન્ડ્રોઇડ એપ્લીકેશનનું પ્રોગ્રામિંગ

• જાવા વેબ એપ્લિકેશન પ્રોગ્રામિંગ

2 વપરાશકર્તાઓએ મત ​​આપ્યો. 1 વપરાશકર્તા દૂર રહ્યો.

સ્ત્રોત: www.habr.com