붉 은 검 은 나무 기본 개념

붉 은 검 은 나무 기본 개념
       [위 키 피 디 아] 붉 은 검 은 나 무 는 균형 이 잡 힌 이 진 트 리 로 컴퓨터 과학 에서 사용 되 는 데이터 구조 로 전형 적 인 용 도 는 관련 배열 을 실현 하 는 것 이다.1972 년 에 루 돌 프 벨 이 발명 한 것 으로 그 는 '대칭 이 진 B 나무' 라 고 불 렀 다. 그의 현대 이름 은 Leo J. Guibas 와 Robert Sedgewick 이 1978 년 에 쓴 논문 에서 얻 은 것 이다.이것 은 복잡 하지만 그의 조작 은 좋 은 최 악의 상황 운행 시간 을 가지 고 실천 에서 효율 적 입 니 다. 이것 은 O (log n) 시간 안에 찾 고 삽입 하 며 삭제 할 수 있 습 니 다. 여기 n 은 나무 에 있 는 요소 의 수량 입 니 다.
       붉 은 검 은 나 무 는 균형 에 대한 제한 을 풀 었 다.더 이상 엄격 한 의미 의 균형 이 진 트 리 가 아 닐 수 있 습 니 다.
       [해석]: 붉 은 검 은 나 무 는 균형 이 잡 힌 이 진 트 리 에 속한다.그것 이 엄격 하지 않다 고 말 하 는 것 은 왼쪽, 오른쪽 나무의 높이 나 노드 수의 차 이 를 1 보다 엄격하게 통제 하지 않 기 때문이다.그러나 붉 은 검 은 나무의 높이 는 여전히 평균 log (n) 이 고 최 악의 경우 2log (n) 를 넘 지 않 는 다 는 것 은 수학 적 증명 이다.그래서 밸 런 스 트 리 라 고 하 는데 엄격 하지 않 을 뿐 이에 요.그러나 엄격 여 부 는 데이터 구조의 복잡 도 에 영향 을 주지 않 는 다.붉 은 검 은 나 무 는 주로 시스템 의 밑바닥 에 쓰 인 다.
       붉 은 검 은 나무 와 AVL 나무의 공통점 과 차이 점 은?
      【 해 독 】: 빨간색 과 검은색 트 리 는 앞에서 말 한 AVL 트 리 와 유사 하 며 삽입 과 삭제 작업 을 할 때 특정한 조작 을 통 해 이 진 트 리 의 균형 을 유지 하여 높 은 검색 성능 을 얻 습 니 다.빨 간 검 은 나무 가 나 온 후부 터 AVL 나 무 는 박물관 에 놓 여 있 는데 빨 간 검 은 나무 가 더 효율 적 이 고 통계 적 성능 이 높다 고 한다.

       AVL                   ，             AVL          。AVL                   。              。

       빨간색 과 검은색 나무, 두 갈래 로 나 무 를 찾 지만, 각 노드 에 노드 를 표시 하 는 색 을 추가 하면 빨간색 이나 검은색 일 수 있다.뿌리 에서 잎 까지 의 모든 노드 착색 방식 에 대한 제한 을 통 해 빨 간 검 은 나 무 는 다른 경로 보다 두 배 나 자 라 는 경로 가 없 기 때문에 균형 에 가깝다.앞에서 말 했 듯 이 빨 간 검 은 나 무 는 이 진 트 리 를 찾 는 것 이다. 이 진 트 리 를 찾 는 이상 이 진 트 리 의 일반적인 성질 을 만족 시 켜 야 한다.
      빨 간 검 은 나 무 는 노드 를 통 해 빨간색, 검은색 두 가지 색 으로 나 누고 일정한 규칙 에 따라 어느 정도 균형 을 잡 도록 확보 하여 빨 간 검 은 나무 에서 찾 거나 삭제 하거나 삽입 하 는 작업 은 모두 O (logk) 의 시간 만 필요 하도록 한다.
      STL 에서 set 와 multiset 는 모두 붉 은 검 은 나 무 를 바탕 으로 이 루어 진다.
        검 붉 은 나무의 성질:
1）  붉 은 검 은 나무 노드 는 붉 은 노드 든 검 은 노드 든;
2）  뿌리 노드 가 검 은 노드;
3）  잎 노드 (빈 노드) 는 검 은 노드 이다.
4）  모든 빨 간 노드 의 두 부분 은 검 은 노드 이다.
5）  각 노드 에 대해 이 노드 에서 자손 노드 까지 의 모든 경로 에는 같은 수량의 검 은 노드 가 포함 되 어 있다.
        붉 은 검 은 나무의 시간 복잡 도:
1. 이 진 트 리 에서 찾기, 삽입, 삭제 등 작업 을 수행 하 는 가장 좋 은 시간 복잡 도 는 O (lgn) 입 니 다.n 개의 결점 으로 무 작위 로 구 성 된 이 진 트 리 의 높이 는 lgn 이기 때문에 순리 적 이 고 일반 작업 의 실행 시간 은 O (lgn) 입 니 다.
2. 그러나 n 개의 결점 을 가 진 선형 체인 이 라면 이 작업 의 최 악의 상황 운행 시간 은 O (n) 이다.
한편, 빨간색 과 검은색 나 무 는 최 악의 상황 에서 기본 적 인 동적 기하학 적 작업 시간 이 모두 O (lgn) 임 을 보장 할 수 있다.
 
 
2 분 찾기 트 리 (2 분 찾기 와 유사)
이 진 트 리 (AVL 트 리)
검 붉 은 나무
최 악의 시간 복잡 도
O（n）
O（logn）
O（logn）
가장 좋 은 시간 복잡 도
O（logn）
O（logn）
O（logn）
평균 시간 복잡 도
O（logn）
O（logn）
O（logn）