İkili axtarış ağacında ən aşağı ümumi əcdad

İkili axtarışın kökü verilmişdir ağac və iki n1 və n2 qovşaqları, verilmiş ikili axtarış ağacındakı qovşaqların LCA-nı (Ən Aşağı Ortaq Atadan) tapın.

misal

Pin

İkili axtarış ağacında ən aşağı ümumi əcdad üçün sadəlövh yanaşma

İçərisində LCA tapmaq üçün optimal yanaşmadan istifadə edərək LCA (n1, n2) tapın İkili ağacBST həm də ikili bir ağac olduğundan.

LCA tapmaq məcburiyyətində olduğumuz n1 və n2-nin ağacda olduğunu düşünsək, yuxarıdakı problem tək keçidlə həll edilə bilər.

Ağacdan keçin, hər qovşaq üçün dörd haldan birinə sahibik,

1. Mövcud node ya n1, ya da n2-dir, bu halda nodu qaytarırıq.
2. Cari düyünün alt ağaclarından biri n1, digəri n2 ehtiva edir, bu düyün LCA-dır, düyünü qaytarın.
3. Cari düyünün bir alt ağacı həm n1 həm də n2 ehtiva edir, alt ağacın qaytardığını qaytarırıq.
4. Alt ağacların heç birində n1 və n2 yoxdur, return null.

Zaman Mürəkkəbliyi = O (n), tək sürüşmə ilə 
burada n ağacdakı qovşaq sayıdır.

İkili axtarış ağacında ən aşağı ümumi əcdad üçün optimal yanaşma

BST xüsusiyyətlərindən istifadə edərək, LCA daha az vaxt mürəkkəbliyində tapıla bilər.

1. BST-ni kökdən başlayaraq keçin (curr-u kök kimi başladın).
2. Cari düyünün dəyəri n1 və n2 (ikisi daxil olmaqla) arasındadırsa, bu LCA-dır.
3. Düyünün dəyəri həm n1, həm də n2-dən azdırsa, LCA sağ yarıda mövcuddur (cərəyan əyri olur. Düz).
4. Başqa LCA sol yarıda mövcuddur (curr əyri olur. Sol).

Izahat

Yuxarıdakı şəkildəki BST-ni nəzərdən keçirin, LCA-nı tapaq (32, 40)

Kökdən başlayaraq ağacdan keçməyə başlayın.

• Cari düyünün dəyəri = 20
  20 <32 və 20 <40, LCA sağ alt ağacda mövcuddur
• Cari düyünün dəyəri = 24
  24 <32 və 20 <40, LCA sağ alt hissədə mövcuddur
• Cari düyünün dəyəri = 35
  35> = 32 və 35 <= 40, bu LCA'dır
  Yəni, LCA (32, 40) = 35

İkili axtarış ağacında ən aşağı ümumi əcdad üçün JAVA kodu

public class LCABST {
    // Class to represent a node in BST
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Function to return LCA of two nodes, and return -1 if LCA does not exist
    private static int LCA(Node root, int n1, int n2) {
        // No LCA for an empty tree
        if (root == null) {
            return -1;
        }

        // Traverse the tree starting from root
        Node curr = root;
        int lca = -1;
        while (curr != null) {
            if (curr.data < n1 && curr.data < n2) {
                // LCA is present in the right sub tree
                curr = curr.right;
            } else if (curr.data > n1 && curr.data > n2) {
                // LCA is present in left sub tree
                curr = curr.left;
            } else {
                lca = curr.data;
                break;
            }
        }

        // Return LCA
        return lca;
    }

    public static void main(String[] args) {
        // Constructing the BST in above example
        Node root = new Node(20);
        root.left = new Node(11);
        root.right = new Node(24);
        root.right.left = new Node(21);
        root.right.right = new Node(35);
        root.right.right.left = new Node(32);
        root.right.right.right = new Node(40);

        // Queries
        System.out.println(LCA(root, 24, 40));
        System.out.println(LCA(root, 11, 21));
        System.out.println(LCA(root, 32, 40));
    }
}

İkili axtarış ağacında ən aşağı ümumi əcdad üçün C ++ kodu

#include <iostream>
using namespace std;

// Class representing node of binary search tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

// Function to return LCA of two nodes, and return -1 if LCA does not exist
int LCA(Node *root, int n1, int n2) {
    // No LCA for an empty tree
    if (root == NULL) {
        return -1;
    }
    
    // Traverse the tree starting from root
    Node *curr = root;
    int lca = -1;
    while (curr != NULL) {
        if (curr->data < n1 && curr->data < n2) {
            // LCA is present in the right sub tree
            curr = curr->right;
        } else if (curr->data > n1 && curr->data > n2) {
            // LCA is present in left sub tree
            curr = curr->left;
        } else {
            lca = curr->data;
            break;
        }
    }
    
    // Return LCA
    return lca;
}

int main() {
  // Construct the tree shown in above example
    Node *root = newNode(20);
    root->left = newNode(11);
    root->right = newNode(24);
    root->right->left = newNode(21);
    root->right->right = newNode(35);
    root->right->right->left = newNode(32);
    root->right->right->right = newNode(40);
    
    // Queries
    cout<<LCA(root, 24, 40)<<endl;
    cout<<LCA(root, 11, 21)<<endl;
    cout<<LCA(root, 32, 40)<<endl;
    
    return 0;
}

24
20
35

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (h), burada h BST hündürlüyüdür

References