[트리] 색인과 이진검색트리

색인

• 데이터의 저장과 검색은 자료구조와 알고리즘 분야에서 가장 중요한 주제
• 이 작업을 위함 핵심 인프라는 색인임
• 색인은 개체의 레코드를 검색하기 위한 것. 레코드에 빨리 접근하기 위한 것
• 내장 색인 : 메인 메모리에 올려놓고 쓰는 색인
• 외장색인 : 메모리 바깥에 놓고 쓰는 색인 ex) B-트리

 

색인의  추상 데이터 타입 ADT

색인에 키 X를 삽입
색인에서 키 X를 검색
색인에서 키 X를 삭제
색인이 비어 있는지 확인
색인을 깨끗이 비우기

 

이진 검색 트리

• 각 노드는 최대 2개까지 가지를 칠 수 있음
• 맨 위에 있는 노드를 루트라고 함
• 특성
  • 각 노드는 키값을 하나씩 가짐, 각 노드의 키값은 모두 다름
  • 최상위 레벨의 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 가짐
  • 임의 노드의 키값은 자신의 왼쪽 아래에 있는 모든 노드의 키값조다 크고, 오른쪽 아래에 있는 모든 노드의 키값보다 작음
• 검색 트리의 높이는 효율성에 큰 영향을 미침

• 노드 객체의 구조

• 핵심작업 : 검색, 삽입, 삭제

 

검색

• 루트 노드의 키값과 비교해서 좌서브트리 혹은 우서브트리로 가서 알맞은 자리를 찾는다.
• 루트 노드의 키값과 비교하고 나면 자신과 성격은 똑같으면서 크기만 더 작은 문제를 만남 = 재귀적인 구조

 

삽입

• 삽입 전 우선 이진 검색트리에 같은 키값을 가진 노드가 없어야 함
• 원소 x를 삽입할 자리를 찾는 것은 실패하는 검색을 한 번 수행하는 것
• 이진 검색 트리의 모양은 원소들이 어떤 순서로 삽입되었는지에 따라 결정됨

 

삭제

• 삭제는 트리의 전 영역에서 발생함
• 삭제 이후의 처리는 3가지 케이스에 따라 달리 처리함
  • 1. r이 리프노드인 경우(자식 없음)
  • 2. r의 자식 노드가 1개인 경우
  • 3. r의 자식 노드가 2개인 경우

 

 

 

이진 검색 트리의 성질

• 빈트리의 높이는 0, 노드 하나로 이루어진 이진 트리는 높이가 1
• 포화 이진 트리 : 모든 노드에서 자식이 둘씩 꽉 채워져 있는 것

순회

• 이진 검색 트리에서 모든 노드를 방문해야 하는 경우
• 전위 순회, 중위 순회, 후위 순회

 

 

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」