[CS/자료구조] 트리(Tree) - #1 이진 트리(Binary Tree)와 이진 탐색 트리(BST, Binary Search Tree)

이진 트리(Binary Tree)

트리(Tree) 란 ?

• 계층적인 데이터 구조로 노드(Node)와 엣지(Edge, 가지 또는 연결선)을 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조를 의미한다. (Edge는 가지라는 의미에서 Branch라고 부르기도 한다.)
• 참고로 Tree도 그래프의 한 종류이나 그래프는 사이클을 이루는 자료구조를 포함한다.
• 트리에서 각 요소는 노드로 표현되며, 노드는 데이터를 저장하는 요소를 의미한다.
• 주로 트리 중 이진 트리(Binary Tree) 가 탐색(검색) 알고리즘 구현시 많이 사용된다.

 

트리의 구성요소

이진 탐색 트리(BST, Binary SearchTree)의 구조

노드(Node) 

트리에서 데이터를 저장하는 기본요소로 데이터와 연결된 노드에 대한 Branch의 주소를 포함한다.

 

부모 노드(Parent Node)

어떤 노드의 이전 레벨에 Branch로 연결된 노드를 의미한다.

 

자식 노드(Child Node) 

어떤 노드의 다음 레벨에 Branch로 연결된 노드를 의미한다.

 

형제 노드(Sibling Node = BrotherNode)

같은 부모 노드를 가진 노드를 의미한다.

 

최상위 노드(Root Node)

트리의 최상단에 위치한 노드를 의미한다. 즉, 부모 노드가 없는 것이 바로 Root 노드이다.

 

최하위 노드 (Leaf Node 또는 Terminal Node) 

트리의 최하단에 위치한 노드를 가리키는 말로 즉, 자식 노드가 하나도 존재하지 않는 노드를 의미한다.

 

레벨(Level) or 깊이(Depth)

최상위 노드(Root Node)를 레벨 0으로 측정하여, 그 다음 레벨의 노드들을 1씩 증가시킨 값을 의미한다. 

각 레벨은 해당 노드와 최상위 노드(Root Node) 사이의 거리를 나타낸다.

 

 

 

---

 

 

 

 

이진 트리(Binary Tree)와 이진 탐색 트리(BST, Binary Search Tree)

 

이진 트리(Binary Tree)

이진 트리(Binary Tree)

• 각 노드가 최대 두개의 자식 노드를 가질 수 있는 트리를 의미한다. (무조건 2개의 자식 노드를 갖는 것이 아님!)
• 자식 노드는 왼쪽 자식노드와 오른쪽 자식 노드로 구분된다. 
• 각 노드는 데이터와 두 개의 Branch(자식 노드를 가리키는 링크)를 가지고 있다.

 

이진 탐색 트리(BST, Binary Search Tree)

이진 탐색 트리(BST, Binary SearchTree)의 구조

• 이진 탐색 트리는 영어로 Binary Search Tree인데 영어 약자만 따서 BST라고도 부른다.
• 이진 탐색 트리는 이진트리의 일종으로 기존의 이진트리에서 추가적인 조건을 만족하는 경우 이진 탐색 트리가 된다.
• 해당 조건은 아래와 같다.

 

이진 탐색 트리의 조건

1. 왼쪽 자식 노드의 값은 해당 노드의 값보다 작아야 한다.
2. 오른쪽 자식 노드의 값은 해당 노드의 값보다 커야 한다.
3. 왼쪽 서브트리(자식트리)와 오른쪽 서브트리(자식트리) 모두 이진 탐색 트리여야 한다.

 

 

 

---

 

 

 

 

이진 탐색 트리(BST, Binary Search Tree)로 탐색(검색)시 시간복잡도와 장단점

 

이진 탐색 트리의 시간복잡도

이진 탐색 트리에서 탐색시 시간복잡도는 보통 O(h) 또는 O(log n) 이다.

 

시간복잡도가 O(h) 또는 O(log n) 인 이유

O(h) 에서 h는 트리의 높이(혹은 깊이) 를 나타낸다. 즉, 트리의 높이에 따라 탐색 작업의 실행 시간이 결정되는 것이다. 이 말은 곧 해당 트리에서 하나의 레벨을 탐색할 때 마다 약 50%의 실행시간을 단축 시킬수 있다는 것을 의미한다. 일반적으로 균형이 잘 잡힌 이진 탐색 트리의 경우 평균적인 트리의 높이는 log n에 가깝다. 이는 균형이 잘 잡힌 BST에서는 탐색 작업이 보통 log n번의 비교를 필요로 한다는 것을 의미한다. 하지만 트리가 균형을 잃어 한쪽으로 치우쳐진 경우에는 트리의 높이(h)가 n(입력수)에 가까워질 수 있으므로 탐색 작업의 시간 복잡도는 최악의 경우 O(n)이 될 수 있다. 따라서 이진 탐색 트리에서 시간 복잡도를 보통의 경우에는 O(h) 로 표기하며 균형이 잘 잡힌 이진 탐색트리의 경우에만 O(log n) 으로 표현하는 것이다.

 

균형 잡힌 이진 탐색 트리란?

이진 탐색 트리(Binary Search Tree, BST)의 노드들이 트리의 높이를 최소화하여 가능한 균형을 유지하도록 설계된 트리를 의미한다. 이진 탐색 트리의 기본조건을 만족한다고 트리가 항상 균형이 잘  잡혀있는 것은 아니다. 따라서 균형이 잘 잡힌 이진 탐색 트리가 되기 위해서는 이진 탐색 트리의 기본조건 외에도 트리의 노드들이 한쪽으로 치우치지 않으며 트리가 최소한의 높이를 갖게 해야한다.

 

 

이진 탐색 트리의 장점

• 데이터 탐색(검색)시 일반적으로 정렬된 배열을 사용하는 것보다  탐색 속도가 훨씬 빠르다.
• 데이터가 정렬되어 있어야 하는 배열과 달리 데이터의 추가, 삭제가 용이하다.
  
  

 

이진 탐색 트리의 단점

LinkedList 형태의 이진 트리

보통의 경우 O(h) , 균형이 잘 잡힌 BST의 경우 O(log n) 의 시간복잡도를 갖지만 트리가 균형을 잃어 노드가 한쪽으로 치우쳐진 경우에는 트리의 높이가 n에 가까워 질 수 있으므로 최악의 경우 최악의 경우 시간복잡도가 LinkedList와 동일한 O(n)까지 나빠질 수 있다. 위의 그림은 LinkedList와 유사한 형태를 가진 이진트리로 이진 탐색 트리가 아니지만 극단적인 상황을 예시로 들기 위해 사용했다. 착오 없으시길 바란다.