알고리즘 트리(Tree)
AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다.
트리의 높이가 h일 때 이진 탐색 트리의 시간 복잡도는 O(h)입니다.
한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에
이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용하게 됩니다.
AVL트리는 다음과 같은 특징을 가집니다.
- AVL 트리는 이진 탐색 트리의 속성을 가집니다.
- 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다.
- 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다.
- AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다.
(트리는 데이터 + 다음 데이터의 주소값을 갖는 형태)
시간 복잡도
트리의 시간 복잡도 트리 안에서는 O(log N) 이다
N은 트리의 노드 수이다.
AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)입니다.
위 사진과 같이 노드들이 계층을 가지고 구성이 된다.
따라서 연결 리스트의 prev, next 같은 선형구조가 아닌, 최상위 노드(20)를 기준으로
노드들이 왼쪽, 오른쪽 "자식"으로 배치 되는 비선형 구조이다.
나무가 나무가지를 뻗어 나가는것처럼 그런 느낌이다.
그리고 서로 사이클을 이루지 않도록 구성이 된다.
트리의 용어
- Node: 트리에서 데이터를 구성하고 있는 각 요소 (데이터 및 Branch 정보도 포함)
-Root Node: 트리의 최상위에 있는 노드
-Level: 노드의 깊이
-Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
-Child Node: 어떤 노드의 이전 레벨에 연결된 노드
-Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
-Depth: 트리에서 Node가 가질 수 있는 최대 Level
-이진 트리란?
위에서 공부한 트리의 내용은 이진트리를 기반으로 설명했는데,
사실 트리를 구성하는 노드의 branch 갯수는 다음과 같이
여러 개가 될 수 있다.
자식 노드가 아예 없을 수 도 있고, 2개가 될 수 도있고, 3개도 될 수 있다.
이진 트리란 branch가 최대 2개인 노드로만 구성되는 트리 를 말하는거 이다.
따라서 다음과 같이 branch의 갯수가 0~2개로 생긴 노드들이
모여서 만든 트리는 모두 이진 트리이다.
만약 branch가 3개 있는 노드가 하나라도 있을 경우, 그 트리는 이진 트리가 아니다.
-이진 탐색 트리
간단하게? 이진트리에 조건이 붙는것이다.
모든 노드가 자신의 왼쪽 Child Node엔 자신보다 작은 값이, 자신의 오른쪽 Chid Node엔
자신보다 큰 값이 오는 규칙을 만족하는 "이진 트리"를 말한다.
노드의 데이터 값은 유일하다(중복 되지 않는다.)
노드의 데이터 값은 항상 존재한다(nil이면 안됨)
그림을 보면 알수있을 것이다.
이진 트리를 Binary Search Tree라고 부르게된다
보통 줄임말로 BST라고 한다.
정리를 해본다면
이진 트리란 branch가 최대 2개인 노드로만 구성된 트리를 말한다.
이진 트리에서 특정 조건을 만족하는 트리를 이진 탐색 트리라고 한다.!