Tree
트리에 대한 간단한 정리
나무처럼 관계를 가진 자료구조이다.
검색, 레코드, 키와 색인
검색트리는 개체의 레코드를 찾아가는 방식을 제공
레코드 개체에 대한 모든 정보
색인 , 키 : 개체가 가지고있는 고유한 유일무이한 값
예시 : 주민등록번호, 학번, 전화번호
2진 검색 알고리즘
문제를 반으로 계속 나누어 탐색하는 방법
검색 트리
이진탐색의 개념을 트리의 계층적인 형태에 접목한 자료구조
트리는 리프 노드와 서브 트리가 있다.
리프 노드는 자식이 없는 노드
서브 트리는 부분적인 트리이다.
2진 트리
2진 트리의 간단한 정의
각 노드의 자식수가 2이하인 트리
경사 2진 트리
경사진 2진 트리인데 한 줄로만 되어있다.
순회
전휘 순회
루트-> 오른쪽 -> 왼쪽
중휘 순회
왼쪽->루트->오른쪽
후휘 순회
왼쪽->오른쪽->루트
2진 트리의 특성
- 각 노드는 키값을 하나씩 갖고 각 노드의 키값은 모두 다르다.
- 최상위 레벨에 루트 노드가 있고 각 노드를 최대 2개 의 자식 노드를 갖는다.
- 임의 노드의 값은 왼쪽 자식 노드보다 크고 오른쪽 자식노드보다 작다.
부모 노드 자식노드의 리스트의 위치 확인 방법
이진 트리를 리스트에 저장하면 특정 노드의 부모 노드, 자식 노드가 리스트의 어디에 저장되어 있는지 확인하는 방법
A[i]의 부모 노드는 a[i//2] 단, i>1
A[i]의 왼쪽 자식 노드는 a[2i] 단, 2i <= N
A[i]의 오른쪽 자식 노드는 a[2i+1] 단, 2i+1 <= N
(자식노드가 하나만 있는 노드는 혹은 자식이 없는 리프노드는 리스트의 공간을 비워놓는다.)
2진 트리의 높이
이진 트리의 높이는 루트에서 가장 깊은 노드(리프 노드) 까지의 거리
노드가 하나인 이진 트리의 높이는 1
노드가 없는 이진 트리의 높이는 0
2진 트리의 종류
empty트리
루트만 있는 2진 트리
오른쪽 서브트리가 없는 2진 트리
왼쪽 서브트리가 없는 2진 트리
포화 2진 트리와 완전 2진 트리
포화 2진 트리
각 내부노드가 2개의 자식 노드를 가지는 트리
완전 2진 트리
마지막 레벨을 제외한 각 레벨이 전부 꽉차있고 마지막 레벨은 왼쪽부터 빠짐없이 채워진 트리
나머지 트리는 불완전한 2진 트리 이다.
2진 트리
레벨 k에 있는 최대 노드 수 2^k-1
높이가 h인 포화2진트리에 있는 노드 수 2^h-1
n개의 노드를 가진 완전이진트리의 높이 log2(n+1)
균형 검색 트리(AVL트리)
이진 검색 트리의 단점인 트리의 균형이 깨진 것을 수선 하는 AVL 트리, 레드-블랙 트리
Adelson-Velskii와 Landis 두 사람이 고안한 트리 자료 구조, 이진 검색 트리가 항상 균형을 유지하도록 운영 트리 내의 어떤 노드도 좌서브 트리와 우서브 트리의 높이 차가 1보다 크지 않은 상태로 유지되는 이진 검색 트리
균형 검색 트리(AVL트리) 수선과정
AVL 트리의 수선 작업은 네 가지 유형으로 분류됨 LL, LR, RR, RL
LL : left left가 가장 깊음
LR : left right가 가장 깊음
RR : right right가 가장 깊음
RL : right left가 가장 깊음
균형 검색 트리(AVL트리)을 쓰는 이유
AVL트리는 트리의 높이의 균형을 맞추는 트리이다.
이러한 트리구조는 N개의 노드를 가진 트리의 높이가 logN이 되어 탐색 삽입 삭제등의 수행시간이 보장된다.
레드 블랙 트리
AVL 트리와 함께 균형을 맞추면서 운영하는 대표적인 균형 2진 검색 트리
루트는 블랙이다
모든 리프 노드는 블랙이다
루트로 부터 임의의 리프 노드에 이르는 경로에 레드 노드 2개가 연속으로 출현하지 못한다
루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다블 / \ 레 블 /\ \ 블 블 레 / \ 레 레
B 트리
정보를 표현하는 각 항목(데이터 필드)과 다른 노드를 가리키는 링크 필드로 구성된다.
디스크 환경에서 사용하기에 적합한 외장 다진 검색 트리
루트를 제외한 모든 노드는 k/2 ~k 개의 키를 갖는다.
모든 리프 노드는 같은 깊이를 가진다.
l-링크 필드 | 데이터 필드 | r-링크 필드
