이진트리(Binary Tree) & 이진 탐색 트리(Binary Search Tree) 이진트리(Binary Tree) 모든 노드들이 둘 이하의 자식을 가진 트리이다. 이진트리 유형 전 이진트리(Full Binary Tree) 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다. 완전 이진트리(Complete Binary Tree) 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다. 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다. 마지막 레벨 h에서 1 ~ 2h - 1개의 노드를 가질 수 있다. 완전 이진트리는 배열을 사용해 효율적으로 표현이 가능하다. 포화 이진트리(Perfect Binary Tree) 모든 내부 노드가 두 개의 자식 노드를 가지며..

AVL 트리(균형 이진 탐색 트리) AVL 트리란? 오른쪽 서브트리의 높이와 왼쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다. 여기서 말하는 높이 차이를 균형 인수(Balance Factor, BF)라고 한다. 이진 탐색 트리의 한 종류이며, 이진 탐색 트리는 이진 트리의 한 종류이다. 따라서, 이진트리와 이진탐색트리의 특징을 모두 갖고 있다. 특징 이진 탐색 트리의 속성을 가진다. 어떤 노드라도 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크지 않다. (= 최대 1이다.) 높이 차이가 1보다 커지면 회전(Rotation) 을 통해 균형을 맞춰 높이 차이를 줄인다. 삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다. (N : 노드의 개수) 사용하는 이유 이진 탐색 트리를 만들..