ProHoster > блог > Администрација > Бинарно стебло или како да подготвите бинарно дрво за пребарување

Бинарно стебло или како да подготвите бинарно дрво за пребарување

Прелудиум

Оваа статија е за бинарни стебла за пребарување. Неодамна направив статија за компресија на податоци со помош на методот Хафман. Таму не обрнував многу внимание на бинарните дрвја, бидејќи методите за пребарување, вметнување и бришење не беа релевантни. Сега решив да напишам статија за дрвјата. Ајде да почнеме.

Дрвото е податочна структура која се состои од јазли поврзани со рабови. Можеме да кажеме дека дрвото е посебен случај на график. Еве пример дрво:

Бинарно стебло или како да подготвите бинарно дрво за пребарување

Ова не е бинарно дрво за пребарување! Сè е исечено!

Терминологија

Root

Корен од дрво - ова е нејзиниот највисок јазол. Во примерот, ова е јазол А. Во дрво, само една патека може да води од коренот до кој било друг јазол! Всушност, секој јазол може да се смета како корен на поддрвото што одговара на овој јазол.

Родители/потомци

Сите јазли освен коренот имаат точно еден раб што води до друг јазол. Јазолот кој се наоѓа над тековниот се нарекува родител овој јазол. Се нарекува јазол кој се наоѓа под тековниот и е поврзан со него потомок овој јазол. Ајде да користиме пример. Да го земеме јазолот Б, тогаш неговиот родител ќе биде јазолот А, а неговите деца ќе бидат јазлите 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)).

Бришење

Отстранувањето е најтешката операција што ќе треба да се изврши на дрво. Јасно е дека прво ќе треба да го најдеме елементот што ќе го избришеме. Но, што тогаш? Ако едноставно ја поставиме нејзината референца на null, ќе изгубиме информации за поддрвото чиј корен е овој јазол. Методите за отстранување на дрвјата се поделени во три случаи.

Прв случај. Јазолот што се брише нема деца

Ако јазолот што се брише нема деца, тогаш тоа значи дека е лист. Затоа, можете едноставно да ги поставите полето 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))

Симетричен бајпас

Траверзал го посетува секој јазол на дрвото со цел да направи некоја акција со него.

Рекурзивен алгоритам за симетрично поминување:

  1. Направете акција на левото дете
  2. Направете акција со себе
  3. Направете акција за вистинското дете

Код:

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

Заклучок

Конечно! Ако не сум објаснил ништо или имам коментари, ве молиме оставете ги во коментарите. Како што ветив, го давам целосниот код.

Јазол.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, рекурзија, компресија на податоци, итн.)

  • Примена на структури на податоци и алгоритми во реалниот живот

  • Програмирање на апликации за Android во Java

  • Програмирање веб-апликации во Java

Гласале 2 корисници. 1 корисник се воздржаа.

Извор: www.habr.com

Додадете коментар