탐색

탐색

순차 탐색

자기 구성 순차 탐색

• 자주 사용되는 요소를 앞에 배치함으로써 순차 탐색의 효율을 높임
• 전진 이동법 : 한 번 탐색된 요소를 집합의 가장 앞에 위치
• 전위법 : 탐색된 요소를 바로 이전 요소와 교환
• 계수법 : 각 요소가 탐색된 수를 저장해 해당 수의 내림차순으로 요소를 재정렬

이진 탐색

• 정렬된 집합의 중앙값과 탐색값을 비교해 작다면 나머지 왼쪽을 대상으로 다시 이진탐색, 크다면 반대

이진 탐색 트리

• 왼쪽 자식 트리는 자신보다 작고 오른쪽 자식 트리는 자신보다 큰 이진 트리
• 이진 탐색을 위한 자료구조
• 트리의 각 노드는 중앙 요소임
• 삽입 시 이진 탐색을 수행, 조건에 맞는 리프 노드에 삽입
• 삭제 시 리프 노드가 아닌 경우 자식 노드를 적절하게 부모 노드에게 연결
  • 삭제될 노드의 오른쪽 자식 노드의 자식 노드 중 가장 작은 노드로 원래 자리 대체. 해당 노드의 자식 노드를 해당 요소의 원래 자리 대체
• 좌우가 불균형한 이진 탐색 트리는 탐색의 효율을 떨어뜨림 → 레드 블랙 트리 등장

레드 블랙 트리

• 아래 5가지 규칙을 모두 지키는 트리
  • 모든 노드는 빨간색 혹은 검은색
  • 루트 노드는 검은색
  • 리프 노드는 검은색
  • 빨간 노드의 자식은 모두 검은색, 하지만 검은 노드의 자식이 빨갈 필요는 없음
  • 루트 노드에서 모든 리프 노드 사이에 있는 검은색 노드 수는 모두 동일
• 삽입과 삭제는 위 5가지 규칙을 지키도록 트리를 변경

https://ko.wikipedia.org/wiki/레드-블랙_트리