java - robert sedgwick的红黑树的delete操作是什么思路?
阿神
阿神 2017-04-18 09:35:17
0
2
423
阿神
阿神

闭关修行中......

모든 응답 (2)
伊谢尔伦

我想明白这个问题了...这个是我模拟标准实现写的代码, 标准实现是先确定红黑树中存在该元素,然后删除; 我的则是直接删除,不管存不存在. 暂时还没有测试, 不过和标准代码实现基本一致

public void delete(int num) { if(root == null) return ; if(!isRed(root.left) && !isRed(root.right)) root.color = RED ; root = delete(root , num) ; if(root != null) root.color = BLACK ; } private Node delete(int key , Node node){ if(node == null) return null ; int cmp = node.key - key ; if(cmp > 0) //说明在他的左子树上 { //说明是一个2-节点, 需要从右子树上借一个给他 if(node.left != null && !isRed(node.left) && !isRed(node.left.left)) node = moveRedLeft(node) ; node.left = delete(node.left , key) ; } else //说明key在右子树上 { if(isRed(node.left))//说明该节点本身就是3-节点, 直接分一个给右子树即可 node = rotateRight(node) ; if(cmp == 0 && node.right == null) return null ; //如果右节点是一个2-节点, 那么就从左子树上借一个给他 if(node.right != null && !isRed(node.right) && !isRed(node.right.left)) node = moveRedRight(node) ; //cmp失效, 重新计算 cmp = node.key-key ; if(cmp == 0) { //和普通二叉树的删除相同, 将右子树的最小节点放在这个节点的位置 Node x = min(node.right) ; node.key = x.key ; node.value = x.value ; //将原来的最小节点删除 node.right = deleteMin(node.right) ; } else { node.right = delete(node.right , key) ; } } //维持红黑树的性质 return balance(node) ; }

删除的思路和删除最小值最大值的思路类似, 之前的思维局限于如何模拟2-3树的删除而导致没有认清楚他们之间的关系...

    阿神

    想问楼主一个问题
    在delete中当要向右分支移动的过程中调用了moveRedRight的方法
    请问 为什么moveRedRight方法中
    node = rotateRight(node);
    flipColors(node) ;
    这两步执行之后为什么不需要进行左旋转呢
    按理说此时的node.right.right的color是红色,node.right.left的color是黑色,(这一行的node是delete方法中传入的node)这时候不应该进行左旋吗?

      최신 다운로드
      더>
      웹 효과
      웹사이트 소스 코드
      웹사이트 자료
      프론트엔드 템플릿
      회사 소개 부인 성명 Sitemap
      PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!