안 드 로 이 드 데이터 구조 08 - 레 드 블랙 트 리

데이터 구조 08 - 레 드 블랙 트 리
1. 붉 은 검 은 나무의 소개
레 드 블랙 트 리 (RBT) 는 노드 마다 색상 속성 을 가 진 밸 런 스 이 진 트 리 로 색상 이나 빨간색 또는 검은색 을 찾 습 니 다.다음 과 같은 성질 을 가진다.

  1:        ；
  2:      。
  3:   NULL        ，     。
  4:                。(                         )
  5:                            。

AVL 나 무 는 첨삭 효율 이 낮 아 붉 은 검 은 나무 가 나 왔 다.레 드 블랙 트 리 는 일반 이 진 트 리 보다 검색 효율 이 높 고 AVL 트 리 보다 낮 지만, 삭제 효율 은 AVL 트 리 보다 높 고 일반 이 진 트 리 보다 낮 습 니 다.
붉 은 검 은 나무의 응용: TreeMap, TreeSet
2. 붉 은 검 은 나무의 삽입
붉 은 검 은 나무의 삽입 은 두 단계 로 나 뉜 다. 균형 을 추가 하고 수정 하 는 것 이다.
여기에 새로 추 가 된 노드 를 A 로 기록 하고 A 의 부모 노드 를 B 로 기록 하 며 찾 은 최소 불 균형 서브 트 리 를 C 로 기록 합 니 다.
1. 추가
첫 번 째 단 계 는 두 갈래 검색 트 리 의 삽입 과 같 습 니 다.
2. 밸 런 스 수정
현재 노드 를 A 로 기록 하고 A 의 아버지 노드 를 B 로 기록 하 며 B 의 형제 노드 를 C 로 기록 하고 B 의 아버지 노드 를 D 로 기록 합 니 다.
수정 과정 은 다음 과 같 습 니 다.

A 를 빨간색 으로 설정 하면 전체 나무의 균형 에 영향 이 적다.

A 가 뿌리 노드 라면 뿌리 노드 를 검은색 으로 바 꾸 면 되 고 수정 이 끝 납 니 다.

B 가 검은색 이 라면 나 무 는 균형 적 이 고 수정 이 끝 납 니 다.

만약 에 B 가 빨간색 이 고 B 가 D 의 왼쪽 아이 라면 C 의 색깔 을 판단 한다.

C 가 빨간색 이면 B 와 C 를 검은색 으로 칠 하고 D 는 빨간색 으로 칠 하 며 현재 노드 (A) 를 D 로 가리 키 고 A 를 계속 비교 합 니 다.

C 가 검은색 이 고 A 가 B 의 왼쪽 아이 라면 B 를 검은색 으로 칠 하고 D 를 빨간색 으로 칠 한 다음 에 D 를 우회전 한 다음 에 A 를 계속 비교 합 니 다.

만약 에 C 가 검은색 이 고 A 가 B 의 오른쪽 아이 라면 현재 노드 (A) 를 B 를 가리 키 고 새로운 A 를 좌회전 합 니 다.그리고 B 를 새 A 의 아버지 에 게 가리 키 고 D 를 새 B 의 아버지 에 게 가리 킨 다음 에 B 를 검 게 칠 하고 D 를 빨간색 으로 칠 하 며 D 를 우회전 한 다음 에 A 를 계속 비교 했다.

만약 에 B 가 빨간색 이 고 B 가 D 의 오른쪽 아이 라면 C 의 색깔 을 판단 한다.

C 가 빨간색 이면 B 와 C 를 검은색 으로 칠 하고 D 는 빨간색 으로 칠 하 며 현재 노드 (A) 를 D 로 가리 키 고 A 를 계속 비교 합 니 다.

C 가 검은색 이 고 A 가 B 의 오른쪽 아이 라면 B 를 검은색 으로 칠 하고 D 를 빨간색 으로 칠 한 다음 에 D 를 왼쪽으로 돌 린 다음 에 A 를 계속 비교 합 니 다.

만약 에 C 가 검은색 이 고 A 가 B 의 왼쪽 아이 라면 현재 노드 (A) 를 B 를 가리 키 고 새로운 A 를 우회전 한다.그리고 B 를 새 A 의 아버지 에 게 가리 키 고 D 를 새 B 의 아버지 에 게 가리 킨 다음 에 B 를 검 게 칠 하고 D 를 빨간색 으로 칠 하 며 D 를 왼쪽으로 돌 린 다음 에 A 를 계속 비교 했다.

요소 추가:

public void put(E data) {
    Node now = new Node(data);
    if (root == null) {
        root = now;
        return;
    }

    Node parent = root;
    //           
    while (parent != null) {
        if (data.compareTo(parent.data) < 0) {
            if (parent.left == null) {
                parent.left = now;
                now.parent = parent;
                break;
            } else {
                parent = parent.left;
            }
        } else if (data.compareTo(parent.data) > 0) {
            if (parent.right == null) {
                parent.right = now;
                now.parent = parent;
                break;
            } else {
                parent = parent.right;
            }
        } else {
            return;
        }
    }
    //    
    fixAfterInsertion(now);
}

수정 위치:

private void fixAfterInsertion(Node node) {
    node.color = RED;

    Node parent = null;
    Node brother = null;
    while (node != null && node != root && node.parent.color == RED) {
        parent = node.parent;
        if (parent.parent != null && parent.parent.left == parent) {
            brother = parent.parent.right;
            if (getColor(brother) == RED) {
                setColor(parent, BLACK);
                setColor(brother, BLACK);
                setColor(parent.parent, RED);
                node = parent.parent;
            } else {
                if (parent.right == node) {
                    node = parent;
                    leftRoate(node);
                }
                parent = node.parent;
                setColor(parent, BLACK);
                setColor(parent.parent, RED);
                rightRoate(parent.parent);
            }
        } else {
            brother = parent.parent == null ? null : parent.parent.left;
            if (getColor(brother) == RED) {
                setColor(parent, BLACK);
                setColor(brother, BLACK);
                setColor(parent.parent, RED);
                node = parent.parent;
            } else {
                if (parent.left == node) {
                    node = parent;
                    rightRoate(node);
                }
                parent = node.parent;
                setColor(parent, BLACK);
                setColor(parent.parent, RED);
                leftRoate(parent.parent);
            }
        }
    }

    root.color = BLACK;
}

3. 붉 은 검 은 나무의 삭제
붉 은 검 은 나무의 삽입 은 두 단계 로 나 뉜 다. 삭제, 균형 수정.
여기 서 수정 해 야 할 노드 를 A 로 기록 하고 A 의 부모 노드 를 B 로 기록 하 며 찾 은 최소 불 균형 서브 트 리 를 C 로 기록 합 니 다.
1. 삭제
첫 번 째 삭 제 는 두 갈래 검색 트 리 의 삽입 과 마찬가지 로 삭 제 된 노드 의 대체 노드 를 수정 해 야 할 노드 로 삼 아야 합 니 다.
주의: 삭 제 된 점 이 빨간색 이 라면 나무의 균형 에 영향 을 주지 않 고 수정 할 필요 가 없습니다.
2. 밸 런 스 수정
현재 노드 를 A 로 기록 하고 A 의 아버지 노드 를 B 로 기록 하 며 A 의 형제 노드 를 C 로 기록 하고 B 의 아버지 노드 를 D 로 기록 합 니 다.
수정 과정 은 다음 과 같 습 니 다.

A 가 뿌리 노드 라면 A 를 검은색 으로 설정 하고 수정 이 끝 납 니 다.

A 가 빨간색 이면 A 를 검은색 으로 설정 하고 수정 이 끝 납 니 다.

A 가 B 의 왼쪽 노드 라면

C 의 색깔 을 먼저 판단 하고 C 가 빨간색 이면 C 를 검은색 으로, B 를 빨간색 으로 한 다음 B 를 왼쪽으로 돌 린 다음 B 를 새 A 의 아버지 에 게, C 를 새 B 의 형제

에 게 가 리 켰 다.

그 다음 에 C 의 좌우 부분 노드 가 모두 검은색 인지 판단 하고 모두 검은색 이면 C 를 빨간색 으로 설정 하고 A 를 B 로 가리 킨 다음 에 A 를 계속 판단 한다.

만약 에 C 의 오른쪽 부분 이 검은색 이 고 C 의 왼쪽 부분 이 빨간색 이나 검은색 이 라면 먼저 C 의 왼쪽 부분 을 검은색 으로 설정 하고 C 를 빨간색 으로 설정 하고 B 를 우회전 하 며 B 를 새로운 A 의 아버지 에 게 가리 키 고 C 를 새로운 B 의 형제 에 게 가리킨다.그 다음 에 C 를 B 의 색 으로 설정 하고 B 를 검은색 으로 설정 하 며 B 의 오른쪽 부분 노드 를 검은색 으로 설정 한 다음 에 B 를 좌회전 시 켜 A 를 root 노드 로 가리킨다.

C 의 오른쪽 부분 이 빨간색 이 고 C 의 왼쪽 부분 이 빨간색 이나 검은색 이면 C 를 B 의 색 으로 설정 하고 B 를 검은색 으로 설정 하 며 B 의 오른쪽 부분 을 검은색 으로 설정 한 다음 에 B 를 좌회전 시 켜 A 를 루트 노드 로 가리킨다.

A 가 B 의 오른쪽 부분 이 라면

C 의 색깔 을 먼저 판단 하고 C 가 빨간색 이면 C 를 검은색 으로, B 를 빨간색 으로 한 다음 B 를 오른쪽으로 돌 린 다음 B 를 새 A 의 아버지 에 게, C 를 새 B 의 형제

에 게 가 리 켰 다.

그 다음 에 C 의 좌우 부분 노드 가 모두 검은색 인지 판단 하고 모두 검은색 이면 C 를 빨간색 으로 설정 하고 A 를 B 로 가리 킨 다음 에 A 를 계속 판단 한다.

만약 에 C 의 왼쪽 부분 이 검은색 이 고 C 의 오른쪽 부분 이 빨간색 이 라면 먼저 C 의 오른쪽 부분 을 검은색 으로 설정 하고 C 를 빨간색 으로 설정 하 며 B 를 왼쪽으로 회전 시 키 며 B 를 새로운 A 의 아버지 에 게 가리 키 고 C 를 새로운 B 의 형제 에 게 가리킨다.그 다음 에 C 를 B 의 색 으로 설정 하고 B 를 검은색 으로 설정 하 며 B 의 왼쪽 노드 를 검은색 으로 설정 한 다음 에 B 를 우회전 시 켜 A 를 root 노드 로 가리킨다.

C 의 왼쪽 노드 가 빨간색 이 고 C 의 오른쪽 노드 가 빨간색 또는 검은색 이면 C 를 B 의 색 으로 설정 하고 B 를 검은색 으로 설정 하 며 B 의 왼쪽 노드 를 검은색 으로 설정 한 다음 에 B 를 우회전 시 켜 A 를 root 노드 로 가리킨다.

삭제:

public Node remove(E data) {
    Node now = get(data);
    if (now == null) {
        throw new NoSuchElementException();
    }

    Node p = get(data);
    if (p == null) {
        throw new NoSuchElementException();
    }
    //p          r
    Node r = nodeLeft(p.right);
    //p          l
    Node l = nodeRight(p.left);
    if (r != null) {
        p.data = r.data;
        //  p         
        if (r != p.right) {
            r.parent.left = r.right;
        } else {
            p.right = p.right.right;
        }
        //         ，           ,               
        if (now.color == BLACK) {
            fixAfterDelete(r.right);
        }
        r.left = r.right = r.parent = null;

    } else if (l != null) {
        p.data = l.data;
        //  p         
        if (l != p.left) {
            l.parent.right = l.left;
        } else {
            p.left = p.left.left;
        }
        //         ，           ,               
        if (now.color == BLACK) {
            fixAfterDelete(l.left);
        }
        l.left = l.right = l.parent = null;

        //  p     
    } else {
        //  p     ，      ，             
        if (p.parent != null && p.color == BLACK) {
            fixAfterDelete(p);
        }

        if (p.parent == null) {
            root = null;
        } else if (p.parent.left == p) {
            p.parent.left = null;
        } else {
            p.parent.right = null;
        }
        p.parent = null;
    }
    return now;
}

수정 위치:

private void fixAfterDelete(Node node) {
    if (node == null) {
        return;
    }

    Node parent = null;
    Node brother = null;
    while (node != root && getColor(node) == BLACK) {
        parent = node.parent;
        if (node == parent.left) {
            brother = parent.right;

            if (getColor(brother) == RED) {
                setColor(brother, BLACK);
                setColor(parent, RED);
                leftRoate(parent);
                parent = node.parent;
                brother = parent.right;
            }

            if (getColor(brother.left) == BLACK && getColor(brother.right) == BLACK) {
                setColor(brother, RED);
                node = node.parent;
            } else {
                if (getColor(brother.right) == BLACK) {
                    setColor(brother.left, BLACK);
                    setColor(brother, RED);
                    rightRoate(brother);
                    parent = node.parent;
                    brother = parent.right;
                }
                setColor(brother, getColor(parent));
                setColor(parent, BLACK);
                setColor(brother.right, BLACK);
                leftRoate(parent);
                node = root;
            }
        } else { // symmetric
            brother = parent.left;

            if (getColor(brother) == RED) {
                setColor(brother, BLACK);
                setColor(parent, RED);
                rightRoate(parent);
                parent = node.parent;
                brother = parent.left;
            }

            if (getColor(brother.left) == BLACK && getColor(brother.right) == BLACK) {
                setColor(brother, RED);
                node = node.parent;
            } else {
                if (getColor(brother.left) == BLACK) {
                    setColor(brother.right, BLACK);
                    setColor(brother, RED);
                    leftRoate(brother);
                    parent = node.parent;
                    brother = parent.left;
                }
                setColor(brother, getColor(parent));
                setColor(parent, BLACK);
                setColor(brother.left, BLACK);
                rightRoate(parent);
                node = root;
            }
        }
    }

    setColor(node, BLACK);
}

마지막.
코드 주소:https://gitee.com/yanhuo2008/Common/blob/master/Tool/src/main/java/gsw/tool/datastructure/tree/TreeRedBlack.java
데이터 구조 와 알고리즘 테마:https://www.jianshu.com/nb/25128590
좋아요, 좋아요, 감사합니다!