💡코드 없는 알고리즘과 데이터 구조을 바탕으로 작성된 글입니다.

트리 데이터 구조

💡트리 데이터 구조 : 데이터를 계층으로 정렬한다. 그 모습이 트리와 닮아 트리 데이터 구조라는 이름이 붙었다.

나무는 식물을 바로 세우는 역할을 뿌리가 담당한다. 트리 데이터 구조에서도 뿌리에 해당하는 루트 노드가 있으며, 루트 노드를 기준으로 나머지 요소들이 구성된다.

트리 데이터 구조의 용어

Tree의 용어

🚨 자식 노드는 여러 개의 부모 노드를 가지지 않는다!
만약, 여러 개의 부모 노드를 가진 자식 노드가 있는 자료 구조가 있다면 그것은 그래프라 한다.

• 💡노드에 데이터를 저장하며, 이 때 데이터를 key-value 유형으로 저장할 수도 있다.
• 트리를 탐색하는 과정을 순회라고 한다.

트리 데이터 구조의 종류

가장 많이 사용되는 데이터 구조.

• 💡 부모 노드가 항상 2개의 자식 노드와 연결되어 있는 구조
• 이진 트리의 종류

이진 탐색 트리

이진 트리의 가장 일반적인 유형으로 key-value 구조로 이루어져 있으며, 노드의 키를 기준으로 정렬한 상태를 말한다.

• 💡 모든 노드의 키는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다.
  
• 가장 작은 키를 갖는 노드는 루트 노드에서 가장 왼쪽에 있는 서브트리의 말단에 위치
• 가장 큰 키를 갖는 노드는 루트 노드에서 가장 오른쪽에 있는 서브트리의 말단에 위치

이진 탐색 트리의 동작

1. 트리에 노드를 추가할 수 있다.
2. 트리에서 노드를 삭제할 수 있다.
3. 노드를 선택해 탐색하고자 하는 키가 존재하는지 확인할 수 있다.

💡이진 탐색 트리는 트리 구조로 정렬된 데이터를 저장하는데 효율적이다.

AVL 트리

불균형 이진 트리

• 단 하나의 자식 노드를 갖는 구조
• 💡 트리의 균형을 조정하는 과정 필요
  • 트리 역할 유지하며 자식 노드의 계층이 최소로 만드는 것

🤔 왜 굳이 균형을 조정해야 하지?
메모리 관리를 위해 중요하며, 불균형 구조보다는 균형이 잡힌 트리 구조가 메모리를 훨씬 효율적으로 사용할 수 있다.

AVL 이진 트리

불균형 했던 AVL 트리의 균형을 조정한 트리 구조
위키백과 - AVL 트리

• 서브트리 2개 사이에서 높이 차이를 감지하면 트리 회전이라는 균형 조정 과정을 수행
• 💡시간 복잡도 : O(logn)
• 일부 데이터베이스 검색 시스템에서 사용된다.

RB 트리

자체적으로 균형을 조정하는 트리 구조구조

• AVL 이진 트리와 비슷하지만 트리 회전수가 적어 AVL 트리보다 효율적

• 💡시간 복잡도 : O(logn)
  

• 노드마다 빨강 또는 검정으로 해석되는 비트를 포함한다.

  • 루트 노드는 검정, 빨강 노드는 검정 노드를 자식 노드로 갖는다.

B 트리

데이터베이스 시스템을 설계할 때 사용하는 데이터 구조.

• 💡 자체적인 균형 조정 기능을 갖춘 트리 유형
• 자식 노드 3개 이상을 갖는 부모 노드가 있다.
  
• 파일 시스템에서 데이터 계층 구조로 사용한다.

힙

트리 기반 데이터 구조로 이진 트리 데이터 구조의 한 종류이다.

• 💡 값이 최대 혹은 최소인 노드에 빠르게 접근해야 할 경우에 적합
• 힙을 사용해 우선순위 큐을 구현할 수 있다.

힙의 구조를 설계하는 방법

1. 최대 힙

루트 노드가 힙에서 가장 큰 값이고 노드 각각의 값이 부모 노드의 값보다 작거나 같도록 구성

2. 최소 힙

루트 노드가 힙에서 가장 작은 값이고 노드 각각의 값이 부모 노드의 값보다 크거나 같도록 구성.

• 💡 최소 힙이나 최대 힙의 성능을 대체할 다른 데이터 구조는 없다!

🚨 힙 메모리와 데이터 구조 힙은 전혀 다른 개념!!!!