Binary Tree သို့မဟုတ် binary ရှာဖွေရေးသစ်ပင်ကို ပြင်ဆင်နည်း

နိဒါနျး

ဤဆောင်းပါးသည် binary ရှာဖွေရေးသစ်ပင်များအကြောင်းဖြစ်သည်။ မကြာသေးမီက ဆောင်းပါးတစ်ပုဒ်ရေးခဲ့ဖူးသည်။ Huffman နည်းလမ်းကို အသုံးပြု၍ ဒေတာချုံ့ခြင်း။ ရှာဖွေခြင်း၊ ထည့်သွင်းခြင်းနှင့် ဖျက်ခြင်းနည်းလမ်းများသည် မသက်ဆိုင်သောကြောင့် ထိုနေရာတွင် binary သစ်ပင်များကို ကျွန်ုပ် သိပ်ဂရုမစိုက်ပါ။ အခုတော့ သစ်ပင်တွေအကြောင်း ဆောင်းပါးတစ်ပုဒ်ရေးဖို့ ဆုံးဖြတ်လိုက်တယ်။ စလိုက်ကြစို့။

သစ်ပင်သည် အစွန်းများဖြင့် ချိတ်ဆက်ထားသော node များပါဝင်သော ဒေတာဖွဲ့စည်းပုံဖြစ်သည်။ သစ်ပင်သည် ဂရပ်တစ်ခု၏ အထူးဖြစ်ရပ်တစ်ခုဟု ကျွန်ုပ်တို့ပြောနိုင်သည်။ ဒါက ဥပမာ သစ်ပင်

၎င်းသည် binary ရှာဖွေမှုသစ်ပင် မဟုတ်ပါ။ အရာအားလုံး ဖြတ်သွားသည် ။

ဝေါဟာရကထာ

အမြစ်

သစ်ပင်အမြစ် - ဒါကသူ့ရဲ့ထိပ်ဆုံး node ပါ။ ဥပမာတွင်၊ ဤသည်မှာ node A ဖြစ်သည်။ သစ်ပင်တစ်ပင်တွင်၊ လမ်းကြောင်းတစ်ခုသာ အမြစ်မှ အခြား node တစ်ခုဆီသို့ ဦးတည်နိုင်သည်။ တကယ်တော့၊ မည်သည့် node ကိုမဆို ဤ node နှင့် သက်ဆိုင်သော subtree ၏ root အဖြစ် ယူဆနိုင်ပါသည်။

မိဘ/သားစဉ်မြေးဆက်များ

root မှလွဲ၍ node အားလုံးတွင် အစွန်းတစ်ခု အတိအကျရှိပြီး အခြား node တစ်ခုဆီသို့ ဦးတည်သည်။ လက်ရှိတစ်ခု၏အထက်တွင်ရှိသော node ကိုခေါ်သည်။ မိဘ ဒီ node လက်ရှိတစ်ခု၏အောက်တွင်ရှိပြီး ၎င်းနှင့်ချိတ်ဆက်ထားသော node ကိုခေါ်သည်။ သားစဉ်မြေးဆက် ဒီ node ဥပမာတစ်ခုသုံးကြည့်ရအောင်။ node B ကိုယူကြပါစို့၊ ထို့နောက်၎င်း၏မိဘသည် node A ဖြစ်ပြီး၎င်း၏ကလေးများသည် node D၊ E နှင့် F ဖြစ်လိမ့်မည်။

အိပ်ရာခင်း

ကလေးများမရှိသော အရွက်ကို သစ်ပင်၏အရွက်ဟုခေါ်သည်။ ဥပမာတွင်၊ အရွက်များသည် node D, E, F, G, I, J, K ဖြစ်လိမ့်မည်။

ဒါက အခြေခံအသုံးအနှုန်းပါ။ အခြားသဘောတရားများကို ဆက်လက်ဆွေးနွေးပါမည်။ ထို့ကြောင့်၊ binary tree သည် node တစ်ခုစီတွင် ကလေးများ နှစ်ခုထက် မပိုသော သစ်ပင်တစ်ခုဖြစ်သည်။ သင်ခန့်မှန်းထားသည့်အတိုင်း၊ ဥပမာမှသစ်ပင်သည် binary ဖြစ်လိမ့်မည်မဟုတ်ပါ၊ အဘယ်ကြောင့်ဆိုသော် node B နှင့် H တွင် ကလေးနှစ်ခုထက်ပိုပါသည်။ ဤသည်မှာ ဒွိသစ်ပင်၏ ဥပမာတစ်ခုဖြစ်သည်။

tree node တွေမှာ အချက်အလက်တွေ ပါနိုင်ပါတယ်။ ဒွိရှာဖွေမှုသစ်ပင်သည် အောက်ပါဂုဏ်သတ္တိများပါရှိသော ဒွိစုံသစ်ပင်ဖြစ်သည်။

1. ဘယ်နှင့်ညာ နှစ်ခုစလုံးသည် ဒွိရှာဖွေရေးသစ်ပင်များဖြစ်သည်။
2. မထင်သလို node X ၏ ဘယ်ဘက်အခွဲ၏ node အားလုံးတွင် node X ၏ data key ၏တန်ဖိုးထက်နည်းသော data key တန်ဖိုးများရှိသည်။
3. မျှတသော node X ၏ ညာဘက်အခွဲရှိ node များအားလုံးတွင် node X ၏ data key ၏တန်ဖိုးထက် ဒေတာသော့တန်ဖိုးများထက်ကြီးသော သို့မဟုတ် ညီမျှပါသည်။

သော့ - node ၏ လက္ခဏာ တစ်ခုခု (ဥပမာ၊ နံပါတ်)။ ဤသော့နှင့်ကိုက်ညီသည့်သစ်ပင်ဒြပ်စင်ကိုရှာဖွေနိုင်စေရန် သော့လိုအပ်ပါသည်။ binary ရှာဖွေမှုသစ်ပင်၏ ဥပမာ-

သစ်ပင်မြင်ကွင်း

ကျွန်ုပ်တို့ တိုးတက်လာသည်နှင့်အမျှ သင့်နားလည်မှု တိုးတက်စေရန်အတွက် ကုဒ်အပိုင်းအစအချို့ (ဖြစ်နိုင်သည်) ကို ကျွန်ုပ်ပေးပါမည်။ ကုဒ်အပြည့်အစုံသည် ဆောင်းပါး၏အဆုံးတွင် ရှိလိမ့်မည်။

သစ်ပင်တွင် node များပါဝင်သည်။ Node တည်ဆောက်ပုံ-

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

node တစ်ခုစီတွင် ကလေးနှစ်ခုပါရှိသည် ( leftChild နှင့်/သို့မဟုတ် rightChild ကလေးများသည် null value ပါရှိလိမ့်မည်)။ ဤကိစ္စတွင် နံပါတ်ဒေတာသည် node တွင် သိမ်းဆည်းထားသော ဒေတာဖြစ်သည်ကို သင်သဘောပေါက်ပေမည်။ သော့ - node သော့။

ထုံးဖွဲ့ပြီးပြီ၊ အခုသစ်ပင်တွေအကြောင်း ဖိနှိပ်တဲ့ပြဿနာတွေအကြောင်း ပြောကြရအောင်။ ဤနောက်၊ “သစ်ပင်” ဟူသော စကားလုံးဖြင့် ကျွန်ုပ်သည် ဒွိရှာဖွေမှုသစ်ပင်၏ သဘောတရားကို ဆိုလိုပါသည်။ ဒွိသစ်ပင်ဖွဲ့စည်းပုံ-

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

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

getLeftChild() နှင့် getRightChild() နည်းလမ်းများကို အသုံးပြု၍ root မှ အတန်းအကွက်တစ်ခုအဖြစ် သစ်ပင်၏ အမြစ်ကို ကျွန်ုပ်တို့ လိုအပ်ပါသည်။

သစ်ပင်ရှိ အယ်လဂိုရီသမ်များ

Поиск

မင်းမှာ ဆောက်ထားတဲ့သစ်ပင်ရှိတယ်ဆိုပါစို့။ သော့သော့ဖြင့် ဒြပ်စင်တစ်ခုကို မည်သို့ရှာရမည်နည်း။ သင်သည် အမြစ်မှသစ်ပင်အောက်သို့ ရွေ့လျားပြီး သော့တန်ဖိုးကို နောက် node ၏ သော့နှင့် နှိုင်းယှဉ်ရန် လိုအပ်သည်- အကယ်၍ သော့သည် နောက် node ၏ သော့ထက်နည်းပါက၊ ၎င်းသည် ရှိပါက node ၏ ဘယ်ဘက်သို့ သွားပါ။ သာ၍ကြီးသည်၊ ညာဘက်တွင်၊ သော့များညီပါက၊ လိုချင်သော node ကိုတွေ့လိမ့်မည်။ သက်ဆိုင်ရာ ကုဒ်-

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

အကယ်၍ လက်ရှိသည် အချည်းနှီးဖြစ်သွားပါက၊ ရှာဖွေမှုသည် သစ်ပင်၏အဆုံးသို့ ရောက်ရှိသွားသည် (အယူအဆအဆင့်တွင်၊ သင်သည် သစ်ရွက်၏အဆက်အစပ်မရှိသောနေရာတွင် ရှိနေသည်)။

ဟန်ချက်ညီသောသစ်ပင်တွင် ရှာဖွေမှု အယ်လဂိုရီသမ်၏ ထိရောက်မှုကို သုံးသပ်ကြည့်ကြစို့ (node ​​များကို အညီအမျှ ဖြန့်ဝေနေသည့် သစ်ပင်)။ ထို့နောက် ရှာဖွေမှု ထိရောက်မှုသည် O(log(n)) ဖြစ်လိမ့်မည်၊၊ လော့ဂရစ်သမ်သည် အခြေခံ 2 ဖြစ်သည်။ ကြည့်ပါ- ဟန်ချက်ညီသော သစ်ပင်တွင် n ဒြပ်စင်များ ရှိပါက၊ ဆိုလိုသည်မှာ အဆိုပါ အဆင့် ၂ ၏ အခြေသို့ log(n) ရှိလိမ့်မည်၊ သစ်ပင်။ ရှာဖွေမှုတွင်၊ သံသရာ၏ခြေတစ်လှမ်းတွင်၊ သင်သည် အဆင့်တစ်ခုသို့ ဆင်းသွားနိုင်သည်။

ထည့်သွင်း

ရှာဖွေမှု၏ အနှစ်သာရကို ဆုပ်ကိုင်ထားလျှင် ထည့်သွင်းမှုကို နားလည်ရန် သင့်အတွက် ခက်ခဲမည်မဟုတ်ပါ။ သင်ရှာဖွေမှုတွင်ဖော်ပြထားသော မျိုးရိုးလိုက်စည်းမျဉ်းများအတိုင်း သစ်ပင်၏အရွက်တစ်ရွက်သို့ဆင်းရန် လိုအပ်ပြီး သော့ပေါ် မူတည်၍ ၎င်း၏သားစဉ်မြေးဆက်ဖြစ်လာသည်- ဘယ် သို့မဟုတ် ညာ။ အကောင်အထည်ဖော်ခြင်း-

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

ဤကိစ္စတွင်၊ လက်ရှိ node အပြင်၊ လက်ရှိ node ၏ parent အကြောင်း အချက်အလက်များကို သိမ်းဆည်းရန် လိုအပ်ပါသည်။ current သည် null နှင့် ညီမျှသောအခါ၊ parent variable တွင် ကျွန်ုပ်တို့လိုအပ်သောစာရွက်ပါရှိသည်။
ထည့်သွင်းခြင်း၏ ထိရောက်မှုသည် ရှာဖွေမှု နှင့် အတူတူပင်ဖြစ်သည် - O(log(n))။

ဖယ်ရှားရေး

ဖယ်ရှားခြင်းသည် သစ်ပင်တစ်ပင်ပေါ်တွင် လုပ်ဆောင်ရန် လိုအပ်သော အခက်ခဲဆုံး လုပ်ဆောင်ချက်ဖြစ်သည်။ ကျွန်ုပ်တို့ ဖျက်ပစ်မည့် အစိတ်အပိုင်းကို ဦးစွာ ရှာဖွေရန် လိုအပ်သည်မှာ ရှင်းပါသည်။ သို့ဖြစ်လျှင် အဘယ်သို့နည်း။ ၎င်း၏အကိုးအကားကို null အဖြစ် ရိုးရိုးရှင်းရှင်း သတ်မှတ်ပါက၊ ဤ node သည် root ဖြစ်သည့် subtree နှင့်ပတ်သက်သော အချက်အလက်များကို ဆုံးရှုံးမည်ဖြစ်ပါသည်။ သစ်ပင်ဖယ်ရှားခြင်းနည်းလမ်းကို သုံးမျိုးခွဲထားသည်။

ပထမကိစ္စ။ ဖျက်လိုက်သော node တွင် ကလေးများမရှိပါ။

ဖျက်လိုက်သော node တွင် ကလေးများမပါပါက၊ ၎င်းသည် အရွက်ဖြစ်သည်ဟု ဆိုလိုသည်။ ထို့ကြောင့်၊ သင်သည် ၎င်း၏မိဘ၏ဘယ်ဘက်ကလေး သို့မဟုတ် ညာဘက်ကလေးအကွက်များကို null အဖြစ်သတ်မှတ်နိုင်သည်။

ဒုတိယကိစ္စ။ ဖျက်ပစ်ရမည့် ကုဒ်တွင် ကလေးတစ်ခုရှိသည်။

ဒီကိစ္စက သိပ်ပြီး မရှုပ်ထွေးပါဘူး။ ကျွန်ုပ်တို့၏ ဥပမာကို ပြန်ကြည့်ကြပါစို့။ သော့ 14 ပါဒြပ်တစ်ခုကို ဖျက်ရန် လိုအပ်သည်ဆိုပါစို့။ ၎င်းသည် ကီး 10 ပါသော node တစ်ခု၏ မှန်ကန်သောမျိုးဆက်ဖြစ်သောကြောင့် ၎င်း၏သားစဉ်မြေးဆက်များ (ဤကိစ္စတွင် မှန်ကန်သောတစ်ခုသည်) တွင် သော့ 10 ထက်ကြီးနေမည်ကို သဘောတူပါသည်။ ၎င်းကို သစ်ပင်မှ အလွယ်တကူ “ဖြတ်” နိုင်ပြီး ဖျက်လိုက်သော node ၏ ကလေးနှင့် မိဘကို တိုက်ရိုက်ချိတ်ဆက်နိုင်သည် ၊ ဆိုလိုသည်မှာ၊ node ကို key 10 မှ node 13 နှင့် ချိတ်ဆက်ပါ။ ၎င်း၏ parent ၏ ဘယ်ဘက်ကလေးဖြစ်သော node တစ်ခုကို ဖျက်ရန်လိုအပ်ပါက အခြေအနေသည် အလားတူဖြစ်လိမ့်မည်။ သင်ကိုယ်တိုင် စဉ်းစားကြည့်ပါ- အတိအကျ ဥပမာတစ်ခု။

တတိယကိစ္စ။ node တစ်ခုတွင် ကလေးနှစ်ခုရှိသည်။

အခက်ခဲဆုံးကိစ္စ။ ဥပမာအသစ်ကိုကြည့်ရအောင်။

ဆက်ခံသူကိုရှာပါ။

key 25 ပါသော node တစ်ခုကို ဖျက်ရန် လိုအပ်သည်ဆိုပါစို့။ ၎င်းနေရာတွင် မည်သူကို ထည့်သင့်သနည်း။ သူ့နောက်လိုက်တစ်ယောက် (descendants or descendants of descendants) ဖြစ်လာရမယ်။ ဆက်ခံသူ(ဖယ်ရှားခံရသည့် node ၏နေရာကိုရယူမည့်သူ)။

ဘယ်သူက ဆက်ခံသင့်တယ်ဆိုတာ ဘယ်လိုနားလည်နိုင်မလဲ။ ပင်ကိုယ်အားဖြင့်၊ ဤသည်မှာ ဖျက်လိုက်သော node မှ နောက်အကြီးဆုံးသော့ဖြစ်ပြီး သစ်ပင်ရှိ ကုဒ်တစ်ခုဖြစ်သည်။ algorithm မှာ အောက်ပါအတိုင်းဖြစ်သည်။ ၎င်း၏ ညာဘက်သားစဉ်မြေးဆက်သို့ သင်သွားရန်လိုအပ်သည် (ဆက်ခံသောကီးသည် ဖျက်လိုက်သော node ၏သော့ထက် ပိုကြီးသည်ဟု ဆိုထားပြီးဖြစ်သောကြောင့် ညာဘက်တွင် အမြဲရှိနေရန် လိုအပ်သည်)၊ ထို့နောက် ညာဘက်ဆက်ခံသူ၏ ဘယ်ဘက်သားစဉ်မြေးဆက်များ၏ ကွင်းဆက်ကို ဖြတ်သွားပါ။ . ဥပမာတွင်၊ ကျွန်ုပ်တို့သည် သော့ 35 ပါသော node သို့သွားကာ ၎င်း၏ဘယ်ဘက်ကလေးများ၏ ကွင်းဆက်များမှတစ်ဆင့် အရွက်ဆီသို့သွားသည် - ဤအခြေအနေတွင်၊ ဤကွင်းဆက်သည် သော့ 30 ပါသော node ၏တစ်ခုတည်းသာပါ၀င်ပါသည်။ အတိအကျပြောရလျှင် ကျွန်ုပ်တို့ ရှာဖွေနေပါသည်။ ကျွန်ုပ်တို့ရှာဖွေနေသော node ထက်ကြီးသော node အစုတွင် အသေးငယ်ဆုံး node အတွက်။

ဆက်ခံရှာဖွေရေးနည်းလမ်းကုဒ်-

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

အချိုးကျ ရှောင်ကွင်း

Traversal သည် ၎င်းကိုလုပ်ဆောင်မှုအချို့ပြုလုပ်ရန်အတွက် သစ်ပင်၏ node တစ်ခုစီသို့ သွားရောက်ခြင်းဖြစ်သည်။

ထပ်ခါတလဲလဲ အချိုးကျသော ဖြတ်သန်းမှုဆိုင်ရာ အယ်လဂိုရီသမ်-

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) သို့ ယိုယွင်းခြင်း

သစ်ပင်ကို ဟန်ချက်မညီအောင် လုပ်ထားရင် သင် တော်တော်များများ သတိထားမိကြမှာပါ။ ဥပမာ၊ သစ်ပင်တစ်ပင်တွင် တိုးလာသောသော့များပါသော node များကို ထည့်ပါ- 1,2,3,4,5,6... ထို့နောက် သစ်ပင်သည် လင့်ခ်ချိတ်ထားသောစာရင်းနှင့် အနည်းငယ်ဆင်တူပါလိမ့်မည်။ ဟုတ်ပါသည်၊ သစ်ပင်သည် ၎င်း၏သစ်ပင်ဖွဲ့စည်းပုံအား ဆုံးရှုံးမည်ဖြစ်ပြီး၊ ထို့ကြောင့် ဒေတာဝင်ရောက်ခြင်း၏ ထိရောက်မှုရှိသည်။ ရှာဖွေမှု၊ ထည့်သွင်းမှု၊ နှင့် ဖျက်ခြင်းလုပ်ဆောင်မှုများ၏ ရှုပ်ထွေးမှုသည် ချိတ်ဆက်ထားသောစာရင်းတစ်ခု၏ တူညီလိမ့်မည်- O(n)။ ဒါက binary tree တွေရဲ့ အရေးကြီးဆုံး အားနည်းချက်တွေထဲက တစ်ခုပါ။

စာရင်းသွင်းအသုံးပြုသူများသာ စစ်တမ်းတွင် ပါဝင်နိုင်ပါသည်။ ဆိုင်းအင်လုပ်ခြင်း, ကျေးဇူးပြု။

ကျွန်ုပ်သည် အချက်အချာကျသောနေရာသို့ မရောက်တာ ကြာပြီဖြစ်ပြီး မည်သည့်အကြောင်းအရာများကို သင်ပိုကြည့်လိုသနည်းဟူသည့် ဆောင်းပါးများကို သိလိုပါသည်။

• ဒေတာဖွဲ့စည်းပုံများ

• အယ်လဂိုရီသမ်များ (DP၊ ပြန်ကောက်ခြင်း၊ ဒေတာချုံ့ခြင်း စသည်)

• လက်တွေ့ဘဝတွင် ဒေတာဖွဲ့စည်းပုံများနှင့် အယ်လဂိုရီသမ်များကို အသုံးချခြင်း။

• Java တွင် Android အပလီကေးရှင်းများ ပရိုဂရမ်ရေးခြင်း။

• Java တွင် ဝဘ်အက်ပလီကေးရှင်းများ ပရိုဂရမ်ရေးခြင်း။

အသုံးပြုသူ 2 ဦး မဲပေးခဲ့သည်။ အသုံးပြုသူ 1 ဦး ရှောင်ခဲ့သည်။

အရင်းအမြစ်: www.habr.com