acwing::acwing3786 命名空间参考

1. 二叉排序树

更多...

函数
int	get_pre (TreeNode *root, int x)
int	get_suc (TreeNode *root, int x)
void	insert (TreeNode *&root, int x)
int	main (istream &cin, ostream &cout)
void	remove (TreeNode *&root, int x)
	TEST (acwing3786, case1)
	TEST (acwing3786, case2)

变量
const int	INF = 2e9
TreeNode *	root = nullptr

详细描述

1. 二叉排序树

函数说明

get_pre()

int acwing::acwing3786::get_pre	(	TreeNode *	root,
		int	x )

在文件 acwing408.cpp 第 508 行定义.

                                           {
            if(!root)
                return -INF;
            if(root->val >= x)
                return get_pre(root->left, x);
            else
                return max(root->val, get_pre(root->right, x));
        }

引用了 get_pre(), INF , 以及 root.

被这些函数引用 get_pre() , 以及 main().

get_suc()

int acwing::acwing3786::get_suc	(	TreeNode *	root,
		int	x )

在文件 acwing408.cpp 第 518 行定义.

                                           {
            if(!root)
                return INF;
            if(root->val <= x)
                return get_suc(root->right, x);
            else
                return min(root->val, get_suc(root->left, x));
        }

引用了 get_suc(), INF , 以及 root.

被这些函数引用 get_suc() , 以及 main().

insert()

void acwing::acwing3786::insert	(	TreeNode *&	root,
		int	x )

在文件 acwing408.cpp 第 460 行定义.

                                            {
            /*
        1. 递归找到x的待插入的位置
        2. 如果x < 当前root就递归到左子树，反之，递归到右子树。
    */
            if(!root)
                root = new TreeNode(x);
            // 如果发现数值相同的话就判断一下;
            if(root->val == x)
                return;
            else if(x < root->val)
                insert(root->left, x);
            else
                insert(root->right, x);
        }

引用了 insert() , 以及 root.

被这些函数引用 insert() , 以及 main().

main()

int acwing::acwing3786::main	(	istream &	cin,
		ostream &	cout )

在文件 acwing408.cpp 第 441 行定义.

                                              {
            int n;
            cin >> n;
            while(n--) {
                int t, x;
                cin >> t >> x;
                if(t == 1)
                    insert(root, x);
                else if(t == 2)
                    remove(root, x);
                else if(t == 3)
                    cout << get_pre(root, x) << endl;
                else
                    cout << get_suc(root, x) << endl;
            }
            return 0;
        }

引用了 get_pre(), get_suc(), insert(), remove() , 以及 root.

被这些函数引用 TEST() , 以及 TEST().

remove()

void acwing::acwing3786::remove	(	TreeNode *&	root,
		int	x )

在文件 acwing408.cpp 第 476 行定义.

                                            {
            /*
        1. 待删除的结点只有左子树。立即可推出，左子树上的结点都是小于待删除的结点的，我们只需要把待删除结点删了然后左子树接上待删除结点的父节点就可以了。
        2. 待删除的结点只有右子树。立即可推出，右子树上的结点都是大于待删除的结点的，我们只需要把待删除结点删了然后右子树接上待删除结点的父节点就可以了。
        3. 待删除的结点既有左子树又有右子树。这个比上两个情况麻烦一点，但也不麻烦，需要读者理解的是，怎么能删除结点后还不改变中序遍历的结果，并且操作代价最小，显而易见，我们根据待删除结点的左子树可以得到最右下角的最后结点满足$<x$并且最接近x的结点，把这个结点覆盖待删除的结点，然后把这个结点删除，就完成了我们的操作。
    */
 
            // 如果不存在直接return
            if(!root)
                return;
            if(x < root->val)
                remove(root->left, x);
            else if(x > root->val)
                remove(root->right, x);
            else {
                if(!root->left && !root->right)
                    root = NULL;
                else if(!root->left)
                    root = root->right;
                else if(!root->right)
                    root = root->left;
                else {
                    auto p = root->left;
                    while(p->right)
                        p = p->right;
                    root->val = p->val;
                    remove(root->left, p->val);
                }
            }
        }

引用了 remove() , 以及 root.

被这些函数引用 main() , 以及 remove().

TEST() [1/2]

acwing::acwing3786::TEST	(	acwing3786	,
		case1	)

在文件 acwing408_test.cpp 第 969 行定义.

                                {
            istringstream in("6\n"
                             "1 1\n"
                             "1 3\n"
                             "1 5\n"
                             "3 4\n"
                             "2 3\n"
                             "4 2");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("3\n"
                      "5\n",
                      ans);
        }

引用了 main().

TEST() [2/2]

acwing::acwing3786::TEST	(	acwing3786	,
		case2	)

在文件 acwing408_test.cpp 第 985 行定义.

                                {
            istringstream in("20\n"
                             "1 -9\n"
                             "1 5\n"
                             "2 5\n"
                             "2 -9\n"
                             "1 -5\n"
                             "1 -4\n"
                             "4 -19\n"
                             "1 -10\n"
                             "2 -4\n"
                             "2 -10\n"
                             "1 -14\n"
                             "4 -17\n"
                             "4 -10\n"
                             "2 -14\n"
                             "1 -12\n"
                             "1 -3\n"
                             "3 -8\n"
                             "1 -7\n"
                             "4 -18\n"
                             "1 1");
            auto out = ostringstream();
            main(in, out);
            const auto ans = out.str();
            ASSERT_EQ("-5\n"
                      "-14\n"
                      "-5\n"
                      "-12\n"
                      "-12\n",
                      ans);
        }

引用了 main().

变量说明

INF

const int acwing::acwing3786::INF = 2e9

在文件 acwing408.cpp 第 439 行定义.

被这些函数引用 get_pre() , 以及 get_suc().

root

TreeNode* acwing::acwing3786::root = nullptr

在文件 acwing408.cpp 第 438 行定义.

被这些函数引用 get_pre(), get_suc(), insert(), main() , 以及 remove().