ProHoster > Blog > İdarə > Binary Tree və ya ikili axtarış ağacını necə hazırlamaq olar

Binary Tree və ya ikili axtarış ağacını necə hazırlamaq olar

Müqəddimə

Bu məqalə binar axtarış ağacları haqqındadır. Bu yaxınlarda haqqında bir məqalə yazdım Huffman metodu ilə məlumatların sıxılması. Orada ikili ağaclara həqiqətən əhəmiyyət vermədim, çünki axtarış, daxil etmə, silmə üsulları aktual deyildi. İndi ağaclar haqqında məqalə yazmaq qərarına gəldim. Bəlkə başlayaq.

Ağac kənarlarla birləşdirilmiş qovşaqlardan ibarət məlumat strukturudur. Ağacın qrafikin xüsusi halı olduğunu deyə bilərik. Budur bir nümunə ağac:

Binary Tree və ya ikili axtarış ağacını necə hazırlamaq olar

Bu ikili axtarış ağacı deyil! Hər şey kəsilməkdədir!

Terminologiya

kök

Ağac kökü ən üst düyündür. Nümunədə bu, A qovşağıdır. Ağacda yalnız bir yol kökdən istənilən digər qovşağa apara bilər! Əslində, istənilən qovşağı bu node uyğun gələn alt ağacın kökü hesab etmək olar.

Valideynlər/övladlar

Kökdən başqa bütün qovşaqların başqa bir node aparan tam bir kənarı var. Cari qovşağın üstündəki qovşaq deyilir valideyn bu node. Cari olanın altında yerləşən və ona qoşulmuş bir qovşaq deyilir nəsli bu node. Bir nümunə götürək. B qovşağını götürün, onda onun valideyni A qovşağı, uşaqları isə D, E və F qovşaqları olacaq.

Sheet

Uşağı olmayan bir düyün ağacın yarpağı adlanır. Nümunədə D, E, F, G, I, J, K qovşaqları yarpaq olacaq.

Bu, əsas terminologiyadır. Digər anlayışlar daha sonra müzakirə olunacaq. Beləliklə, ikili ağac, hər düyünün ikidən çox uşağı olmayan bir ağacdır. Təxmin etdiyiniz kimi, nümunədəki ağac ikili olmayacaq, çünki B və H qovşaqlarının ikidən çox uşağı var. Budur ikili ağac nümunəsi:

Binary Tree və ya ikili axtarış ağacını necə hazırlamaq olar

Ağacın düyünlərində istənilən məlumat ola bilər. İkili axtarış ağacı aşağıdakı xüsusiyyətlərə malik olan ikili ağacdır:

  1. Həm sol, həm də sağ alt ağaclar ikili axtarış ağaclarıdır.
  2. İxtiyari X qovşağının sol alt ağacının bütün qovşaqları X nodeunun məlumat açarı dəyərindən az olan məlumat açarı dəyərlərinə malikdir.
  3. İxtiyari X nodeunun sağ alt ağacının bütün qovşaqları, X nodeunun məlumat açarının dəyərindən böyük və ya ona bərabər olan məlumat açarı dəyərlərinə malikdir.

Açar - düyünün bəzi xarakteristikası (məsələn, nömrə). Açar bu açarın uyğun olduğu ağacın elementini tapa bilmək üçün lazımdır. İkili axtarış ağacı nümunəsi:

Binary Tree və ya ikili axtarış ağacını necə hazırlamaq olar

ağac görünüşü

İrəlilədikcə, anlayışınızı yaxşılaşdırmaq üçün bəzi (bəlkə də natamam) kod hissələrini daxil edəcəyəm. Tam kod məqalənin sonunda olacaq.

Ağac düyünlərdən ibarətdir. Düyün quruluşu:

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

Hər qovşağın iki uşağı var (solUşaq və/və ya sağUşaq uşaqlarının null olması olduqca mümkündür). Yəqin başa düşdünüz ki, bu halda nömrə məlumatı qovşaqda saxlanılan məlumatdır; açar - qovşaq açarı.

Düyünü anladıq, indi ağaclarla bağlı aktual problemlərdən danışaq. Bundan sonra "ağac" sözü ikili axtarış ağacı anlayışını ifadə edəcəkdir. İkili ağac quruluşu:

public class BinaryTree<T> {
     private Node<T> root;

    //методы дерева
}

Sinif sahəsi olaraq bizə yalnız ağacın kökü lazımdır, çünki kökdən getLeftChild() və getRightChild() metodlarından istifadə edərək ağacın istənilən qovşağına gedə bilərsiniz.

Ağac alqoritmləri

Axtar

Tutaq ki, bir ağacınız var. Açar açarı olan elementi necə tapmaq olar? Ardıcıl olaraq kökdən ağacın aşağısına doğru hərəkət etməli və açarın dəyərini növbəti qovşağın açarı ilə müqayisə etməlisiniz: əgər açar növbəti qovşağın açarından azdırsa, onda qovşağın sol nəslinə keçin, əgər çox olarsa - sağda, düymələr bərabərdirsə - istədiyiniz node tapıldı! Müvafiq kod:

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;
}

Əgər cərəyan sıfır olarsa, deməli iterasiya ağacın sonuna çatmışdır (konseptual səviyyədə siz ağacda mövcud olmayan yerdəsiniz - yarpaq uşağı).

Balanslaşdırılmış bir ağacda (qovşaqların daha çox və ya daha az bərabər paylandığı bir ağac) axtarış alqoritminin səmərəliliyini nəzərdən keçirin. Onda axtarış səmərəliliyi O(log(n)) və baza 2 loqarifm olacaq Bax: əgər balanslaşdırılmış ağacda n element varsa, bu o deməkdir ki, ağacın log(n) baza 2 səviyyəsi olacaq. Axtarışda isə dövrün bir addımı üçün bir pillə aşağı düşürsən.

daxil

Əgər axtarışın mahiyyətini dərk etmisinizsə, o zaman əlavəni başa düşmək sizin üçün çətin olmayacaq. Yalnız ağacın yarpağına enmək lazımdır (axtarışda təsvir edilən eniş qaydalarına uyğun olaraq) və onun nəslinə çevrilmək lazımdır - açardan asılı olaraq sola və ya sağa. İcra:

   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;
                    }
                }
            }
        }
    }

Bu halda, cari node ilə yanaşı, cari node ana haqqında məlumat saxlamaq lazımdır. Cari sıfır olduqda, əsas dəyişən bizə lazım olan vərəqi ehtiva edəcəkdir.
Daxiletmə səmərəliliyi, şübhəsiz ki, axtarışın effektivliyi ilə eyni olacaq - O(log(n)).

Removal

Silinmə bir ağacla edilməli olan ən mürəkkəb əməliyyatdır. Aydındır ki, əvvəlcə aradan qaldıracağımız elementi tapmaq lazımdır. Amma sonra nə? Sadəcə olaraq onun istinadını null olaraq təyin etsək, o zaman kökü bu node olan alt ağac haqqında məlumatı itirəcəyik. Ağacların çıxarılması üsulları üç halda bölünür.

Birinci hal. Silinəcək node uşaqları yoxdur.

Əgər silinəcək node uşaqları yoxdursa, bu, yarpaqdır. Buna görə də, siz sadəcə olaraq onun valideyninin leftChild və ya rightChild sahələrini null olaraq təyin edə bilərsiniz.

İkinci hal. Silinəcək node bir uşaq var

Bu iş də çox çətin deyil. Nümunəmizə qayıdaq. Tutaq ki, biz 14 açarı olan elementi silməliyik. Razılaşın ki, o, 10 açarı olan qovşağın sağ uşağı olduğundan, onun nəslindən hər hansı birinin (bu halda, sağda) 10-dan böyük açarı olacaq, ona görə də siz onu ağacdan asanlıqla "kəsmək" olar və valideyni birbaşa silinən düyünün uşağına bağlaya bilər, yəni. qovşağı 10 açarı ilə 13-cü qovşaqla birləşdirin. Əgər biz onun valideyninin sol uşağı olan qovşağı silməli olsaq, vəziyyət oxşar olardı. Bu barədə özünüz düşünün - dəqiq bir bənzətmə.

Üçüncü hal. Node-nin iki övladı var

Ən çətin hal. Gəlin yeni bir nümunəyə nəzər salaq.

Binary Tree və ya ikili axtarış ağacını necə hazırlamaq olar

Varisi axtarın

Tutaq ki, 25-ci açarla düyünü çıxarmaq lazımdır. Onun yerinə kimi qoyaq? Onun ardıcıllarından biri (nəslinin nəsli və ya nəsli) olmalıdır varisi(çıxarılmış düyünün yerini tutacaq).

Varisi kimin olması lazım olduğunu necə bilirsiniz? İntuitiv olaraq bu, ağacın açarı çıxarılan qovşaqdan sonrakı ən böyüyü olan qovşaqdır. Alqoritm aşağıdakı kimidir. Onun sağ uşağına getmək lazımdır (həmişə sağa, çünki varisin açarının silinən düyünün açarından böyük olduğu deyilirdi) və sonra bu hüququn sol uşaqlarının zəncirindən keçmək lazımdır. uşaq. Nümunədə, biz 35 açarı olan düyünə getməliyik və sonra onun sol uşaqlarının zəncirindən yarpağa enməliyik - bu halda, bu zəncir yalnız 30 açarı olan qovşaqdan ibarətdir. Düzünü desək, biz axtarırıq arzu olunan qovşaqdan böyük olan qovşaqlar dəstindəki ən kiçik node.

Binary Tree və ya ikili axtarış ağacını necə hazırlamaq olar

Xələf axtarış metodunun kodu:

    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;
    }

Silinmə metodunun tam kodu:

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;
    }

Mürəkkəblik O(log(n))-a yaxınlaşdırıla bilər.

Ağacda maksimum/minimumu tapmaq

Aydındır ki, ağacda minimum / maksimum dəyəri necə tapmaq olar - ardıcıl olaraq ağacın sol / sağ elementlərinin zəncirindən keçmək lazımdır; yarpağa çatdığınız zaman minimum/maksimum element olacaq.

    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;
    }

Mürəkkəblik - O(log(n))

Simmetrik bypass

Traversal, ağacın hər düyününə onunla bir şey etmək üçün ziyarətdir.

Rekursiv simmetrik keçid alqoritmi:

  1. Sol uşağa bir hərəkət edin
  2. Özünüzlə bir hərəkət edin
  3. Düzgün uşağa bir hərəkət edin

Kodu:

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
            inOrder(current.getRightChild());
        }
    }

Nəticə

Nəhayət! Əgər bir şeyi izah etməmişəmsə və ya şərhim varsa, şərhlərdə gözləyirəm. Söz verdiyimiz kimi, tam kod buradadır.

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)-a degenerasiya

Yəqin ki, bir çoxlarınız fikirləşmisiniz: ağacın tarazlığını itirsəniz nə olacaq? Məsələn, artan düymələri olan ağaca qovşaqları qoyun: 1,2,3,4,5,6... Onda ağac bir qədər əlaqəli siyahını xatırladacaq. Bəli, ağac öz ağac strukturunu itirəcək və buna görə də məlumat əldə etmək səmərəliliyi azalacaq. Axtarış, daxiletmə və silmə əməliyyatlarının mürəkkəbliyi əlaqəli siyahı ilə eyni olacaq: O(n). Bu, mənim fikrimcə, ikili ağacların ən vacib çatışmazlıqlarından biridir.

Sorğuda yalnız qeydiyyatdan keçmiş istifadəçilər iştirak edə bilər. Daxil olunxahiş edirəm.

Mən uzun müddətdir Habré-də deyiləm və bilmək istərdim ki, hansı mövzularda hansı məqalələri daha çox görmək istərdiniz?

  • Məlumat strukturları

  • Alqoritmlər (DP, rekursiya, məlumatların sıxılması və s.)

  • Məlumat strukturlarının və alqoritmlərin real həyatda tətbiqi

  • Java-da android proqramların proqramlaşdırılması

  • Java Veb Tətbiqi Proqramlaşdırması

2 istifadəçi səs verdi. 1 istifadəçi bitərəf qaldı.

Mənbə: www.habr.com

Добавить комментарий