🥇ორობითი ხე ან როგორ მოვამზადოთ ორობითი საძიებო ხე

პრელუდია

ეს სტატია ეხება ბინარული საძიებო ხეებს. მე ცოტა ხნის წინ დავწერე სტატია ამის შესახებ მონაცემთა შეკუმშვა ჰაფმანის მეთოდით. იქ ბინარულ ხეებს ნამდვილად არ მიმიქცევია ყურადღება, რადგან ძიების, ჩასმის, წაშლის მეთოდები არ იყო აქტუალური. ახლა გადავწყვიტე დამეწერა სტატია ხეების შესახებ. ალბათ ჩვენ დავიწყებთ.

ხე არის მონაცემთა სტრუქტურა, რომელიც შედგება კიდეებით დაკავშირებული კვანძებისგან. შეგვიძლია ვთქვათ, რომ ხე არის გრაფიკის განსაკუთრებული შემთხვევა. აქ არის მაგალითი ხე:

ეს არ არის ორობითი საძიებო ხე! ყველაფერი ჭრის ქვეშაა!

ტერმინოლოგია

root

ხის ფესვი არის ყველაზე მაღალი კვანძი. მაგალითში ეს არის A კვანძი. ხეში მხოლოდ ერთ გზას შეუძლია ფესვიდან ნებისმიერ სხვა კვანძამდე მიიყვანოს! სინამდვილეში, ნებისმიერი კვანძი შეიძლება ჩაითვალოს ამ კვანძის შესაბამისი ქვეხის ფესვად.

მშობლები/შთამომავლები

ფესვის გარდა ყველა კვანძს აქვს ზუსტად ერთი კიდე, რომელიც მიდის მეორე კვანძამდე. მიმდინარე კვანძის ზემოთ მდებარე კვანძს ეწოდება მშობელი ეს კვანძი. კვანძს, რომელიც მდებარეობს ამჟამინდელის ქვემოთ და უკავშირდება მას, ეწოდება შთამომავალი ეს კვანძი. ავიღოთ მაგალითი. აიღეთ კვანძი B, შემდეგ მისი მშობელი იქნება კვანძი A და მისი შვილები იქნება კვანძები D, E და F.

ფურცელი

კვანძს, რომელსაც შვილი არ ჰყავს, ხის ფოთოლს უწოდებენ. მაგალითში, კვანძები D, E, F, G, I, J, K იქნება ფოთლები.

ეს არის ძირითადი ტერმინოლოგია. სხვა ცნებები მოგვიანებით იქნება განხილული. ასე რომ, ორობითი ხე არის ხე, რომელშიც თითოეულ კვანძს ექნება არაუმეტეს ორი შვილი. როგორც მიხვდით, მაგალითიდან ხე არ იქნება ორობითი, რადგან B და H კვანძებს ორზე მეტი შვილი ჰყავთ. აქ არის ბინარული ხის მაგალითი:

ხის კვანძები შეიძლება შეიცავდეს ნებისმიერ ინფორმაციას. ორობითი საძიებო ხე არის ბინარული ხე, რომელსაც აქვს შემდეგი თვისებები:

ორივე მარცხენა და მარჯვენა ქვეხეები ორობითი საძიებო ხეებია.
თვითნებური X კვანძის მარცხენა ქვეხის ყველა კვანძს აქვს მონაცემთა გასაღების მნიშვნელობები უფრო ნაკლები ვიდრე თავად X კვანძის მონაცემთა გასაღების მნიშვნელობა.
თვითნებური 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;
    }
//...остальные методы узла
}

თითოეულ კვანძს ჰყავს ორი შვილი (სავსებით შესაძლებელია, რომ leftChild და/ან rightChild ბავშვები იყოს null). ალბათ მიხვდით, რომ ამ შემთხვევაში რიცხვითი მონაცემები არის კვანძში შენახული მონაცემები; გასაღები - კვანძის გასაღები.

ჩვენ გავარკვიეთ კვანძი, ახლა მოდით ვისაუბროთ ხეების აქტუალურ პრობლემებზე. შემდგომში სიტყვა „ხე“ ნიშნავს ორობითი საძიებო ხის კონცეფციას. ორობითი ხის სტრუქტურა:

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 ელემენტი დაბალანსებულ ხეში, მაშინ ეს ნიშნავს, რომ იქნება ხის ლოგი(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;
                    }
                }
            }
        }
    }

ამ შემთხვევაში, გარდა მიმდინარე კვანძისა, აუცილებელია შეინახოს ინფორმაცია მიმდინარე კვანძის მშობლის შესახებ. როდესაც დენი გახდება null, მშობელი ცვლადი შეიცავს ჩვენ გვჭირდება ფურცელს.
ჩასმის ეფექტურობა აშკარად იგივე იქნება, რაც ძიების - O(log(n)).

მოცილება

წაშლა არის ყველაზე რთული ოპერაცია, რომელიც უნდა გაკეთდეს ხეზე. გასაგებია, რომ პირველ რიგში საჭირო იქნება ელემენტის პოვნა, რომლის ამოღებას ვაპირებთ. მაგრამ მერე რა? თუ ჩვენ უბრალოდ დავაყენებთ მის მითითებას null-ზე, მაშინ დავკარგავთ ინფორმაციას იმ ქვეხის შესახებ, რომლის ფესვი არის ეს კვანძი. ხის მოცილების მეთოდები იყოფა სამ შემთხვევაში.

პირველი შემთხვევა. ამოსაღებ კვანძს შვილი არ ჰყავს.

თუ წასაშლელი კვანძს შვილი არ ჰყავს, ეს ნიშნავს, რომ ის ფოთოლია. ამიტომ, თქვენ შეგიძლიათ უბრალოდ დააყენოთ მისი მშობლის მარცხენა ან მარჯვენა Child ველები null.

მეორე შემთხვევა. ამოსაღებ კვანძს ჰყავს ერთი შვილი

ეს შემთხვევა ასევე არ არის ძალიან რთული. დავუბრუნდეთ ჩვენს მაგალითს. დავუშვათ, რომ ჩვენ უნდა წავშალოთ ელემენტი 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))

სიმეტრიული შემოვლითი გზა

ტრავერსია არის ვიზიტი ხის თითოეულ კვანძში, რათა რაღაც გააკეთოს.

რეკურსიული სიმეტრიული გავლის ალგორითმი:

გააკეთეთ მოქმედება მარცხენა ბავშვზე
გააკეთე მოქმედება საკუთარ თავთან
გააკეთეთ მოქმედება სწორ ბავშვზე

კოდი:

    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). ეს არის ორობითი ხეების ერთ-ერთი ყველაზე მნიშვნელოვანი, ჩემი აზრით, მინუსი.

გამოკითხვაში მონაწილეობა შეუძლიათ მხოლოდ დარეგისტრირებულ მომხმარებლებს. Შებრძანდითგთხოვთ

მე საკმაოდ დიდი ხანია არ ვყოფილვარ Habré-ზე და მინდა ვიცოდე, რა სტატიების ნახვა გსურთ მეტი?

მონაცემთა სტრუქტურები
ალგორითმები (DP, რეკურსია, მონაცემთა შეკუმშვა და ა.შ.)
მონაცემთა სტრუქტურებისა და ალგორითმების გამოყენება რეალურ ცხოვრებაში
ანდროიდის აპლიკაციების დაპროგრამება ჯავაში
Java ვებ აპლიკაციის პროგრამირება

ხმა მისცა 2 მომხმარებელმა. 1 მომხმარებელმა თავი შეიკავა.

წყარო: www.habr.com

ორობითი ხე ან როგორ მოვამზადოთ ორობითი საძიებო ხე