Skip to main content
なるべく質問文を見るだけで回答しやすくなるようにコード部分を部分的に引用してきました。
ソース リンク
nekketsuuu
  • 2.4万
  • 12
  • 53
  • 117

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

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

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

// 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"; 
    } 
}
タイトルだけでも略語を開きました
リンク
nekketsuuu
  • 2.4万
  • 12
  • 53
  • 117

BST 二分探索木を分割する際の計算量

ソース リンク
Avril
  • 117
  • 8

BSTを分割する際の計算量

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

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