TIL#66(이진 트리, 이진 검색 트리, 힙)

오늘 한일

• 이진 트리 (Binary Tree)
  각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조이다.

• 특징
  - 모든 노드가 두 개 이하의 자식 노드를 가진다.
  - 완전히 균현 잡힌 트리, 편향 트리 등 다양한 형태가 있다.
  - 특정한 규칙이나 순서 없이 노드들이 배치될 수 있다.

 

• 이진 검색 트리 (Binary Search Tree, BST)
  각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조이다. 이진 트리의 각 노드는 왼쪽 자식과 오른쪽 자식에 대한 포인터를 가지고 있다.

• 특징
  - 노드의 왼쪽 자식 노드는 항상 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 크다.
  - 이 속성 때문에 이진 검색 트리는 효율적인 검색, 삽입, 삭제를 지원한다.
  - 평균적으로 검색, 삽입, 삭제의 시간 복잡도는 O(log n)이다. 그러나 편향된 경우에는 O(n)의 시간 복잡도를 가질 수 있다.

 

• 힙 (Heap)
  완전 이진 트리의 일종으로, 특별한 속성을 만족하는 트리이다. 힙에는 크게 두 종류로 최대 힙(max heap)과 최소 힙(min heap)이 있다.

• 특징
  - 최대 힙 : 모든 부모 노드의 키는 자식 노드의 키보다 크거나 같다. 따라서 루트 노드는 항상 최대 값을 가진다.
  - 최소 힙 : 모든 부모 노드의 키는 자식 노드의 키보다 작거나 같다. 따라서 루트 노드는 항상 최소 값을 가진다.
  - 힙은 주로 우선순위 큐 구현에 사용된다.
  - 삽입과 삭제의 시간 복잡도는 O(log n)이다.

오늘의 TIP

• 순회 (traversal) : 트리의 각 노드를 중복되지 않게 전부 방문하는 것을 의미한다.

• 3가지 기본적인 순회 방법
  - 전위순회(preorder traversal)
  - 중위순회(inorder traversal)
  - 후위순회(postorder traversal)