상용 데이터 구조 - 트 리

원본 링크:https://www.jianshu.com/p/912357993486
트 리 (Tree) 의 기본 개념 트 리 는 결점 이나 정점 과 변 으로 구 성 된 (비 선형 일 수 있 음) 이 고 그 어떠한 고리 의 데이터 구조 도 존재 하지 않 는 다.노드 가 없 는 나 무 를 빈 트 리 라 고 합 니 다.비 어 있 는 나 무 는 하나의 결점 을 포함 하고 여러 개의 부가 결점 이 있 으 며 모든 결점 은 하나의 다단 계 분 층 구 조 를 구성한다.
이 진 트 리
모든 결점 은 기껏해야 두 그루 의 나무 (즉, 이 진 트 리 에는 2 이상 의 결점 이 존재 하지 않 는 다) 를 가지 고 있 으 며, 이 진 트 리 의 자 나 무 는 좌우 의 구분 이 있 으 며, 그 다음 순 서 는 임의로 뒤 바 꿀 수 없다.이 진 트 리 의 성질 1. 이 진 트 리 의 층 차 는 0 에서 시작 하면 이 진 트 리 의 i 층 에서 많 게 는 2^i 개의 결점 (i > = 0) 이 있다. 높이 k 의 이 진 트 리 는 최대 2^(k+1) - 1 개의 결점 (k>=-1) (빈 나무의 높이 는 - 1) 이 있다. 그 어떠한 이 진 트 리 에 대해 서도 잎 결점 (도 0) 수가 m 이 고 도 는 2 의 결점 n 이면 m = n + 1 이다.
이 진 트 리 는 완벽 한 이 진 트 리, 완전 이 진 트 리, 완전 이 진 트 리, 완벽 한 이 진 트 리 (만 이 진 트 리) 로 나 뉜 다.
image
완전 이 진 트 리
image
완 만 이 진 트 리
image
구별
image
이 진 트 리 의 옮 겨 다 니 는 방법
중간 순서 옮 겨 다 니 기: 즉 왼쪽 - 뿌리 - 오른쪽 옮 겨 다 니 며 주어진 이 진 트 리 뿌리 에 대해 왼쪽 트 리 를 찾 습 니 다.왼쪽 나무의 뿌리 에 대해 왼쪽 나 무 를 찾 아가 기;가장 왼쪽 에 있 는 노드 i 를 찾 을 때 까지 반복 합 니 다. 그 다음 에 i 의 부모 노드 를 옮 겨 다 니 고 i 의 형제 노드 를 옮 겨 다 닙 니 다.재 귀적 으로 스 택 에서 나 오 면서 최종 적 으로 옮 겨 다 니 는 순서 가 완 료 됩 니 다. 즉, 뿌리 - 왼쪽 - 오른쪽 옮 겨 다 니 는 순서 입 니 다. 즉, 왼쪽 - 오른쪽 - 뿌리 옮 겨 다 니 는 것 입 니 다.
자바 에서 흔히 볼 수 있 는 트 리 구조
두 갈래 찾기 트 리
이 진 트 리 는 질서 있 는 이 진 트 리 라 고도 부 릅 니 다. 이 진 트 리 의 일반적인 성질 을 만족 시 키 는 것 은 빈 트 리 가 다음 과 같은 성질 을 가 진 다 는 것 을 말 합 니 다. 임 의 노드 왼쪽 트 리 가 비어 있 지 않 으 면 왼쪽 트 리 의 값 은 모두 뿌리 노드 의 값 보다 작 습 니 다. 임 의 노드 오른쪽 트 리 가 비어 있 지 않 습 니 다.오른쪽 하위 트 리 의 값 은 모두 뿌리 노드 의 값 보다 크 고 임 의 노드 의 좌우 하위 트 리 도 각각 이 진 트 리 에서 키 가 같은 노드 가 없습니다.
한계 성과 이 진 트 리 를 사용 하 는 것 은 n 개의 노드 로 무 작위 로 구성 되 기 때문에 특정한 상황 에서 이 진 트 리 는 n 개의 노드 가 있 는 선형 체인 으로 퇴화 된다. 다음 과 같은 그림:
image.png
AVL 트 리
AVL 트 리 는 균형 조건 이 있 는 이 진 트 리 입 니 다. 빨간색 과 검은색 트 리 에 비해 엄격 한 균형 이 진 트 리 입 니 다. 균형 조건 은 반드시 만족 해 야 합 니 다 (모든 노드 의 좌우 서브 트 리 높이 차 이 는 1 을 초과 하지 않 습 니 다). 우리 가 삽입 을 하 든 삭제 하 든 위의 항목 을 만족 시 키 지 않 으 면 회전 을 통 해 균형 을 유지 해 야 합 니 다. 회전 은 시간 이 많이 걸 립 니 다.
사용 필드:
AVL 트 리 는 삽입 삭제 횟수 가 적 지만 많은 경 우 를 찾 는 데 적합 합 니 다.또한 Windows 프로 세 스 주소 공간 관리 에서 회전 을 사용 하 는 목적 은 나무의 높이 를 낮 추고 이 를 균형 있 게 하기 위해 AVL 트 리 의 특징 을 얻 었 다. AVL 트 리 는 이 진 검색 트 리 AVL 트 리 의 좌우 부분 노드 이자 AVL 트 리 AVL 트 리 는 이 진 검색 트 리 의 모든 기본 적 인 특징 을 가지 고 각 노드 의 좌우 부분 노드 의 높이 차 이 는 절대 값 이 최대 1 이다. 즉, 균형 인 자 는 범위 가 1 이다.[-1,1]
검 붉 은 나무
균형 이 잡 힌 두 갈래 로 나 무 를 찾 습 니 다. 뿌리 에서 잎 까지 의 모든 경로 에서 각 노드 에 착색 하 는 방식 에 대한 제한 을 통 해 빨 간 검 은 나 무 는 뿌리 에서 잎 노드 까지 의 가장 긴 경로 가 가장 짧 은 경로 의 두 배 가 되 지 않도록 확보 합 니 다. 엄격 하지 않 은 균형 으로 삭제 점 을 추가 할 때 회전 횟수 가 낮 아 지고 그 어떠한 불 균형 도 세 번 의 회전 안에서 해결 합 니 다.
사용 필드:
붉 은 검 은 나 무 는 검색, 삽입, 삭제 작업 이 많은 경우 에 많이 사용 된다. 1. C++ 의 STL 에 널리 사용 된다. map 와 set 는 모두 붉 은 검 은 나무 로 이 루어 진다. 2. 유명한 linux 프로 세 스 스케줄 링 Completely Fair Scheduler 은 붉 은 나무 로 프로 세 스 제어 블록 을 관리한다. 3. epoll 커 널 에서 이 루어 지고 붉 은 나무 로 이벤트 블록 을 관리한다. 4.nginx 중 붉 은 검 은 나무 로 관리 timer 등
원인: 붉 은 검 은 나무의 조회 성능 은 AVL 나무 보다 약간 뒤떨어진다. AVL 나무 보다 약간 불 균형 하고 가장 많 기 때문이다. 즉, 붉 은 검 은 나무의 조회 성능 은 같은 내용 의 AVL 나무 보다 한 번 더 많 을 뿐 이지 만, 붉 은 검 은 나 무 는 삽입 과 삭제 에 폭발 AVL 나 무 를 삽입 하고 제거 하고 있다. AVL나 무 는 매번 삽입 삭제 할 때마다 대량의 균형 도 계산 을 하 는데, 붉 은 검 은 나 무 는 붉 은 검 은 성질 을 유지 하기 위해 하 는 붉 은 검 은 변환 과 회전 비용 은 AVL 나무 가 균형 을 유지 하기 위해 하 는 비용 보다 훨씬 적다.
성질: 1. 노드 는 빨간색 이나 검은색 입 니 다. 2. 뿌리 노드 는 검은색 입 니 다. 3. 모든 잎 노드 는 검은색 의 빈 노드 (NIL 노드) 입 니 다. 4. 모든 빨간색 노드 의 두 노드 는 검은색 입 니 다. (모든 잎 에서 뿌리 까지 의 모든 경로 에 두 개의 연속 적 인 빨간색 노드 가 있 을 수 없습니다) 5. 모든 노드 에서 모든 잎의 모든 경 로 는 같은 수량의 검은색 노드 를 포함 합 니 다.
B 나무
B - 트 리 는 B 트 리 입 니 다. - 하나의 기호 일 뿐 입 니 다. B 트 리 (B - Tree) 는 균형 잡 힌 트 리 입 니 다. 다 중 검색 트 리 (두 갈래 가 아 닌) 로 데이터 의 질 서 를 확보 할 수 있 습 니 다. 또한 검색, 삽입, 삭제 등 작업 시 성능 을 유지 할 수 있 습 니 다 O(logn). 큰 데이터 의 읽 기와 쓰기 작업 을 최적화 시 키 는 동시에 외부 저장 소 를 묘사 하 는 데 도 사용 할 수 있 습 니 다.(디스크 나 네트워크 에 저 장 된 기호 표를 외부 에서 찾 을 수 있 습 니 다)
특징: 1. 임 의 비 엽 결점 을 정의 하 는 데 는 최대 M 명의 아들 만 있 고 M>2 2. 뿌리 결점 의 아들 수 는 [2, M] 3. 뿌리 결점 을 제외 한 비 엽 결점 의 아들 수 는 [M/2, M] 4. 각 결점 마다 최소 M/2-1 와 최대 M-1 개의 키 워드 를 보관 합 니 다. (최소 2 개의 키워드)5. 비 엽 결점 의 키워드 개수 = 아들 을 가리 키 는 지침 개수 - 16. 비 엽 결점 의 키워드: K[1], K[2], …, K[M-1]； K[i] < K[i+1] 7. 비 엽 결점 의 지침: P[1], P[2], …, P[M], 그 중 P[1] 은 키워드 가 K[1] 보다 작은 하위 나 무 를 가리 키 고 P[M] 키 가 큰 K[M-1] 하위 나 무 를 가리 키 며, 기타 P[i] 키 워드 는 (K[i-1], K[i]) 에 속한다.모든 잎 결점 은 같은 층 에 있다.
예: (M = 3)
image.png
삽입 과 균형 과정
이 그림 은 4 단계 B 트 리 에 다음 데 이 터 를 순서대로 삽입 하 는 과정 을 나타 낸다. 6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4image
4 단계 B 트 리 는 각 노드 에 최대 4 개의 키 트 리, 3 개의 키 워드 를 표시 하고 최소 2 개의 키 트 리, 하나의 키 워드 를 표시 합 니 다.
추가/삭제 도 마찬가지 입 니 다. 아 이 를 추가/삭제 한 후에 부모 노드 가 하위 트 리 k 가 M/2 와 M 에 있 는 조건 을 만족 시 키 는 지 고려 해 야 합 니 다. 만족 하지 않 으 면 다른 노드 에서 하위 트 리 를 뜯 거나 관련 하위 트 리 구 조 를 수정 하여 균형 을 유지 해 야 합 니 다.
B + 나무
B + 나 무 는 B - 나무의 변형 이자 다 중 검색 트 리 B + 의 검색 은 B - 나무 와 대체적으로 같다. 차이 점 은 B + 나 무 는 잎 결점 에 도달 해 야 명중 (B - 나 무 는 비 잎 결점 에서 명중 할 수 있다) 하 는 것 이다. 그 성능 도 키워드 전집 에서 한 번 에 2 점 을 찾 는 것 과 같다.
B + 의 특성: 1. 모든 키 워드 는 잎 결점 의 링크 에 나타 납 니 다 (조밀 한 색인). 또한 링크 의 키 워드 는 질서 가 있 습 니 다. 2. 비 잎 결점 에서 명중 할 수 없습니다. 3. 비 잎 결점 은 잎 결점 의 색인 (희소 색인) 에 해당 하고 잎 결점 은 저장 (키워드) 에 해당 합 니 다.데이터 의 데이터 층 4. 파일 색인 시스템 에 더욱 적합 한 이유: 파일 (노드) 을 추가 삭제 할 때 효율 이 더욱 높다. B + 나무의 잎 노드 는 모든 키 워드 를 포함 하고 질서 있 는 링크 구조 로 저장 하기 때문에 삭제 효율 을 높 일 수 있다. 예 를 들 어 (M = 3)
image.png
사용 필드:
파일 시스템 과 데이터베이스 시스템 에서 자주 사용 되 는 B/B + 트 리 입 니 다. 그 는 각 노드 에 개 수 를 저장 하 는 확장 을 통 해 연속 적 인 데 이 터 를 빠 른 위치 추적 과 접근 을 할 수 있 고 검색 시간 을 효과적으로 줄 이 며 저장 공간의 국부 성 을 향상 시 켜 IO 작업 을 줄 일 수 있 습 니 다. 그 는 파일 시스템 과 데이터 베이스 에 널리 사 용 됩 니 다. 예 를 들 어 Windows: HPFS 파일 시스템 Mac: HFS, HFS +파일 시스템 Linux: ResiserFS, XFS, Ext3FS, JFS 파일 시스템 데이터베이스: ORACLE, MYSQL, SQLSERVER 등
B 트 리: 질서 있 는 배열 + 균형 다 진 트 리 B + 트 리: 질서 있 는 배열 링크 + 균형 다 진 트 리
B + 나무의 장점:
1. 등급 이 낮 고 IO 횟수 가 적 습 니 다. 2. 매번 에 잎 노드 를 조회 해 야 합 니 다. 조회 성능 이 안정 적 입 니 다. 3. 잎 노드 는 질서 있 는 링크 를 형성 하고 범위 조회 가 편리 합 니 다. B + 수 삽입 과 균형
image
B + 나 무 는 가장 큰 장점 이 있 습 니 다. 라 이브 러 리 를 쓸 기 편 합 니 다. B 나 무 는 중간 순서 로 라 이브 러 리 를 쓸 어야 합 니 다. B + 나 무 는 잎 결점 에서 하나씩 쓸 면 됩 니 다. B + 나 무 는 range - query 를 지원 하 는 것 이 매우 편리 하고 B 나 무 는 지원 하지 않 습 니 다. 이것 은 데이터 베 이 스 를 선택 하여 B + 나 무 를 선택 하 는 가장 주요 한 원인 입 니 다.
예 를 들 어 5 - 10 사 이 를 조사 하려 면 B + 나 무 는 한 줌 에서 5 라 는 표 시 를 한 다음 에 10 까지 꿰 면 됩 니 다. B 나 무 는 매우 번 거 롭 습 니 다. B 나무의 장점 은 성공 적 으로 조회 하 는 것 이 매우 유리 합 니 다. 나무의 높이 는 전체적으로 B + 나무 보다 낮 기 때 문 입 니 다. 성공 하지 못 한 상황 에서 B 나무 도 B + 나무 보다 조금 쌉 니 다.