qq_40586164
Owl丶
2020-03-02 11:31

二叉搜索树删除结点时指针问题(邓俊辉数据结构)

10
  • c++

新手学习数据结构时遇到了些问题,想请教各位大佬。
在看清华大学邓俊辉网课数据结构 二叉搜索树删除结点时 看到这样一段代码:

#define BinNodePosi(T) BinNode<T>*//节点位置

template <typename T> BinNodePosi(T) & BST<T>::search ( const T & e ) { //在BST中查找关键码e
   if ( !_root || e == _root->data ) { 
       _hot = NULL; 
       return _root; 
   } //在树根v处命中
   for ( _hot = _root; ; ) { //自顶而下
      BinNodePosi(T) & c = ( e < _hot->data ) ? _hot->lc : _hot->rc; //确定方向
      if ( !c || e == c->data ) 
          return c; 
      _hot = c; //命中返回,或者深入一层
   } //无论命中或失败,hot均指向v之父亲(或为NULL)
} //返回目标节点位置的引用,以便后续插入、删除操作

template <typename T> bool BST<T>::remove ( const T& e ) { //从BST树中删除关键码e
   BinNodePosi(T) & x = search ( e ); 
   if ( !x ) return false; //确认目标存在(留意_hot的设置)
   removeAt ( x, _hot ); 
   _size--; //实施删除
   updateHeightAbove ( _hot ); //更新_hot及其历代祖先的高度
   return true;
} //删除成功与否,由返回值指示

template <typename T>
static BinNodePosi(T) removeAt ( BinNodePosi(T) & x, BinNodePosi(T) & hot ) {
   BinNodePosi(T) w = x; //实际被摘除的节点,初值同x
   BinNodePosi(T) succ = NULL; //实际被删除节点的接替者
   if ( !HasLChild ( *x ) ) //若*x的左子树为空,则可
      succ = x = x->rc; //直接将*x替换为其右子树
   else if ( !HasRChild ( *x ) ) //若右子树为空,则可
      succ = x = x->lc; //对称地处理——注意:此时succ != NULL
   else { //若左右子树均存在,则选择x的直接后继作为实际被摘除节点,为此需要
      w = w->succ(); //(在右子树中)找到*x的直接后继*w
      swap ( x->data, w->data ); //交换*x和*w的数据元素
      BinNodePosi(T) u = w->parent;
      ( ( u == x ) ? u->rc : u->lc ) = succ = w->rc; //隔离节点*w
   }
   hot = w->parent; //记录实际被删除节点的父亲
   if ( succ ) 
       succ->parent = hot; //并将被删除节点的接替者与hot相联
   release ( w->data ); 
   release ( w ); 
   return succ; //释放被摘除节点,返回接替者
} //release()负责释放复杂结构,与算法无直接关系,具体实现详见代码包

仅讨论第三部分remove_At函数第6行 删除的结点x只有右子树的情况,假设y为x的父节点,并且x是y的右子树,那么第6行只做了x=x->rc仅用子树将其覆盖,为什么不需要将y->rc=x->rc?
x的父节点的成员rc,保存的不应该是x的值吗?x变化了,但是y->rc保存的值并没有变吧?

问题大概可以简单概括为,假设y为x右孩子节点(x,y,z为节点指针),z为y右孩子节点。
如果用y=y->rchild,那此时 x->rchild到底变没变?
我的理解是x->rchild应该是原y的值,y被重新赋值后,x->child还是原来的值,没有变。
但这个理解好像错了,请问错在哪?

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

2条回答