트리(Tree)

contability·2025년 7월 31일
비선형 자료구조자료구조
0

자료구조

목록 보기
8/8

정의

트리(Tree)는 노드(Node)들이 계층적으로 연결된 비선형 자료구조다. 하나의 루트 노드에서 시작하여 자식 노드들이 가지처럼 뻗어나가는 구조로, 사이클이 없는 연결된 그래프의 특수한 형태다.

기본 개념

      A (루트)
     / \
    B   C
   / \   \
  D   E   F
     /   / \
    G   H   I

주요 용어

  • 루트(Root): 최상위 노드 (A)
  • 부모(Parent): 상위 노드 (B는 D, E의 부모)
  • 자식(Child): 하위 노드 (D, E는 B의 자식)
  • 잎(Leaf): 자식이 없는 노드 (D, G, H, I)
  • 깊이(Depth): 루트부터 해당 노드까지의 거리
  • 높이(Height): 잎부터 해당 노드까지의 최대 거리
  • 레벨(Level): 같은 깊이에 있는 노드들의 집합

주요 연산

  • 삽입(Insert): 새로운 노드 추가
  • 삭제(Delete): 노드 제거
  • 탐색(Search): 특정 값을 가진 노드 찾기
  • 순회(Traversal): 모든 노드 방문
    • 전위순회(Pre-order): 루트 → 왼쪽 → 오른쪽
    • 후위순회(Post-order): 왼쪽 → 오른쪽 → 루트
    • 레벨순회(Level-order): 레벨별로 좌에서 우로

시간 복잡도

연산평균최악설명
탐색O(n)O(n)모든 노드를 확인해야 할 수 있음
삽입O(1)O(1)부모 노드에 직접 추가
삭제O(1)O(1)자식 관계만 끊으면 됨
순회O(n)O(n)모든 노드 방문

공간 복잡도

O(n) - 모든 노드를 저장

TypeScript 구현

기본 트리 노드

class TreeNode<T> {
  data: T;
  children: TreeNode<T>[];
  parent: TreeNode<T> | null;

  constructor(data: T) {
    this.data = data;
    this.children = [];
    this.parent = null;
  }

  addChild(child: TreeNode<T>): void {
    child.parent = this;
    this.children.push(child);
  }

  removeChild(child: TreeNode<T>): boolean {
    const index = this.children.indexOf(child);
    if (index !== -1) {
      this.children.splice(index, 1);
      child.parent = null;
      return true;
    }
    return false;
  }

  isLeaf(): boolean {
    return this.children.length === 0;
  }

  getDepth(): number {
    let depth = 0;
    let current = this.parent;
    while (current) {
      depth++;
      current = current.parent;
    }
    return depth;
  }

  getHeight(): number {
    if (this.isLeaf()) {
      return 0;
    }
    return 1 + Math.max(...this.children.map(child => child.getHeight()));
  }
}

일반 트리 클래스

class Tree<T> {
  root: TreeNode<T> | null;

  constructor() {
    this.root = null;
  }

  setRoot(data: T): TreeNode<T> {
    this.root = new TreeNode(data);
    return this.root;
  }

  // 전위순회 (Pre-order)
  preOrderTraversal(node: TreeNode<T> = this.root!, visit: (data: T) => void): void {
    if (!node) return;

    visit(node.data);
    for (const child of node.children) {
      this.preOrderTraversal(child, visit);
    }
  }

  // 후위순회 (Post-order)
  postOrderTraversal(node: TreeNode<T> = this.root!, visit: (data: T) => void): void {
    if (!node) return;

    for (const child of node.children) {
      this.postOrderTraversal(child, visit);
    }
    visit(node.data);
  }

  // 레벨순회 (Level-order / BFS)
  levelOrderTraversal(visit: (data: T) => void): void {
    if (!this.root) return;

    const queue: TreeNode<T>[] = [this.root];

    while (queue.length > 0) {
      const node = queue.shift()!;
      visit(node.data);

      for (const child of node.children) {
        queue.push(child);
      }
    }
  }

  // DFS로 노드 찾기
  findNode(data: T, node: TreeNode<T> = this.root!): TreeNode<T> | null {
    if (!node) return null;
    if (node.data === data) return node;

    for (const child of node.children) {
      const found = this.findNode(data, child);
      if (found) return found;
    }

    return null;
  }

  // 트리 높이
  getHeight(): number {
    return this.root ? this.root.getHeight() : -1;
  }

  // 노드 개수
  getSize(node: TreeNode<T> = this.root!): number {
    if (!node) return 0;

    let size = 1;
    for (const child of node.children) {
      size += this.getSize(child);
    }
    return size;
  }

  // 배열로 변환 (레벨 순서)
  toArray(): T[] {
    const result: T[] = [];
    this.levelOrderTraversal(data => result.push(data));
    return result;
  }
}

실생활 비유

조직도

  • CEO가 루트 노드
  • 각 부서장은 중간 노드
  • 일반 직원들은 잎 노드
  • 보고 체계가 부모-자식 관계

파일 시스템

  • 루트 디렉토리가 루트 노드
  • 폴더들이 중간 노드
  • 파일들이 잎 노드
  • 경로가 루트부터 해당 노드까지의 경로

가계도

  • 시조가 루트 노드
  • 각 세대가 레벨
  • 부모-자식 관계가 엣지
  • 후손이 없는 사람이 잎 노드

프론트엔드 활용 예시

파일 탐색기 컴포넌트

interface FileNode {
  name: string;
  type: 'file' | 'folder';
  children?: FileNode[];
}

const FileExplorer: React.FC<{ rootFolder: FileNode }> = ({ rootFolder }) => {
  const [expandedFolders, setExpandedFolders] = useState<Set<string>>(new Set());

  const toggleFolder = (folderName: string) => {
    setExpandedFolders(prev => {
      const newSet = new Set(prev);
      if (newSet.has(folderName)) {
        newSet.delete(folderName);
      } else {
        newSet.add(folderName);
      }
      return newSet;
    });
  };

  const renderNode = (node: FileNode, depth: number = 0): JSX.Element => {
    const isExpanded = expandedFolders.has(node.name);
    const indent = depth * 20;

    return (
      <div key={node.name}>
        <div
          style={{ paddingLeft: `${indent}px` }}
          className={`file-item ${node.type}`}
          onClick={() => node.type === 'folder' && toggleFolder(node.name)}
        >
          {node.type === 'folder' && (
            <span className="folder-icon">
              {isExpanded ? '📂' : '📁'}
            </span>
          )}
          {node.type === 'file' && <span className="file-icon">📄</span>}
          <span>{node.name}</span>
        </div>

        {node.type === 'folder' && isExpanded && node.children && (
          <div className="folder-contents">
            {node.children.map(child => renderNode(child, depth + 1))}
          </div>
        )}
      </div>
    );
  };

  return (
    <nav className="file-explorer" role="tree">
      {renderNode(rootFolder)}
    </nav>
  );
};

메뉴 네비게이션

interface MenuItem {
  id: string;
  label: string;
  url?: string;
  children?: MenuItem[];
}

const NavigationMenu: React.FC<{ menuItems: MenuItem[] }> = ({ menuItems }) => {
  const [activeMenu, setActiveMenu] = useState<string | null>(null);

  const renderMenuItem = (item: MenuItem, level: number = 0): JSX.Element => {
    const hasChildren = item.children && item.children.length > 0;
    const isActive = activeMenu === item.id;

    return (
      <li key={item.id} className={`menu-item level-${level}`}>
        <button
          className={`menu-button ${isActive ? 'active' : ''}`}
          onClick={() => setActiveMenu(isActive ? null : item.id)}
          aria-expanded={hasChildren ? isActive : undefined}
          aria-haspopup={hasChildren ? 'menu' : undefined}
        >
          {item.label}
          {hasChildren && (
            <span className="menu-arrow" aria-hidden="true">
              {isActive ? '▼' : '▶'}
            </span>
          )}
        </button>

        {hasChildren && isActive && (
          <ul className="submenu" role="menu">
            {item.children!.map(child => renderMenuItem(child, level + 1))}
          </ul>
        )}
      </li>
    );
  };

  return (
    <nav role="menubar">
      <ul className="main-menu">
        {menuItems.map(item => renderMenuItem(item))}
      </ul>
    </nav>
  );
};

사용 예시

// 트리 생성
const orgChart = new Tree<string>();

// 루트 설정
const ceo = orgChart.setRoot("CEO");

// 부서장들 추가
const cto = new TreeNode("CTO");
const cfo = new TreeNode("CFO");
const cmo = new TreeNode("CMO");

ceo.addChild(cto);
ceo.addChild(cfo);
ceo.addChild(cmo);

// 개발팀 추가
const frontendLead = new TreeNode("Frontend Lead");
const backendLead = new TreeNode("Backend Lead");

cto.addChild(frontendLead);
cto.addChild(backendLead);

// 순회해서 출력
console.log("전체 조직:");
orgChart.preOrderTraversal((name) => console.log(name));

// 특정 직책 찾기
const found = orgChart.findNode("Frontend Lead");
console.log(`깊이: ${found?.getDepth()}`); // 2

장점

  • 계층적 구조 표현: 자연스러운 계층 관계 모델링
  • 유연한 구조: 각 노드마다 다른 수의 자식 가능
  • 직관적: 실세계의 많은 구조와 유사
  • 확장성: 동적으로 노드 추가/제거 가능

단점

  • 비효율적 탐색: 특정 노드 찾기 위해 O(n) 시간 필요
  • 구조 제약 없음: 성능 최적화가 어려움
  • 메모리 오버헤드: 각 노드마다 자식 배열 필요
  • 불균형: 한쪽으로 치우칠 수 있음

활용 사례

  • 조직도: 회사, 정부 기관의 계층 구조
  • 파일 시스템: 폴더와 파일의 계층 구조
  • 웹 개발: HTML DOM, React 컴포넌트 트리
  • 메뉴 시스템: 다단계 네비게이션 메뉴
  • 분류 체계: 카테고리, 태그 시스템

다음에는 이진 트리에 대해 알아보자. 이진 트리는 각 노드가 최대 2개의 자식만 가질 수 있는 특별한 형태의 트리다.

profile
contability
이전 포스트

덱 (Deque)

0개의 댓글