ProHoster > Dienoraštis > Administravimas > Dvejetainis medis arba kaip parengti dvejetainį paieškos medį

Dvejetainis medis arba kaip parengti dvejetainį paieškos medį

Įžanga

Šis straipsnis yra apie dvejetainės paieškos medžius. Neseniai parašiau straipsnį apie duomenų suspaudimas naudojant Huffman metodą. Ten aš nekreipiau daug dėmesio į dvejetainius medžius, nes paieškos, įterpimo ir trynimo metodai nebuvo svarbūs. Dabar nusprendžiau parašyti straipsnį apie medžius. Pradėkime.

Medis yra duomenų struktūra, susidedanti iš mazgų, sujungtų briaunomis. Galima sakyti, kad medis yra ypatingas grafiko atvejis. Štai medžio pavyzdys:

Dvejetainis medis arba kaip parengti dvejetainį paieškos medį

Tai nėra dvejetainis paieškos medis! Viskas supjaustoma!

terminologija

šaknis

Medžio šaknis - tai aukščiausias jo mazgas. Pavyzdyje tai mazgas A. Medyje tik vienas kelias gali nuvesti nuo šaknies į bet kurį kitą mazgą! Tiesą sakant, bet kuris mazgas gali būti laikomas pomedžio, atitinkančio šį mazgą, šaknimi.

Tėvai / palikuonys

Visi mazgai, išskyrus šaknį, turi tiksliai vieną kraštą, vedantį į kitą mazgą. Vadinamas mazgas, esantis virš dabartinio tėvas šis mazgas. Vadinamas mazgas, esantis žemiau dabartinio ir prijungtas prie jo palikuonis šis mazgas. Panaudokime pavyzdį. Paimkime mazgą B, tada jo pirminis mazgas bus A, o jo vaikai bus mazgai D, E ir F.

Lapas

Mazgas, kuris neturi vaikų, bus vadinamas medžio lapu. Pavyzdyje lapai bus mazgai D, E, F, G, I, J, K.

Tai yra pagrindinė terminija. Kitos sąvokos bus aptariamos toliau. Taigi, dvejetainis medis yra medis, kuriame kiekvienas mazgas turės ne daugiau kaip du vaikus. Kaip atspėjote, pavyzdžio medis nebus dvejetainis, nes mazgai B ir H turi daugiau nei du vaikus. Štai dvejetainio medžio pavyzdys:

Dvejetainis medis arba kaip parengti dvejetainį paieškos medį

Medžio mazguose gali būti bet kokios informacijos. Dvejetainis paieškos medis yra dvejetainis medis, turintis šias savybes:

  1. Ir kairysis, ir dešinysis pomedžiai yra dvejetainiai paieškos medžiai.
  2. Visi savavališko mazgo X kairiojo pomedžio mazgai turi mažesnes duomenų raktų reikšmes nei paties mazgo X duomenų rakto reikšmė.
  3. Visi mazgai, esantys savavališko mazgo X dešiniajame pomedyje, turi duomenų rakto reikšmes, didesnes arba lygias paties mazgo X duomenų rakto reikšmei.

Raktas — bet kuri mazgo charakteristika (pavyzdžiui, skaičius). Raktas reikalingas, kad galėtumėte rasti medžio elementą, kurį atitinka šis raktas. Dvejetainės paieškos medžio pavyzdys:

Dvejetainis medis arba kaip parengti dvejetainį paieškos medį

Medžio vaizdas

Tobulėjant pateiksiu keletą (galbūt neišsamių) kodo dalių, kad geriau suprastumėte. Visas kodas bus straipsnio pabaigoje.

Medis susideda iš mazgų. Mazgo struktūra:

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

Kiekvienas mazgas turi du antrinius (visiškai įmanoma, kad leftChild ir (arba) dešinės vaiko vaikai turės nulinę reikšmę). Tikriausiai supratote, kad šiuo atveju skaičiaus duomenys yra mazge saugomi duomenys; raktas - mazgo raktas.

Sutvarkėme mazgą, o dabar pakalbėkime apie aktualias problemas dėl medžių. Toliau žodžiu „medis“ turėsiu galvoje dvejetainio paieškos medžio sąvoką. Dvejetainė medžio struktūra:

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

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

Mums reikia tik medžio šaknies kaip klasės lauko, nes iš šaknies, naudodami getLeftChild() ir getRightChild() metodus, galite patekti į bet kurį medžio mazgą.

Algoritmai medyje

Paieška

Tarkime, kad turite pastatytą medį. Kaip rasti elementą su rakto raktu? Turite nuosekliai pereiti nuo šaknies į medį ir palyginti rakto reikšmę su kito mazgo raktu: jei raktas yra mažesnis už kito mazgo raktą, tada eikite į kairįjį mazgo palikuonį, jei jis yra didesnis, į dešinįjį, jei raktai lygūs, norimas mazgas randamas! Atitinkamas kodas:

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

Jei srovė tampa nuline, vadinasi, paieška pasiekė medžio pabaigą (koncepciniu lygmeniu jūs esate neegzistuojančioje medžio vietoje – lapo palikuonyje).

Panagrinėkime paieškos algoritmo efektyvumą subalansuotame medyje (medyje, kuriame mazgai pasiskirstę daugiau ar mažiau tolygiai). Tada paieškos efektyvumas bus O(log(n)), o logaritmas – 2 bazė. Pažiūrėkite: jei subalansuotame medyje yra n elementų, tai reiškia, kad bus log(n) iki 2 bazinių lygių. medis. O paieškoje vienu ciklo žingsniu nusileidžiate vienu lygiu žemyn.

įterpti

Jei suvoksite paieškos esmę, suprasti įterpimą jums nebus sunku. Jums tereikia nusileisti prie medžio lapo (pagal paieškoje aprašytas nusileidimo taisykles) ir tapti jo palikuonimi – kairėje arba dešinėje, priklausomai nuo rakto. Įgyvendinimas:

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

Šiuo atveju, be dabartinio mazgo, būtina saugoti informaciją apie dabartinio mazgo pirminį elementą. Kai srovė tampa lygi nuliui, pirminiame kintamajame bus mums reikalingas lapas.
Akivaizdu, kad įterpimo efektyvumas bus toks pat kaip ir paieškos – O(log(n)).

Šalinimas

Pašalinimas yra pati sunkiausia operacija, kurią reikės atlikti su medžiu. Akivaizdu, kad pirmiausia turėsime rasti elementą, kurį ketiname ištrinti. Bet kas tada? Jei tiesiog nustatysime jo nuorodą į nulį, prarasime informaciją apie pomedį, kurio šaknis yra šis mazgas. Medžių šalinimo būdai skirstomi į tris atvejus.

Pirmas atvejis. Ištrinamas mazgas neturi vaikų

Jei ištrinamas mazgas neturi vaikų, tai reiškia, kad tai yra lapas. Todėl galite tiesiog nustatyti jo pirminio lauko leftChild arba rightChild į nulį.

Antras atvejis. Trintinas mazgas turi vieną antrį

Šis atvejis taip pat nėra labai sudėtingas. Grįžkime prie mūsų pavyzdžio. Tarkime, kad turime ištrinti elementą su raktu 14. Sutikite, kad kadangi tai yra dešinysis mazgo, kurio raktas 10, palikuonis, bet kurio jo palikuonio (šiuo atveju dešiniojo) raktas bus didesnis nei 10, todėl jūs gali nesunkiai jį „iškirpti“ iš medžio, o tėvą tiesiogiai prijungti prie ištrinamo mazgo vaiko, t.y. sujunkite mazgą su raktu 10 su mazgu 13. Situacija būtų panaši, jei reikėtų ištrinti mazgą, kuris yra kairysis jo pirminio antrinis vaikas. Pagalvokite patys – tiksli analogija.

Trečias atvejis. Mazgas turi du vaikus

Sunkiausias atvejis. Pažvelkime į naują pavyzdį.

Dvejetainis medis arba kaip parengti dvejetainį paieškos medį

Ieškokite įpėdinio

Tarkime, kad reikia ištrinti mazgą su raktu 25. Ką turėtume įdėti į jo vietą? Turi tapti vienu iš jo pasekėjų (palikuonių ar palikuonių palikuonių). įpėdinis(tas, kuris užims pašalinamo mazgo vietą).

Kaip suprasti, kas turėtų tapti įpėdiniu? Intuityviai tai yra medžio mazgas, kurio raktas yra antras pagal dydį iš ištrinamo mazgo. Algoritmas yra toks. Turite pereiti prie jo dešiniojo palikuonio (visada į dešinįjį, nes jau buvo pasakyta, kad įpėdinis raktas yra didesnis nei ištrinamo mazgo raktas), o tada pereiti per šio dešiniojo palikuonio kairiųjų palikuonių grandinę. . Pavyzdyje mes eitume į mazgą su raktu 35, o tada nusileisime į lapą per jo kairiųjų vaikų grandinę – šiuo atveju šią grandinę sudaro tik mazgas su raktu 30. Griežtai kalbant, mes ieškome mažiausiam mazgui mazgų aibėje, didesniam nei tas mazgas, kurio ieškome.

Dvejetainis medis arba kaip parengti dvejetainį paieškos medį

Įpėdinio paieškos metodo kodas:

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

Visas ištrynimo metodo kodas:

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

Sudėtingumas gali būti aproksimuotas iki O(log(n)).

Medyje rasti maksimumą/minimumą

Akivaizdu, kaip medyje rasti mažiausią/maksimalią reikšmę – reikia nuosekliai judėti atitinkamai kairiųjų/dešinių elementų grandine; kai pateksite į lapą, tai bus minimalus/maksimalus elementas.

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

Sudėtingumas – O(log(n))

Simetrinis aplinkkelis

„Traversal“ aplanko kiekvieną medžio mazgą, kad galėtų su juo atlikti tam tikrus veiksmus.

Rekursyvus simetriškas važiavimo algoritmas:

  1. Atlikite veiksmą su kairiuoju vaiku
  2. Atlikite veiksmą su savimi
  3. Atlikite veiksmą tinkamam vaikui

Kodas:

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

išvada

Pagaliau! Jei nieko nepaaiškinau ar turiu pastabų, palikite juos komentaruose. Kaip ir žadėjau, pateikiu visą kodą.

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

Degeneracija iki O(n)

Daugelis iš jūsų tikriausiai pastebėjo: ką daryti, jei padarysite medį nesubalansuotą? Pavyzdžiui, į medį įdėkite mazgus su didėjančiais raktais: 1,2,3,4,5,6... Tada medis šiek tiek primins susietą sąrašą. Ir taip, medis praras savo medžio struktūrą, taigi ir duomenų prieigos efektyvumą. Paieškos, įterpimo ir ištrynimo operacijų sudėtingumas taps toks pat kaip ir susieto sąrašo: O(n). Tai vienas iš svarbiausių, mano nuomone, dvinarių medžių trūkumų.

Apklausoje gali dalyvauti tik registruoti vartotojai. Prisijungti, Prašau.

Labai ilgai nebuvau centre ir norėčiau sužinoti, kokių straipsnių kokiomis temomis norėtumėte pamatyti daugiau?

  • Duomenų struktūros

  • Algoritmai (DP, rekursija, duomenų glaudinimas ir kt.)

  • Duomenų struktūrų ir algoritmų taikymas realiame gyvenime

  • Android programų programavimas Java

  • Interneto programų programavimas Java kalba

Balsavo 2 vartotojai. 1 vartotojas susilaikė.

Šaltinis: www.habr.com

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