ਬਾਈਨਰੀ ਟ੍ਰੀ ਜਾਂ ਬਾਈਨਰੀ ਖੋਜ ਟ੍ਰੀ ਕਿਵੇਂ ਤਿਆਰ ਕਰਨਾ ਹੈ

ਪ੍ਰੀਤ ਕਰੋ

ਇਹ ਲੇਖ ਬਾਈਨਰੀ ਖੋਜ ਰੁੱਖਾਂ ਬਾਰੇ ਹੈ। ਮੈਂ ਹਾਲ ਹੀ ਵਿੱਚ ਇਸ ਬਾਰੇ ਇੱਕ ਲੇਖ ਕੀਤਾ ਹਫਮੈਨ ਵਿਧੀ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ ਡੇਟਾ ਕੰਪਰੈਸ਼ਨ. ਉੱਥੇ ਮੈਂ ਬਾਈਨਰੀ ਰੁੱਖਾਂ 'ਤੇ ਜ਼ਿਆਦਾ ਧਿਆਨ ਨਹੀਂ ਦਿੱਤਾ, ਕਿਉਂਕਿ ਖੋਜ, ਸੰਮਿਲਨ ਅਤੇ ਮਿਟਾਉਣ ਦੇ ਤਰੀਕੇ ਢੁਕਵੇਂ ਨਹੀਂ ਸਨ। ਹੁਣ ਮੈਂ ਰੁੱਖਾਂ ਬਾਰੇ ਇੱਕ ਲੇਖ ਲਿਖਣ ਦਾ ਫੈਸਲਾ ਕੀਤਾ. ਆਓ ਸ਼ੁਰੂ ਕਰੀਏ।

ਇੱਕ ਰੁੱਖ ਇੱਕ ਡੇਟਾ ਢਾਂਚਾ ਹੁੰਦਾ ਹੈ ਜਿਸ ਵਿੱਚ ਕਿਨਾਰਿਆਂ ਦੁਆਰਾ ਜੁੜੇ ਨੋਡ ਹੁੰਦੇ ਹਨ। ਅਸੀਂ ਕਹਿ ਸਕਦੇ ਹਾਂ ਕਿ ਇੱਕ ਰੁੱਖ ਇੱਕ ਗ੍ਰਾਫ ਦਾ ਇੱਕ ਵਿਸ਼ੇਸ਼ ਕੇਸ ਹੈ. ਇੱਥੇ ਇੱਕ ਉਦਾਹਰਨ ਰੁੱਖ ਹੈ:

ਇਹ ਇੱਕ ਬਾਈਨਰੀ ਖੋਜ ਰੁੱਖ ਨਹੀਂ ਹੈ! ਸਭ ਕੁਝ ਕੱਟਿਆ ਗਿਆ ਹੈ!

ਪਰਿਭਾਸ਼ਾ

ਰੂਟ

ਰੁੱਖ ਦੀ ਜੜ੍ਹ - ਇਹ ਇਸਦਾ ਸਭ ਤੋਂ ਉੱਚਾ ਨੋਡ ਹੈ। ਉਦਾਹਰਨ ਵਿੱਚ, ਇਹ ਨੋਡ ਏ ਹੈ। ਇੱਕ ਰੁੱਖ ਵਿੱਚ, ਸਿਰਫ਼ ਇੱਕ ਮਾਰਗ ਰੂਟ ਤੋਂ ਕਿਸੇ ਹੋਰ ਨੋਡ ਤੱਕ ਲੈ ਜਾ ਸਕਦਾ ਹੈ! ਵਾਸਤਵ ਵਿੱਚ, ਕਿਸੇ ਵੀ ਨੋਡ ਨੂੰ ਇਸ ਨੋਡ ਦੇ ਅਨੁਸਾਰੀ ਸਬਟ੍ਰੀ ਦਾ ਮੂਲ ਮੰਨਿਆ ਜਾ ਸਕਦਾ ਹੈ।

ਮਾਤਾ-ਪਿਤਾ/ਔਲਾਦ

ਰੂਟ ਨੂੰ ਛੱਡ ਕੇ ਸਾਰੇ ਨੋਡਾਂ ਦਾ ਬਿਲਕੁਲ ਇੱਕ ਕਿਨਾਰਾ ਦੂਜੇ ਨੋਡ ਵੱਲ ਜਾਂਦਾ ਹੈ। ਮੌਜੂਦਾ ਦੇ ਉੱਪਰ ਸਥਿਤ ਨੋਡ ਨੂੰ ਕਿਹਾ ਜਾਂਦਾ ਹੈ ਮਾਤਾ-ਪਿਤਾ ਇਹ ਨੋਡ. ਮੌਜੂਦਾ ਨੋਡ ਦੇ ਹੇਠਾਂ ਸਥਿਤ ਅਤੇ ਇਸ ਨਾਲ ਜੁੜਿਆ ਇੱਕ ਨੋਡ ਕਿਹਾ ਜਾਂਦਾ ਹੈ ਵੰਸ਼ਜ ਇਹ ਨੋਡ. ਆਓ ਇੱਕ ਉਦਾਹਰਣ ਦੀ ਵਰਤੋਂ ਕਰੀਏ. ਚਲੋ ਨੋਡ ਬੀ ਲੈਂਦੇ ਹਾਂ, ਫਿਰ ਇਸਦੇ ਮਾਤਾ-ਪਿਤਾ ਨੋਡ ਏ ਹੋਣਗੇ, ਅਤੇ ਇਸਦੇ ਬੱਚੇ ਨੋਡ ਡੀ, ਈ ਅਤੇ ਐੱਫ ਹੋਣਗੇ।

ਲੀਫ

ਇੱਕ ਨੋਡ ਜਿਸ ਦੇ ਕੋਈ ਬੱਚੇ ਨਹੀਂ ਹਨ, ਨੂੰ ਰੁੱਖ ਦਾ ਪੱਤਾ ਕਿਹਾ ਜਾਵੇਗਾ। ਉਦਾਹਰਨ ਵਿੱਚ, ਪੱਤੇ 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;

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

ਸਾਨੂੰ ਸਿਰਫ ਇੱਕ ਕਲਾਸ ਫੀਲਡ ਦੇ ਰੂਪ ਵਿੱਚ ਟ੍ਰੀ ਦੇ ਰੂਟ ਦੀ ਲੋੜ ਹੈ, ਕਿਉਂਕਿ ਰੂਟ ਤੋਂ, 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 'ਤੇ ਸੈੱਟ ਕਰਦੇ ਹਾਂ, ਤਾਂ ਅਸੀਂ ਉਸ ਸਬਟ੍ਰੀ ਬਾਰੇ ਜਾਣਕਾਰੀ ਗੁਆ ਦੇਵਾਂਗੇ ਜਿਸ ਦਾ ਇਹ ਨੋਡ ਰੂਟ ਹੈ। ਰੁੱਖਾਂ ਨੂੰ ਹਟਾਉਣ ਦੇ ਤਰੀਕਿਆਂ ਨੂੰ ਤਿੰਨ ਮਾਮਲਿਆਂ ਵਿੱਚ ਵੰਡਿਆ ਗਿਆ ਹੈ।

ਪਹਿਲਾ ਕੇਸ. ਮਿਟਾਏ ਜਾ ਰਹੇ ਨੋਡ ਦਾ ਕੋਈ ਬੱਚਾ ਨਹੀਂ ਹੈ

ਜੇਕਰ ਮਿਟਾਏ ਜਾ ਰਹੇ ਨੋਡ ਦੇ ਕੋਈ ਬੱਚੇ ਨਹੀਂ ਹਨ, ਤਾਂ ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਇਹ ਇੱਕ ਪੱਤਾ ਹੈ। ਇਸਲਈ, ਤੁਸੀਂ ਬਸ ਇਸਦੇ ਪੇਰੈਂਟ ਦੇ ਲੈਫਟਚਾਈਲਡ ਜਾਂ ਰਾਈਟਚਾਈਲਡ ਫੀਲਡ ਨੂੰ 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))

ਸਮਮਿਤੀ ਬਾਈਪਾਸ

ਟ੍ਰੈਵਰਸਲ ਇਸ ਨਾਲ ਕੁਝ ਕਾਰਵਾਈ ਕਰਨ ਲਈ ਰੁੱਖ ਦੇ ਹਰੇਕ ਨੋਡ ਦਾ ਦੌਰਾ ਕਰ ਰਿਹਾ ਹੈ।

ਆਵਰਤੀ ਸਮਮਿਤੀ ਟ੍ਰਾਵਰਸਲ ਐਲਗੋਰਿਦਮ:

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). ਇਹ ਸਭ ਤੋਂ ਮਹੱਤਵਪੂਰਨ ਹੈ, ਮੇਰੀ ਰਾਏ ਵਿੱਚ, ਬਾਈਨਰੀ ਰੁੱਖਾਂ ਦੇ ਨੁਕਸਾਨ.

ਸਿਰਫ਼ ਰਜਿਸਟਰਡ ਉਪਭੋਗਤਾ ਹੀ ਸਰਵੇਖਣ ਵਿੱਚ ਹਿੱਸਾ ਲੈ ਸਕਦੇ ਹਨ। ਸਾਈਨ - ਇਨ, ਤੁਹਾਡਾ ਸੁਆਗਤ ਹੈ.

ਮੈਂ ਬਹੁਤ ਲੰਬੇ ਸਮੇਂ ਤੋਂ ਹੱਬ 'ਤੇ ਨਹੀਂ ਹਾਂ, ਅਤੇ ਮੈਂ ਜਾਣਨਾ ਚਾਹਾਂਗਾ ਕਿ ਤੁਸੀਂ ਕਿਹੜੇ ਵਿਸ਼ਿਆਂ 'ਤੇ ਹੋਰ ਲੇਖ ਦੇਖਣਾ ਚਾਹੋਗੇ?

• ਡਾਟਾ ਬਣਤਰ

• ਐਲਗੋਰਿਦਮ (ਡੀਪੀ, ਰੀਕਰਸ਼ਨ, ਡੇਟਾ ਕੰਪਰੈਸ਼ਨ, ਆਦਿ)

• ਅਸਲ ਜੀਵਨ ਵਿੱਚ ਡੇਟਾ ਢਾਂਚੇ ਅਤੇ ਐਲਗੋਰਿਦਮ ਦੀ ਵਰਤੋਂ

• Java ਵਿੱਚ ਪ੍ਰੋਗ੍ਰਾਮਿੰਗ ਐਂਡਰਾਇਡ ਐਪਲੀਕੇਸ਼ਨ

• Java ਵਿੱਚ ਪ੍ਰੋਗਰਾਮਿੰਗ ਵੈੱਬ ਐਪਲੀਕੇਸ਼ਨ

2 ਉਪਭੋਗਤਾਵਾਂ ਨੇ ਵੋਟ ਦਿੱਤੀ। 1 ਵਰਤੋਂਕਾਰ ਬਚਿਆ।

ਸਰੋਤ: www.habr.com