こちらのコードを用いて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";
}
}