66949


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

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

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

[code]

    // 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"; 
        } 
    }
    
[/code]


CC BY-SA 4.0
2020-05-24T05:16:04.717
66939
2020-05-24T17:46:42.257
2020-05-24T12:10:36.007
19110
38330
question
アルゴリズム データ構造 計算量
二分探索木を分割する際の計算量


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


CC BY-SA 4.0
2020-05-24T17:46:42.257
66949
2020-05-24T17:46:42.257
33033
66939
answer