[자료구조] 이진 탐색 트리 (Binary Search Tree)

1. 그래프

• 그래프 : 단순히 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 자료구조
• 그래프 용어
  • 정점(vertex) : 위치라는 개념 (node라고도 함)
  • 간선(edge) : 위치 간의 관계, 노드를 연결하는 선(link, branch 라고도 부름)
  • 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
  • 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 진입 차수(in-degree) : 방향 그래프에서 외부에서 오는 간선의 수(내차수라고도 부름)
  • 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
  • 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
  • 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
  • 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우
• 그래프 종류
  • 무방향 그래프 VS 방향 그래프
    • 무방향 그래프(Undirected Graph) 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
    • 방향 그래프(Directed Graph) 간선에 방향성이 존재하는 그래프
  • 가중치 그래프 : 간선에 비용이나 가중치가 할당된 그래프
  • 연결 그래프 VS 비연결 그래프
    • 연결 그래프(Connected Graph) 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
    • 비연결 그래프(Disconnected Graph) 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
  • 사이클 VS 비순환 그래프
    • 사이클(Cycle) 단순 경로의 시작 정점과 종료 정점이 동일한 경우 단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우
    • 비순환 그래프(Acyclic Graph) 사이클이 없는 그래프
  • 완전 그래프 완전 그래프(Complete Graph) 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프 무방향 완전 그래프 정점 수: n이면 간선의 수: n * (n-1) / 2
• 그래프의 구현
  • 인접리스트
    • 모든 정점(혹은 노드)을 인접 리스트에 저장한다. 즉, 각각의 정점에 인접한 정점들을 리스트로 표시한 것이다. 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 리스트에 쉽게 접근할 수 있다
    • 장점 어떤 노드에 인접한 노드들 을 쉽게 찾을 수 있다. 그래프에 존재하는 모든 간선의 수 는 O(N+E) 안에 알 수 있다.
    • 단점 간선의 존재 여부와 정점의 차수를 찾을 시, 정점 i의 리스트에 있는 노드의 수 즉, 정점 차수만큼의 시간이 필요
  • 인접 행렬
    • 인접 행렬은 NxN 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 i -> j로의 간선이 있다는 뜻이다
    • 장점 두 정점을 연결하는 간선의 존재 여부 (M[i][j])를 O(1) 안에 즉시 알 수 있다. 정점의 차수 는 O(N) 안에 알 수 있다. : 인접 배열의 i번 째 행 또는 열을 모두 더한다.
    • 단점 어떤 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다. 그래프에 존재하는 모든 간선의 수는 O(N^2) 안에 알 수 있다. : 인접 행렬 전체를 조사한다.
• 그래프의 탐색 : 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

2. 트리

트리는 그래프의 한 일종이다.

트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다.

특징

• 연결 그래프 이다. (컴포넌트가 하나이다)
• 방향을 무시하였을 때, 싸이클이 존재하지 않는다.
• 트리의 간선 개수는 반드시 트리의 정점 개수보다 1 작다.
  • 루트를 제외하면 모든 노드가 자신의 부모 노드와 이어진 간선을 1개 갖기 때문
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다.

트리를 구성하고 있는 구성요소들 (용어)

• Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
• leaf Node(단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
• Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.
• 형제(sibling) : 같은 부모를 가지는 노드
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 가진 하위 노드의 수
• 트리의 차수(degree of tree): 트리의 최대 차수

 

3. 이진 트리

각 노드가 최대 두 개의 자식을 갖는 트리를 이진 트리라고 한다. 최대 3개의 자식을 가지는 트리라면 삼진트리이며, 최대 차수가 K인 트리를 K진트리로 칭할 수 있다. 나머지는 이진 트리에 비하면 메이저하지 않다.

루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 진다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다. 한 가지 덧붙이자면 공집합도 이진 트리로 포함시켜야 한다. 그래야 재귀적으로 조건을 확인해갔을 때, leaf node 에 다다랐을 때, 정의가 만족되기 때문이다. 자연스럽게 노드가 하나 뿐인 것도 이진 트리 정의에 만족하게 된다.

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level(레벨)이라고 한다. 레벨의 값은 0 부터 시작하고 따라서 루트 노드의 레벨은 0 이다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다

모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리(Perfect Binary Tree)라고 한다. 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리(Complete Binary Tree)라고 한다. 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리를 가리켜 정 이진 트리(Full Binary Tree)라고 한다.

 

 

4. 이진 탐색 트리

효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안된다. 그보다는 효율적인 탐색을 위한 저장 방법이 무엇일까를 고민해야 한다. 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.

이진 탐색 트리는 이진 트리의 한 종류이다. 이진 트리에 추가적인 조건이 붙는다.

• 모든 원소는 서로 다른 유일한 키를 갖는다.
• 왼쪽 자식이 있다면, 왼쪽 자식의 키 값보다 자신의 키 값이 커야 한다.
• 오른쪽 자식이 있다면, 오른쪽 자식의 키 값보다 자신의 키 값이 작아야 한다.
• 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.

key 값이라는 것은 노드가 다른 노드와의 비교를 위해서 갖고 있는 값을 의미하며, 그와 별개로 노드 자체가 가지고 있는 의미있는 값을 value 값이라고 구분지어서 말하기도 합니다.

 

탐색

이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다. 사실 정확히 말하면 O(h)라고 표현하는 것이 맞다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 이러한 이진 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있다. 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문이다. 이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case 가 되고 시간 복잡도는 O(n)이 된다.

배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생한다. 이를 해결하기 위해 Rebalancing 기법이 등장하였다. 균형을 잡기 위한 트리 구조의 재조정을 Rebalancing이라 한다. 이 기법을 구현한 트리에는 여러 종류가 존재하는데 레드 블랙트리, B-Tree 등이 있다.