자료구조 트리, 이진탐색트리, 해시테이블

JAVA로 구현하는 알고리즘과 디자인 패턴 공부: 핵심 자료구조 2편

1. 트리 (Tree) 🌳

개념: 이름처럼 나무를 거꾸로 뒤집어 놓은 듯한 형태의 계층적 자료구조입니다. 하나의 루트(Root) 노드에서 시작하여 여러 개의 자식 노드가 가지처럼 뻗어 나가는 구조를 가집니다. 파일 시스템의 폴더 구조나 회사의 조직도를 생각하면 쉽습니다.

• 주요 용어:
  • 노드(Node): 트리를 구성하는 각각의 데이터 요소.
  • 간선(Edge): 노드와 노드 사이를 연결하는 선.
  • 루트(Root): 트리의 최상위 노드.
  • 부모(Parent) / 자식(Child): 특정 노드에 연결된 상위 노드와 하위 노드.

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

트리 중에서도 가장 중요하고 자주 사용되는 것이 바로 이진 탐색 트리입니다. 특정 규칙에 따라 데이터를 저장하기 때문에 탐색(Search)에 매우 효율적입니다.

• BST의 핵심 규칙:
  1. 모든 노드의 왼쪽 자식 노드는 부모 노드보다 값이 작다.
  2. 모든 노드의 오른쪽 자식 노드는 부모 노드보다 값이 크다.
  3. 모든 서브트리(Subtree) 또한 이진 탐색 트리이다.

• 특징 및 시간 복잡도:
  • 탐색/추가/삭제: 평균 O(logn), 최악 O(n)
    • 평균: 데이터를 찾거나 추가할 때마다 비교를 통해 탐색 범위가 절반씩 줄어들기 때문에 $O(\log n)$의 아주 빠른 속도를 보입니다. (이진 탐색과 원리가 같죠!)
    • 최악: 데이터가 1, 2, 3, 4, 5처럼 순서대로 들어오면 트리가 한쪽으로만 계속 자라서 연결 리스트(LinkedList)와 같은 형태가 됩니다. 이 경우 탐색 시간은 $O(n)$이 됩니다.
• Java 코드 예시 (노드 클래스):
• Java

   

  // 이진 탐색 트리를 구성하는 노드 클래스
  class Node {
      int key;      // 노드의 값
      Node left;    // 왼쪽 자식 노드
      Node right;   // 오른쪽 자식 노드
  
      public Node(int item) {
          key = item;
          left = right = null;
      }
  }
  // 실제 삽입, 삭제, 탐색 로직은 이 Node를 활용하여 Tree 클래스에 구현합니다.
  

• 실제 사용 예:
  • 데이터베이스 인덱스: 데이터베이스는 빠른 검색을 위해 인덱스를 B-Tree(BST를 확장한 형태)로 저장하여 $O(\log n)$의 검색 성능을 보장합니다.
  • 파일 시스템: 폴더와 파일의 계층 구조를 표현하는 데 사용됩니다.
  • UI 라이브러리: 화면에 보이는 컴포넌트들의 계층 구조(DOM)를 트리 형태로 관리합니다.

---

2. 해시 테이블 (Hash Table) #️⃣

개념: **키(Key)와 값(Value)**을 하나의 쌍으로 저장하는 자료구조입니다. 가장 큰 특징은 **해시 함수(Hash Function)**를 사용하여 키를 배열의 인덱스(Hash Code)로 변환하고, 이를 통해 데이터에 $O(1)$의 속도로 직접 접근한다는 점입니다.

• 핵심 원리:
  1. 'username'이라는 키를 해시 함수에 넣습니다.
  2. 해시 함수는 'username'을 기반으로 12345와 같은 고유한 숫자(해시 코드)를 만듭니다.
  3. 이 해시 코드를 배열의 크기로 나눈 나머지 값 등을 이용해 실제 배열의 인덱스를 결정합니다.
  4. 해당 인덱스에 값(사용자 정보)을 저장하거나 가져옵니다.
• 해시 충돌 (Hash Collision): 서로 다른 키가 해시 함수를 거쳐 같은 인덱스로 변환되는 경우를 말합니다. 해시 테이블은 이런 충돌을 해결하기 위한 전략이 필요하며, 주로 해당 인덱스에 **연결 리스트(Chaining)**를 두어 데이터를 관리합니다.
• 특징 및 시간 복잡도:
  • 탐색/추가/삭제: 평균 O(1), 최악 O(n)
    • 평균: 해시 함수를 통해 키가 바로 인덱스로 변환되므로, 데이터의 양과 상관없이 거의 일정한 속도를 보입니다. 그 어떤 자료구조보다 빠른 '검색' 성능입니다.
    • 최악: 운이 나쁘게 모든 키가 같은 인덱스로 충돌하면, 해당 인덱스의 연결 리스트를 처음부터 끝까지 탐색해야 하므로 $O(n)$이 됩니다. (하지만 잘 만들어진 해시 함수는 이런 경우를 거의 만들지 않습니다.)
• Java 코드 예시 (HashMap):
• Java

   

  // Java에서는 해시 테이블을 HashMap 클래스로 제공합니다.
  Map<String, String> capitals = new HashMap<>();
  
  // 1. 데이터 추가 (put)
  capitals.put("대한민국", "서울");
  capitals.put("미국", "워싱턴 D.C.");
  capitals.put("일본", "도쿄");
  
  // 2. 데이터 조회 (get) - O(1)의 위력!
  // "미국"이라는 키를 해싱하여 바로 값에 접근한다.
  System.out.println("미국의 수도: " + capitals.get("미국")); // 출력: 워싱턴 D.C.
  
  // 3. 데이터 삭제 (remove)
  capitals.remove("일본");
  

• 실제 사용 예:
  • 캐시(Cache): 한번 계산된 결과를 키-값 형태로 메모리에 저장해두고, 다음번에 동일한 요청이 오면 계산 없이 $O(1)$의 속도로 빠르게 결과를 반환하는 데 사용됩니다.
  • Spring Framework: Spring의 IoC 컨테이너는 내부적으로 HashMap을 사용하여 **빈(Bean)의 이름(Key)과 실제 객체 인스턴스(Value)**를 관리합니다. @Autowired 등으로 빈을 주입받을 때, 이 해시맵에서 빈의 이름을 키로 객체를 매우 빠르게 찾아옵니다.

---

3. 문제 제시 및 답변

개념을 잘 이해했는지 확인해볼 시간입니다! 💡

문제: 수백만 명의 회원 정보를 관리하는 시스템을 만드려고 합니다. 각 회원은 고유한 email 주소를 가지고 있습니다. 이 시스템의 가장 중요한 요구사항은, 사용자가 email 주소를 입력했을 때 해당 회원의 정보를 가장 빠르게 찾아내는 것입니다. 어떤 자료구조를 사용하는 것이 가장 적합할까요?

답변:

정답은 해시 테이블 (Java의 HashMap) 입니다.

• HashMap<String, UserProfile> (Key: email, Value: 회원 정보 객체)

이유:

• 시간 복잡도: 해시 테이블은 평균 **O(1)**의 시간 복잡도로 데이터를 조회할 수 있습니다. 수백만 건의 데이터가 있더라도 email을 키로 사용하면 해시 함수를 통해 거의 즉시 원하는 회원 정보를 찾아낼 수 있습니다.
• 다른 자료구조와의 비교:
  • ArrayList: 모든 회원을 리스트에 담는다면, 특정 email을 찾기 위해 최악의 경우 모든 회원(n명)을 순차적으로 비교해야 합니다. (O(n))
  • 이진 탐색 트리: email 순으로 정렬된 트리에서 회원을 찾는다면 $O(\log n)$의 빠른 속도를 보여주겠지만, $O(1)$인 해시 테이블보다는 느립니다.
  • 따라서 '가장 빠른 검색'이라는 요구사항에는 해시 테이블이 가장 이상적인 선택입니다.