붉 은 검 은 나무 에 대해

7247 단어
hashmap 의 처리 에는 붉 은 검 은 나무의 참여 가 있 습 니 다. 붉 은 검 은 나 무 를 알 아 봤 습 니 다.
붉 은 검 은 나 무 는 '완전한 균형' 을 추구 하지 않 는 다. 그것 은 부분적으로 균형 요 구 를 달성 하고 회전 에 대한 요 구 를 낮 추어 성능 을 향상 시킨다.
빨 간 검 은 나 무 는 O (log 2 n) 의 시간 복잡 도 로 검색, 삽입, 삭제 작업 을 할 수 있 습 니 다.그 밖 에 디자인 으로 인해 어떠한 불 균형 도 세 번 의 회전 안에서 해결 된다.물론 더 좋 은 것 도 있 지만 실현 하면 더욱 복잡 한 데이터 구 조 는 한 걸음 회전 안에 균형 을 이 룰 수 있 지만 빨 간 검 은 나 무 는 우리 에 게 비교적 저렴 한 해결 방안 을 줄 수 있다.레 드 블랙 트 리 는 알고리즘 시간 복잡 도가 AVL 과 같 지만 통계 성능 은 AVL 트 리 보다 높다.
물론 붉 은 검 은 나 무 는 모든 응용 나무의 영역 에 적응 하지 못 한다.만약 데이터 가 기본적으로 정적 이 라면 그들 이 삽입 할 수 있 고 균형 에 영향 을 주지 않 는 곳 에 있 게 하 는 것 이 더욱 좋 은 성능 을 가 질 것 이다.만약 데이터 가 완전히 정적 이 라면, 예 를 들 어 해시 표를 만 들 면 성능 이 좀 더 좋 을 것 이다.
다음은 자바 로 추가 및 삭제 작업 을 마 쳤 습 니 다.
기본: * 레 드 블랙 트 리 의 노드 (x) 를 왼쪽 회전 * * 왼쪽 회전 설명도 (노드 x 를 왼쪽 회전): * root * / * x p * / \ - (왼쪽 회전) -. / * lx p x rp * / * lp rp lx lp * * / private > void right Rotate (TreeNode x, TreeNode root) {TreeNode p = x. right; if (p. left! = null) {p. left. parent = x;} if(x. parent = = null) {root = p; / x 가 루트 노드 일 때} else {if (x. parent. left = = x) x. parent. left = p; else x. parent. right = p;} p. left = x; x. parent = p;}
우회전: / *
  • 검 붉 은 나무의 노드 (x) 를 우 회전
  • 우회전 설명도 (노드 x 를 좌회전):
  •        py                               py
    
  •       /                                /
    
  •      x                               p
    
  •     /  \      --(  )-.>>          /  \
    
  •    p   rx                           lp   x
    
  •   / \                                   / \
    
  •  lp  rp                                rp  rx
    

  • * / private > void left Rotate (TreeNode x, TreeNode root) {TreeNode p = x. right; if (p. right! = null) {x. left = p. right;} if (p. right! = null) {p. right. parent = x;} if (x. parent = = null) {root = p; / / x 가 루트 노드 일 때} else {if (x. parent. right = x) x. parent. let = p; else x. parent. right = p;}
    삽입:
     * 1.           ,     
     * 2.          
     * 3.              
     *      :
     *         ,     。
     *      。
     *         。 [  :      ,         !]
     *          ,            。
     *                               。
     * @param n
     * @param root    
     * @param 
     * @param 
     */
    private   > void  insert(TreeNode n,TreeNode root){
        while (root != null) {
            if (n.key.compareTo(root.key) < 0)
                root =root.left;
            else
                root= root.right;
        }
        TreeNode p=null;
        if(root==null){
            root=n;
        }else {
             p = root.parent;
        }
        n.parent=p;
        n.red=true;
        //   
        if(n.key.compareTo(p.key)>0){
            p.right=n;
        }else {
            p.left=n;
        }
        insertRedTree(n,root);
    }
    
    private  > void insertRedTree(TreeNode n,TreeNode root) {
        TreeNode parent=n.parent;
        //             
        if(n.parent==null){
            n.red=false;
        }
        while((parent=n.parent)!=null&&parent.red){
    
            TreeNode gParent=n.parent.parent;
            //                     
            if(gParent.left.red&&gParent.right.red||(gParent.left.red&&gParent.right!=null)||(gParent.right.red&&gParent.left!=null)){
                gParent.right.red=false;
                gParent.left.red=false;
                gParent.red=true;
                n=gParent;
                continue;
            }
            //        ,         
            if(n==parent.right){
                n=parent;
                parent=n.parent;
                n.leftRotate(n,root);
    
            }else{
                //        ,         
                parent.red=false;
                gParent.red=true;
                n.rightRotate(gParent,root);
    
            }
        }
        root.red=false;
    }
    

    삭제:
    private > void remove (TreeNode n, TreeNode root) {TreeNode child, parent; if (n. left! = null & n. right! = null) {/ 삭 제 된 노드 에 두 아들 이 있 습 니 다.. / / 여기 서 후계 노드 는 대역 에 해당 합 니 다. / / 후계 노드 의 내용 을 '삭 제 된 노드' 에 복사 한 후 / / 후계 노드 를 삭제 합 니 다. 이렇게 하면 문 제 를 '후계 노드 삭제' 로 교묘 하 게 변환 합 니 다. TreeNode replace = n; / / 후계 노드 replace = replace. right; while (replace. left! = null) {replace = replace. left;}/ * * * * O * / * x y * / * p rx * / \ / * lp rp a b * * x 의 후계 결점 은 a * / if (n. parent = = null) {root = replace;} else {if (n. parent. left = = n) {n. parent. left = replace;} else {n. parent. right = replace;}}child = replace. right; parent = replace. parent; boolean color = replace. red; / 후계 노드 를 덮어 서 삭제 한 값 입 니 다. 후계 노드 의 right 를 parent 에 if (parent = = n) {parent = replace;} else {if (child! = null) {child. parent = parent; parent. left = child; replace. right = n. right; n. right. parent = replace;}}/ / 속성 은 모두 replace. parent = n. parent; replace. red = n. red; replace. left = n. left; n. left. parent = replace; / 원래 색상 이 검은색 if (! color) {/ / 빨간색 검 은 나무의 특성 유지 removeRedTree (child, parent, root);} n = null; return;}
        //           。  ,       ,                 。
        if (n.left !=null) {
            child = n.left;
        } else {
            child = n.right;
        }
    
        parent = n.parent;
        //   "    "   
         boolean color = n.red;
    
        if (child!=null)
            child.parent = parent;
    
        // "node  "     
        if (parent!=null) {
            if (parent.left == n)
                parent.left = child;
            else
                parent.right = child;
        } else {
            root = child;
        }
    
        if (color == false)
            removeRedTree(child, parent,root);
           n = null;
    
    
    }
    
    private > void removeRedTree(TreeNode n, TreeNode parent, TreeNode root) {
        TreeNode p;
        while((n==null||n.red)&&n.parent!=null) {
            if (parent.left == n)
                p = parent.right;
            else p=parent.left;
                //x “ + ”  ,x        。
                if (p.red) {
                    p.red=false;
                    parent.red=true;
                    p.leftRotate(parent,root);
                    p= parent.right;
                }
                // x “ + ”  ,x        ,x              。
                if ((p.left==null || !p.left.red) &&
                        (p.right==null || !p.right.red)) {
                    p.red=true;
                    n = parent;
                    parent = n.parent;
                }
                else {
                    //x “ + ”  ,x        ;x            ,       。
                    if (p.right==null || !(p.right.red)) {
                        p.left.red=false;
                        p.red=true;
                        p.rightRotate(p,root);
                        p = parent.right;
                    }
                    //x “ + ”  ,x        ;x             ,x             。
                    p.red=p.parent.red;
                    p.parent.red=false;
                    p.right.red=false;
                    p.leftRotate(parent,root);
                    n=root;
                    break;
                }
    
        }
    
    }
    

    이 글 은 인터넷 의 실현 을 참고 하여 소스 코드 를 읽 는 것 은 우리 가 대신 분 야 를 이해 하 는 큰 지름길 이다. 생명 이 멈 추 지 않 고 분투 하 는 것 이 그 치지 않 는 다.

    좋은 웹페이지 즐겨찾기