ដើមឈើគោលពីរ ឬរបៀបរៀបចំមែកធាងស្វែងរកប្រព័ន្ធគោលពីរ

ស្មានទុកមុន

អត្ថបទនេះគឺអំពីដើមឈើស្វែងរកប្រព័ន្ធគោលពីរ។ ថ្មីៗនេះខ្ញុំបានសរសេរអត្ថបទមួយអំពី ការបង្ហាប់ទិន្នន័យដោយវិធីសាស្ត្រ Huffman ។ នៅទីនោះខ្ញុំពិតជាមិនយកចិត្តទុកដាក់ចំពោះដើមឈើគោលពីរទេ ព្រោះវិធីសាស្ត្រស្វែងរក បញ្ចូល លុប មិនពាក់ព័ន្ធ។ ឥឡូវនេះខ្ញុំបានសម្រេចចិត្តសរសេរអត្ថបទអំពីដើមឈើ។ ប្រហែលជាយើងនឹងចាប់ផ្តើម។

មែកធាងគឺជារចនាសម្ព័ន្ធទិន្នន័យដែលមានថ្នាំងដែលតភ្ជាប់ដោយគែម។ យើងអាចនិយាយបានថាដើមឈើគឺជាករណីពិសេសនៃក្រាហ្វ។ នេះជាឧទាហរណ៍ដើមឈើ៖

នេះមិនមែនជាមែកធាងស្វែងរកប្រព័ន្ធគោលពីរទេ! អ្វីគ្រប់យ៉ាងគឺស្ថិតនៅក្រោមការកាត់!

ស័ព្ទ

ដើម

ឫសដើមឈើ គឺជាថ្នាំងកំពូលបំផុត។ ក្នុងឧទាហរណ៍នេះគឺជា node A. នៅក្នុងមែកធាង មានតែផ្លូវមួយប៉ុណ្ណោះដែលអាចនាំពី root ទៅកាន់ node ផ្សេងទៀត! តាមពិតថ្នាំងណាមួយអាចត្រូវបានចាត់ទុកថាជាឫសនៃអនុមែកធាងដែលត្រូវគ្នានឹងថ្នាំងនេះ។

ឪពុកម្តាយ / កូនចៅ

ថ្នាំងទាំងអស់លើកលែងតែ root មានគែមមួយយ៉ាងពិតប្រាកដដែលនាំទៅដល់ថ្នាំងផ្សេងទៀត។ ថ្នាំងខាងលើថ្នាំងបច្ចុប្បន្នត្រូវបានគេហៅថា ឪពុកម្តាយ ថ្នាំងនេះ។ ថ្នាំង​ដែល​មាន​ទីតាំង​នៅ​ខាងក្រោម​បច្ចុប្បន្ន​និង​បាន​តភ្ជាប់​ទៅ​វា​ត្រូវ​បាន​ហៅ​ កូនចៅ ថ្នាំងនេះ។ សូមលើកឧទាហរណ៍មួយ។ យកថ្នាំង 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;

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

ក្នុងនាមជាវាលថ្នាក់ យើងត្រូវការតែ root នៃមែកធាងប៉ុណ្ណោះ ពីព្រោះពី root ដោយប្រើវិធីសាស្ត្រ getLeftChild() និង getRightChild() អ្នកអាចទៅដល់ថ្នាំងណាមួយនៃមែកធាង។

ក្បួនដោះស្រាយដើមឈើ

Поиск

ចូរនិយាយថាអ្នកមានដើមឈើដែលបានសាងសង់។ តើធ្វើដូចម្តេចដើម្បីស្វែងរកធាតុជាមួយ key key? អ្នកត្រូវផ្លាស់ទីតាមលំដាប់លំដោយពីឫសចុះក្រោមដើមឈើ ហើយប្រៀបធៀបតម្លៃនៃកូនសោជាមួយកូនសោរនៃថ្នាំងបន្ទាប់៖ ប្រសិនបើកូនសោរតិចជាងកូនសោរនៃថ្នាំងបន្ទាប់ បន្ទាប់មកចូលទៅកាន់កូនចៅខាងឆ្វេងនៃថ្នាំង ប្រសិនបើច្រើនទៀត - នៅខាងស្តាំប្រសិនបើគ្រាប់ចុចស្មើគ្នា - ថ្នាំងដែលចង់បានត្រូវបានរកឃើញ! លេខកូដពាក់ព័ន្ធ៖

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 របស់មេរបស់វាទៅជា null។

ករណីទីពីរ។ ថ្នាំងដែលត្រូវដកចេញមានកូនមួយ។

ករណីនេះក៏មិនពិបាកខ្លាំងដែរ។ ចូរយើងត្រលប់ទៅឧទាហរណ៍របស់យើង។ ឧបមាថាយើងត្រូវលុបធាតុដែលមានកូនសោលេខ 14។ យល់ស្របថា ដោយសារវាជាកូនត្រឹមត្រូវរបស់ថ្នាំងដែលមានកូនសោ 10 ដូច្នេះកូនចៅរបស់វា (ក្នុងករណីនេះ លេខត្រឹមត្រូវ) នឹងមានកូនសោធំជាង 10 ដូច្នេះអ្នក អាច "កាត់" វាយ៉ាងងាយស្រួលពីមែកធាង ហើយភ្ជាប់មេដោយផ្ទាល់ទៅកូនរបស់ថ្នាំងដែលត្រូវបានលុប ពោលគឺឧ។ ភ្ជាប់ node ជាមួយ key 10 ទៅ node 13. ស្ថានភាពនឹងស្រដៀងគ្នា ប្រសិនបើយើងត្រូវលុប node ដែលជាកូនខាងឆ្វេងរបស់ parent របស់វា។ គិតអំពីវាសម្រាប់ខ្លួនអ្នក - ការប្រៀបធៀបពិតប្រាកដ។

ករណីទីបី។ Node មានកូនពីរនាក់

ករណីពិបាកបំផុត។ សូមក្រឡេកមើលឧទាហរណ៍ថ្មីមួយ។

ស្វែងរកអ្នកស្នង

ឧបមាថាយើងត្រូវដកថ្នាំងដោយប្រើសោ 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)។ នេះគឺជាការសំខាន់បំផុតមួយនៅក្នុងគំនិតរបស់ខ្ញុំ គុណវិបត្តិនៃដើមឈើគោលពីរ។

មានតែអ្នកប្រើប្រាស់ដែលបានចុះឈ្មោះប៉ុណ្ណោះដែលអាចចូលរួមក្នុងការស្ទង់មតិនេះ។ ចូលសូម។

ខ្ញុំ​មិន​បាន​មក​ Habre យូរ​មក​ហើយ​ ហើយ​ខ្ញុំ​ចង់​ដឹង​ថា​តើ​អត្ថបទ​ណា​ខ្លះ​ដែល​អ្នក​ចង់​មើល​បន្ថែម?

• រចនាសម្ព័ន្ធទិន្នន័យ

• ក្បួនដោះស្រាយ (DP, recursion, បង្ហាប់ទិន្នន័យ។ល។)

• ការអនុវត្តរចនាសម្ព័ន្ធទិន្នន័យ និងក្បួនដោះស្រាយក្នុងជីវិតពិត

• ការសរសេរកម្មវិធី Android នៅក្នុង Java

• កម្មវិធី Java Web Application Programming

អ្នកប្រើប្រាស់ 2 នាក់បានបោះឆ្នោត។ អ្នកប្រើប្រាស់ 1 នាក់ត្រូវបានហាមឃាត់។

ប្រភព៖ www.habr.com