0

https://www.geeksforgeeks.org/split-a-bst-into-two-balanced-bsts-based-on-a-value-k/?ref=leftbar-rightbar

こちらのコードを用いてBSTを分割する際の計算量は、O(h)(hはツリーの高さ)ということは直感的には理解できるのですが、どうしても具体的に証明する方法がわかりません。お力を貸していただけると嬉しいです。

以下上のサイトより部分的にコードを引用します。

// Function to split the BST 
// into two Balanced BST 
void splitBST(node* root, int k) 
{ 

    // Print the original BST 
    cout << "Original BST : "; 
    if (root != NULL) { 
        inorderTrav(root); 
    } 
    else { 
        cout << "NULL"; 
    } 
    cout << endl; 

    // Store the size of BST1 
    int numNode = sizeOfTree(root); 

    // Take auxiliary array for storing 
    // The inorder traversal of BST1 
    int inOrder[numNode + 1]; 
    int index = 0; 

    // Function call for storing 
    // inorder traversal of BST1 
    storeInorder(root, inOrder, index); 

    // Function call for getting 
    // splitting index 
    int splitIndex 
        = getSplittingIndex(inOrder, 
                            index, k); 

    node* root1 = NULL; 
    node* root2 = NULL; 

    // Creation of first Balanced 
    // Binary Search Tree 
    if (splitIndex != -1) 
        root1 = createBST(inOrder, 0, 
                          splitIndex); 

    // Creation of Second Balanced 
    // Binary Search Tree 
    if (splitIndex != (index - 1)) 
        root2 = createBST(inOrder, 
                          splitIndex + 1, 
                          index - 1); 

    // Print two Balanced BSTs 
    cout << "First BST : "; 
    if (root1 != NULL) { 
        inorderTrav(root1); 
    } 
    else { 
        cout << "NULL"; 
    } 
    cout << endl; 

    cout << "Second BST : "; 
    if (root2 != NULL) { 
        inorderTrav(root2); 
    } 
    else { 
        cout << "NULL"; 
    } 
}

1 件の回答 1

1

O(h)(hはツリーの高さ)ではないです。
一旦通りがけ順に要素を列挙した後、その要素を二つの二分探索木に分割してるのでO(N)(Nはツリーのサイズ)です。
一般的な分割の方法では、それぞれの部分木に対して右か左の一方の子を再帰的に分割して、それを定数時間でマージするのでO(h)(hはツリーの高さ)になります。ただしバランスはとれません。

1
  • 勘違いしていました。ありがとうございます。
    – Avril
    Commented 2020年5月25日 5:02

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。