ಬೈನರಿ ಟ್ರೀ ಅಥವಾ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಅನ್ನು ಹೇಗೆ ತಯಾರಿಸುವುದು

ಮುನ್ನುಡಿ

ಈ ಲೇಖನ ಬೈನರಿ ಹುಡುಕಾಟ ಮರಗಳ ಬಗ್ಗೆ. ನಾನು ಇತ್ತೀಚೆಗೆ ಲೇಖನವನ್ನು ಬರೆದಿದ್ದೇನೆ ಹಫ್ಮನ್ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಡೇಟಾ ಸಂಕುಚಿತಗೊಳಿಸುವಿಕೆ. ಅಲ್ಲಿ ನಾನು ಬೈನರಿ ಮರಗಳಿಗೆ ಹೆಚ್ಚು ಗಮನ ಕೊಡಲಿಲ್ಲ, ಏಕೆಂದರೆ ಹುಡುಕಾಟ, ಅಳವಡಿಕೆ ಮತ್ತು ಅಳಿಸುವಿಕೆ ವಿಧಾನಗಳು ಸಂಬಂಧಿತವಾಗಿಲ್ಲ. ಈಗ ನಾನು ಮರಗಳ ಬಗ್ಗೆ ಲೇಖನವನ್ನು ಬರೆಯಲು ನಿರ್ಧರಿಸಿದೆ. ನಾವೀಗ ಆರಂಭಿಸೋಣ.

ಮರವು ಅಂಚುಗಳಿಂದ ಸಂಪರ್ಕಿಸಲಾದ ನೋಡ್‌ಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಡೇಟಾ ರಚನೆಯಾಗಿದೆ. ಮರವು ಗ್ರಾಫ್ನ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ ಎಂದು ನಾವು ಹೇಳಬಹುದು. ಒಂದು ಉದಾಹರಣೆ ಮರ ಇಲ್ಲಿದೆ:

ಇದು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಅಲ್ಲ! ಎಲ್ಲವನ್ನೂ ಕತ್ತರಿಸಲಾಗಿದೆ!

ಪರಿಭಾಷೆ

ರೂಟ್

ಮರದ ಬೇರು - ಇದು ಅದರ ಉನ್ನತ ನೋಡ್ ಆಗಿದೆ. ಉದಾಹರಣೆಯಲ್ಲಿ, ಇದು ನೋಡ್ A. ಮರದಲ್ಲಿ, ಕೇವಲ ಒಂದು ಮಾರ್ಗವು ಮೂಲದಿಂದ ಯಾವುದೇ ಇತರ ನೋಡ್‌ಗೆ ಕಾರಣವಾಗಬಹುದು! ವಾಸ್ತವವಾಗಿ, ಯಾವುದೇ ನೋಡ್ ಅನ್ನು ಈ ನೋಡ್‌ಗೆ ಅನುಗುಣವಾದ ಸಬ್‌ಟ್ರೀಯ ಮೂಲ ಎಂದು ಪರಿಗಣಿಸಬಹುದು.

ಪೋಷಕರು / ವಂಶಸ್ಥರು

ಮೂಲವನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ನೋಡ್‌ಗಳು ನಿಖರವಾಗಿ ಒಂದು ಅಂಚನ್ನು ಮತ್ತೊಂದು ನೋಡ್‌ಗೆ ಮುನ್ನಡೆಸುತ್ತವೆ. ಪ್ರಸ್ತುತದ ಮೇಲಿರುವ ನೋಡ್ ಅನ್ನು ಕರೆಯಲಾಗುತ್ತದೆ ಪೋಷಕ ಈ ನೋಡ್. ಪ್ರಸ್ತುತ ಒಂದಕ್ಕಿಂತ ಕೆಳಗಿರುವ ಒಂದು ನೋಡ್ ಅನ್ನು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಅದಕ್ಕೆ ಸಂಪರ್ಕಿಸಲಾಗಿದೆ ವಂಶಸ್ಥ ಈ ನೋಡ್. ಒಂದು ಉದಾಹರಣೆಯನ್ನು ಬಳಸೋಣ. ನೋಡ್ ಬಿ ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳೋಣ, ನಂತರ ಅದರ ಪೋಷಕ ನೋಡ್ A ಆಗಿರುತ್ತದೆ ಮತ್ತು ಅದರ ಮಕ್ಕಳು ನೋಡ್ D, E ಮತ್ತು F ಆಗಿರುತ್ತದೆ.

ಲೀಫ್

ಮಕ್ಕಳಿಲ್ಲದ ನೋಡ್ ಅನ್ನು ಮರದ ಎಲೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಯಲ್ಲಿ, ಎಲೆಗಳು ಡಿ, ಇ, ಎಫ್, ಜಿ, ಐ, ಜೆ, ಕೆ ನೋಡ್ಗಳಾಗಿರುತ್ತವೆ.

ಇದು ಮೂಲ ಪರಿಭಾಷೆ. ಇತರ ಪರಿಕಲ್ಪನೆಗಳನ್ನು ಮತ್ತಷ್ಟು ಚರ್ಚಿಸಲಾಗುವುದು. ಆದ್ದರಿಂದ, ಬೈನರಿ ಮರವು ಒಂದು ಮರವಾಗಿದೆ, ಇದರಲ್ಲಿ ಪ್ರತಿ ನೋಡ್‌ನಲ್ಲಿ ಎರಡು ಮಕ್ಕಳಿಗಿಂತ ಹೆಚ್ಚಿಲ್ಲ. ನೀವು ಊಹಿಸಿದಂತೆ, ಉದಾಹರಣೆಯಿಂದ ಮರವು ಬೈನರಿ ಆಗಿರುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ನೋಡ್ಗಳು 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 ಅಂಶಗಳಿದ್ದರೆ, ಇದರರ್ಥ 2 ಹಂತಗಳಿಗೆ 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;
                    }
                }
            }
        }
    }

ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಪ್ರಸ್ತುತ ನೋಡ್ಗೆ ಹೆಚ್ಚುವರಿಯಾಗಿ, ಪ್ರಸ್ತುತ ನೋಡ್ನ ಪೋಷಕರ ಬಗ್ಗೆ ಮಾಹಿತಿಯನ್ನು ಸಂಗ್ರಹಿಸುವುದು ಅವಶ್ಯಕ. ಪ್ರಸ್ತುತವು ಶೂನ್ಯಕ್ಕೆ ಸಮಾನವಾದಾಗ, ಮೂಲ ವೇರಿಯಬಲ್ ನಮಗೆ ಅಗತ್ಯವಿರುವ ಹಾಳೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ.
ಅಳವಡಿಕೆಯ ದಕ್ಷತೆಯು ನಿಸ್ಸಂಶಯವಾಗಿ ಹುಡುಕಾಟದಂತೆಯೇ ಇರುತ್ತದೆ - O(log(n)).

ಅಳಿಸಿ

ತೆಗೆದುಹಾಕುವಿಕೆಯು ಮರದ ಮೇಲೆ ನಿರ್ವಹಿಸಬೇಕಾದ ಅತ್ಯಂತ ಕಷ್ಟಕರವಾದ ಕಾರ್ಯಾಚರಣೆಯಾಗಿದೆ. ಮೊದಲು ನಾವು ಅಳಿಸಲು ಹೊರಟಿರುವ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು ಎಂಬುದು ಸ್ಪಷ್ಟವಾಗಿದೆ. ಆದರೆ ನಂತರ ಏನು? ನಾವು ಅದರ ಉಲ್ಲೇಖವನ್ನು ಶೂನ್ಯಕ್ಕೆ ಹೊಂದಿಸಿದರೆ, ಈ ನೋಡ್ ಮೂಲವಾಗಿರುವ ಉಪಟ್ರೀಯ ಮಾಹಿತಿಯನ್ನು ನಾವು ಕಳೆದುಕೊಳ್ಳುತ್ತೇವೆ. ಮರ ತೆಗೆಯುವ ವಿಧಾನಗಳನ್ನು ಮೂರು ಪ್ರಕರಣಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ.

ಮೊದಲ ಪ್ರಕರಣ. ಅಳಿಸಲಾಗುತ್ತಿರುವ ನೋಡ್‌ಗೆ ಮಕ್ಕಳಿಲ್ಲ

ಅಳಿಸಲಾದ ನೋಡ್‌ಗೆ ಮಕ್ಕಳಿಲ್ಲದಿದ್ದರೆ, ಅದು ಎಲೆ ಎಂದು ಅರ್ಥ. ಆದ್ದರಿಂದ, ನೀವು ಅದರ ಪೋಷಕರ ಎಡ ಚೈಲ್ಡ್ ಅಥವಾ ರೈಟ್ ಚೈಲ್ಡ್ ಕ್ಷೇತ್ರಗಳನ್ನು ಶೂನ್ಯಕ್ಕೆ ಹೊಂದಿಸಬಹುದು.

ಎರಡನೇ ಪ್ರಕರಣ. ಅಳಿಸಬೇಕಾದ ನೋಡ್ ಒಂದು ಮಗುವನ್ನು ಹೊಂದಿದೆ

ಈ ಪ್ರಕರಣವೂ ತುಂಬಾ ಸಂಕೀರ್ಣವಾಗಿಲ್ಲ. ನಮ್ಮ ಉದಾಹರಣೆಗೆ ಹಿಂತಿರುಗಿ ನೋಡೋಣ. ನಾವು ಕೀ 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());
        }
    }

ತೀರ್ಮಾನಕ್ಕೆ

ಅಂತಿಮವಾಗಿ! ನಾನು ಏನನ್ನೂ ವಿವರಿಸದಿದ್ದರೆ ಅಥವಾ ಯಾವುದೇ ಕಾಮೆಂಟ್‌ಗಳನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ, ದಯವಿಟ್ಟು ಅವುಗಳನ್ನು ಕಾಮೆಂಟ್‌ಗಳಲ್ಲಿ ಬಿಡಿ. ಭರವಸೆ ನೀಡಿದಂತೆ, ನಾನು ಸಂಪೂರ್ಣ ಕೋಡ್ ಅನ್ನು ಒದಗಿಸುತ್ತೇನೆ.

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