在二叉搜索树中插入节点

Question

老师给了我们这个代码，在二叉搜索树中插入一个节点，但我不确定 $z.p=y$ 指令确实如此。如果没有它，算法不会工作吗？

abr_insert(T, z) //z is the node that must be inserted
    {
            y = NULL;
            x = T.root;
            while(x != NULL)
            {
                    y  = x;
                    if(z.key < x.key)
                            x = x.left;
                    else
                            x = x.right;
            }
            z.p = y; //here is the instruction that I don't understand
            if(y = NULL)
                T.root = z;
            else if(z.key < y,key)
                    y.left = z;
            else
                    y.right = z;
    }

Answer 1

看起来这个算法正在跟踪父指针。每个节点 N 有三个领域: N.left （左小孩）, N.right （正确的孩子），以及 N.p （家长）。变量 y 用于跟踪最近的父级，所以当我们从树上掉下来时（即何时 x == NULL）我们可以使用 y 作为新节点的父节点 z.