🥇ബൈനറി ട്രീ അല്ലെങ്കിൽ എങ്ങനെ ഒരു ബൈനറി സെർച്ച് ട്രീ തയ്യാറാക്കാം

ഫോർ‌പ്ലേ

ഈ ലേഖനം ബൈനറി സെർച്ച് ട്രീകളെ കുറിച്ചുള്ളതാണ്. ഞാൻ അടുത്തിടെ ഒരു ലേഖനം എഴുതി ഹഫ്മാൻ രീതി ഉപയോഗിച്ച് ഡാറ്റ കംപ്രഷൻ. അവിടെ ഞാൻ ബൈനറി മരങ്ങൾ ശരിക്കും ശ്രദ്ധിച്ചില്ല, കാരണം തിരയൽ, തിരുകൽ, ഇല്ലാതാക്കൽ രീതികൾ പ്രസക്തമല്ല. ഇപ്പോൾ ഞാൻ മരങ്ങളെക്കുറിച്ച് ഒരു ലേഖനം എഴുതാൻ തീരുമാനിച്ചു. ഒരുപക്ഷേ ഞങ്ങൾ ആരംഭിക്കും.

അരികുകളാൽ ബന്ധിപ്പിച്ച നോഡുകൾ അടങ്ങുന്ന ഒരു ഡാറ്റാ ഘടനയാണ് ട്രീ. ഒരു ഗ്രാഫിന്റെ ഒരു പ്രത്യേക കേസാണ് ഒരു മരം എന്ന് നമുക്ക് പറയാം. ഒരു വൃക്ഷത്തിന്റെ ഉദാഹരണം ഇതാ:

ഇതൊരു ബൈനറി സെർച്ച് ട്രീ അല്ല! എല്ലാം വെട്ടിക്കുറച്ചിരിക്കുന്നു!

പദാവലി

റൂട്ട്

ട്രീ റൂട്ട് ഏറ്റവും ഉയർന്ന നോഡ് ആണ്. ഉദാഹരണത്തിൽ, ഇതാണ് നോഡ് A. മരത്തിൽ, ഒരു പാതയ്ക്ക് മാത്രമേ റൂട്ടിൽ നിന്ന് മറ്റേതെങ്കിലും നോഡിലേക്ക് നയിക്കാൻ കഴിയൂ! വാസ്തവത്തിൽ, ഏത് നോഡും ഈ നോഡിന് അനുയോജ്യമായ സബ്ട്രീയുടെ റൂട്ടായി കണക്കാക്കാം.

മാതാപിതാക്കൾ/സന്തതി

റൂട്ട് ഒഴികെയുള്ള എല്ലാ നോഡുകൾക്കും കൃത്യമായി ഒരു എഡ്ജ് മറ്റൊരു നോഡിലേക്ക് നയിക്കുന്നു. നിലവിലെ നോഡിന് മുകളിലുള്ള നോഡിനെ വിളിക്കുന്നു രക്ഷിതാവ് ഈ നോഡ്. നിലവിലുള്ളതിന് താഴെ സ്ഥിതി ചെയ്യുന്ന ഒരു നോഡ്, അതുമായി ബന്ധിപ്പിച്ചിരിക്കുന്നു സന്തതി ഈ നോഡ്. നമുക്ക് ഒരു ഉദാഹരണം എടുക്കാം. നോഡ് ബി എടുക്കുക, അപ്പോൾ അതിന്റെ പാരന്റ് നോഡ് എ ആയിരിക്കും, അതിന്റെ കുട്ടികൾ ഡി, ഇ, എഫ് എന്നീ നോഡുകൾ ആയിരിക്കും.

ലീഫ്

കുട്ടികളില്ലാത്ത ഒരു നോഡിനെ മരത്തിന്റെ ഇല എന്ന് വിളിക്കുന്നു. ഉദാഹരണത്തിൽ, നോഡുകൾ 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;
    }
//...остальные методы узла
}

ഓരോ നോഡിനും രണ്ട് കുട്ടികളുണ്ട് (ഇടത് കുട്ടി കൂടാതെ/അല്ലെങ്കിൽ വലത് കുട്ടികൾ അസാധുവാകാൻ സാധ്യതയുണ്ട്). ഈ സാഹചര്യത്തിൽ നമ്പർ ഡാറ്റ നോഡിൽ സംഭരിച്ചിരിക്കുന്ന ഡാറ്റയാണെന്ന് നിങ്ങൾ മനസ്സിലാക്കിയിരിക്കാം; കീ - നോഡ് കീ.

ഞങ്ങൾ കെട്ട് കണ്ടെത്തി, ഇപ്പോൾ നമുക്ക് മരങ്ങളെക്കുറിച്ചുള്ള പ്രധാന പ്രശ്നങ്ങളെക്കുറിച്ച് സംസാരിക്കാം. ഇനിമുതൽ, "മരം" എന്ന വാക്കിന്റെ അർത്ഥം ബൈനറി സെർച്ച് ട്രീ എന്ന ആശയമാണ്. ബൈനറി ട്രീ ഘടന:

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

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

ഒരു ക്ലാസ് ഫീൽഡ് എന്ന നിലയിൽ, ഞങ്ങൾക്ക് മരത്തിന്റെ റൂട്ട് മാത്രമേ ആവശ്യമുള്ളൂ, കാരണം റൂട്ടിൽ നിന്ന്, getLeftChild() and 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 ആയി സജ്ജീകരിക്കുകയാണെങ്കിൽ, ഈ നോഡ് റൂട്ട് ആയ സബ്ട്രീയെക്കുറിച്ചുള്ള വിവരങ്ങൾ നമുക്ക് നഷ്‌ടമാകും. മരം നീക്കംചെയ്യൽ രീതികൾ മൂന്ന് കേസുകളായി തിരിച്ചിരിക്കുന്നു.

ആദ്യ കേസ്. നീക്കം ചെയ്യേണ്ട നോഡിന് കുട്ടികളില്ല.

നീക്കം ചെയ്യേണ്ട നോഡിന് കുട്ടികളില്ലെങ്കിൽ, അത് ഒരു ഇലയാണെന്ന് അർത്ഥമാക്കുന്നു. അതിനാൽ, നിങ്ങൾക്ക് അതിന്റെ രക്ഷിതാവിന്റെ ലെഫ്റ്റ് ചൈൽഡ് അല്ലെങ്കിൽ റൈറ്റ് ചൈൽഡ് ഫീൽഡുകൾ അസാധുവായി സജ്ജീകരിക്കാം.

രണ്ടാമത്തെ കേസ്. നീക്കം ചെയ്യേണ്ട നോഡിന് ഒരു കുട്ടിയുണ്ട്

ഈ കേസും വളരെ ബുദ്ധിമുട്ടുള്ള കാര്യമല്ല. നമുക്ക് നമ്മുടെ ഉദാഹരണത്തിലേക്ക് മടങ്ങാം. കീ 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(ലോഗ്(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());
        }
    }
}

പി.എസ്

O(n) ലേക്ക് ഡീജനറേഷൻ

നിങ്ങളിൽ പലരും ശ്രദ്ധിച്ചിരിക്കാം: നിങ്ങൾ മരത്തെ അസന്തുലിതമാക്കിയാലോ? ഉദാഹരണത്തിന്, വർദ്ധിച്ചുവരുന്ന കീകൾ ഉപയോഗിച്ച് ട്രീയിൽ നോഡുകൾ ഇടുക: 1,2,3,4,5,6... അപ്പോൾ ട്രീ ഒരു ലിങ്ക് ചെയ്ത ലിസ്റ്റിനെ അനുസ്മരിപ്പിക്കും. അതെ, വൃക്ഷത്തിന് അതിന്റെ ട്രീ ഘടന നഷ്ടപ്പെടും, അതിനാൽ ഡാറ്റ ആക്‌സസിന്റെ കാര്യക്ഷമത. തിരയൽ, തിരുകൽ, ഇല്ലാതാക്കൽ പ്രവർത്തനങ്ങൾ എന്നിവയുടെ സങ്കീർണ്ണത ലിങ്ക് ചെയ്‌ത ലിസ്റ്റിന് സമാനമാകും: O(n). ഇത് ഏറ്റവും പ്രധാനപ്പെട്ട ഒന്നാണ്, എന്റെ അഭിപ്രായത്തിൽ, ബൈനറി മരങ്ങളുടെ ദോഷങ്ങൾ.

രജിസ്റ്റർ ചെയ്ത ഉപയോക്താക്കൾക്ക് മാത്രമേ സർവേയിൽ പങ്കെടുക്കാൻ കഴിയൂ. സൈൻ ഇൻദയവായി.

ഞാൻ വളരെക്കാലമായി ഹബ്രെയിൽ ഇല്ല, കൂടാതെ ഏതൊക്കെ വിഷയങ്ങളെക്കുറിച്ചുള്ള ലേഖനങ്ങളാണ് നിങ്ങൾ കൂടുതൽ കാണാൻ ആഗ്രഹിക്കുന്നതെന്ന് അറിയാൻ ഞാൻ ആഗ്രഹിക്കുന്നു?

ഡാറ്റ ഘടനകൾ
അൽഗോരിതങ്ങൾ (ഡിപി, റികർഷൻ, ഡാറ്റ കംപ്രഷൻ മുതലായവ)
യഥാർത്ഥ ജീവിതത്തിൽ ഡാറ്റാ ഘടനകളുടെയും അൽഗോരിതങ്ങളുടെയും പ്രയോഗം
ജാവയിൽ ആൻഡ്രോയിഡ് ആപ്ലിക്കേഷനുകൾ പ്രോഗ്രാമിംഗ്
ജാവ വെബ് ആപ്ലിക്കേഷൻ പ്രോഗ്രാമിംഗ്

2 ഉപയോക്താക്കൾ വോട്ട് ചെയ്തു. 1 ഉപയോക്താവ് വിട്ടുനിന്നു.

ഉറവിടം: www.habr.com

ബൈനറി ട്രീ അല്ലെങ്കിൽ ഒരു ബൈനറി സെർച്ച് ട്രീ എങ്ങനെ തയ്യാറാക്കാം

ഫോർ‌പ്ലേ

പദാവലി

റൂട്ട്

മാതാപിതാക്കൾ/സന്തതി

ലീഫ്

വൃക്ഷ കാഴ്ച

ട്രീ അൽഗോരിതങ്ങൾ

Поиск

കൂട്ടിച്ചേര്ക്കുക

ഇല്ലാതാക്കുക

ആദ്യ കേസ്. നീക്കം ചെയ്യേണ്ട നോഡിന് കുട്ടികളില്ല.

രണ്ടാമത്തെ കേസ്. നീക്കം ചെയ്യേണ്ട നോഡിന് ഒരു കുട്ടിയുണ്ട്

മൂന്നാമത്തെ കേസ്. നോഡിന് രണ്ട് കുട്ടികളുണ്ട്

ഒരു പിൻഗാമിയെ തിരയുക

ഒരു മരത്തിൽ പരമാവധി/കുറഞ്ഞത് കണ്ടെത്തുന്നു

സമമിതി ബൈപാസ്

തീരുമാനം

പി.എസ്

O(n) ലേക്ക് ഡീജനറേഷൻ

ഒരു അഭിപ്രായം ചേർക്കുക

ബൈനറി ട്രീ അല്ലെങ്കിൽ ഒരു ബൈനറി സെർച്ച് ട്രീ എങ്ങനെ തയ്യാറാക്കാം

ഫോർ‌പ്ലേ

പദാവലി

റൂട്ട്

മാതാപിതാക്കൾ/സന്തതി

ലീഫ്

വൃക്ഷ കാഴ്ച

ട്രീ അൽഗോരിതങ്ങൾ

Поиск

കൂട്ടിച്ചേര്ക്കുക

ഇല്ലാതാക്കുക

ആദ്യ കേസ്. നീക്കം ചെയ്യേണ്ട നോഡിന് കുട്ടികളില്ല.

രണ്ടാമത്തെ കേസ്. നീക്കം ചെയ്യേണ്ട നോഡിന് ഒരു കുട്ടിയുണ്ട്

മൂന്നാമത്തെ കേസ്. നോഡിന് രണ്ട് കുട്ടികളുണ്ട്

ഒരു പിൻഗാമിയെ തിരയുക

ഒരു മരത്തിൽ പരമാവധി/കുറഞ്ഞത് കണ്ടെത്തുന്നു

സമമിതി ബൈപാസ്

തീരുമാനം

പി.എസ്

O(n) ലേക്ക് ഡീജനറേഷൻ

ഒരു അഭിപ്രായം ചേർക്കുക മറുപടി റദ്ദാക്കാൻ

ഒരു അഭിപ്രായം ചേർക്കുക