从二叉搜索树中删除子树

在任务中，我们有以下输入数据：

6

-2 0 2

8 4 3

9 0 0

3 6 5

600

0 0 0

四

6 9 7 8

其中第一个数字是二叉搜索树中的顶点数，随后的行存储有关顶点的数据。第一个数字是顶点键，第二个是左孩子描述的行号，第三个是右孩子描述的行号，如果没有左孩子或右孩子，那么在它们应该被描述为 0。下一个数字是删除请求的数量。接下来是键 - 需要删除的子树的根。

在输出中，您需要在执行每个删除具有给定键的子树的请求后打印树中剩余顶点的数量。具有给定键的子树可能不存在。

在这种情况下，输出将如下所示。

5 4 4 1

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>

using namespace std;


ifstream in("input.txt");
ofstream out("output.txt");


struct data
{
    int value, left, right;
    bool is_delete;
};


vector <data> data_tree;

int nodes = 0;

void input()
{
    int size_tree;

    in >> size_tree;

    if (size != 0)
    {

        for (int i = 0; i < size_tree; i++)
        {
            data add;
            in >> add.value >> add.left >> add.right;

            add.is_delete = false;

            data_tree.push_back(add);
        }
    }
}


void remove(int index, int key)
{
    // если узел считается удаленным то не можем двигаться дальше
    if (data_tree[index].is_delete == true)return;

    // если узел равен нашему ключу то говорим, что он удален и выходим
    if (data_tree[index].value == key)
    {
        data_tree[index].is_delete = true;
        return;
    }

    // двигаемся дальше по дереву
    if (data_tree[index].left != 0)remove(data_tree[index].left - 1, key);

    if (data_tree[index].right != 0)remove(data_tree[index].right - 1, key);
 
    // считаем количество пройденных узлов
    nodes++;
}



void delete_sub_tree()
{
    int size_tree, key;
    in >> size_tree;

    // ввод запросов и удаление поддеревьев
    for (int i = 0; i < size_tree; i++)
    {
        nodes = 0;

        in >> key;

        remove(0, key);
        
        out << nodes << endl;
    }
}



int main()
{

    input();         // ввод данных

    delete_sub_tree(); // удаление поддеревьев

    in.close();
    out.close();
}

我没有构建二叉树，因为输入数据已经具有二叉搜索树的充分必要条件。（每个元素都有一个左右子引用）

我没有删除节点，因为它会改变节点在向量中的位置，这样会破坏树的结构，所以在删除的时候，它只是说带有节点的子树已经被删除（bool is_delete） .

问题是这个算法在处理大量数据时不能及时运行。从 65000 个顶点开始。我不知道如何加快这个算法。为了在树中找到具有给定键的节点，您需要从根开始遍历树（您想不出更快的）O（log（n））。也许 input() 会减慢程序的速度。