자료구조 탐색 기초 개념 정리

탐색(Search)

탐색은 말그대로 데이터를 찾는 방법으로서, 자료구조에서 효율적인 탐색을 위해서는 어떤방식으로 찾을까 뿐만아니라 효율적인 탐색을 위한 저장방법을 고민해야한다.

순차탐색: 정렬되지 않은 데이터를 대상으로 하는 탐색

이진탐색: 정렬된 데이터를 대상으로 하는 탐색

---

이진탐색트리

이진탐색트리는 이진트리에서 데이터의 저장규칙을 더한 것으로 이 저장규칙은 특정 데이터의 위치를 찾는데 사용한다.

이진트리: 모든 노드의 자식 노드가 각각 최대 2개인 트리

이진탐색트리의단점: 이진탐색트리의 조건을 만족하면서도 저장순서에 따라서 탐색의 성능이 크게 저하될 수 있다. 

이진탐색트리 조건

1. 노드에 저장된 키는 유일해야한다.

2. 루트노드의 키가 왼쪽 서브트리를 구성하는 노드의 키값들과 비교했을때 가장 커야한다. 

3. 루트노드의 키가 오른쪽 서브트리를 구성하는 노드의 키값들과 비교했을때 가장 작아야한다. 

왼쪽노드의 키 < 부모노드의 키 < 오른쪽노드의 키 (작으면 왼쪽 크면 오른쪽) 

균형잡힌이진트리: 이진탐색트리의 단점을 해결한 트리

균형잡힌이진트리의 종류: AVL트리, 2-3트리, 2-3-4트리, Red-Black트리, B트리

AVL트리

AVL트리는 노드가 추가 및 삭제 될때 트리의 균형상태를 파악하여 스스로 구조를 변경하여 균형을 잡는 트리이다.

기존에 이진탐색트리에서 리밸런싱기능만 추가하면 AVL트리라고 생각할 수 있다.

균형인수(균형의 정도를 표현하는 것) = 왼쪽서브트리의 높이 - 오른쪽서브트리의 높이

= 균형인수의 절댓값이 클수록 트리의 균형이 무너진 상태이다.

AVL트리에서는 균형인수의 절댓값이 2이상일 경우에 리밸런싱을 진행한다.

리밸런싱(rebalancing): 균형을 잡기위한 트리구조의 재조정