이진탐색트리(Binary Search Tree)의 핵심: 탐색, 구조, 순회 방법 쉽게 배우기

안녕하세요, 스터디 4주차입니다. 이번에는 트리(Tree) 자료구조에 대해서 알아보려고 합니다.
트리가 무엇이고, 왜 사용하는지? 그리고 가장 많이 사용하는 이진트리(Binary Tree)와 이진탐색트리(Binary Tree)까지 이야기 해보겠습니다. 도움이 되는 글이었으면 좋겠습니다. 😄

1. 트리(Tree) 자료구조가 뭐지?

트리(Tree) 자료구조는 그래프의 일종으로, 노드와 간선으로 이루어진 계층적 방향 그래프를 말합니다. (부모 - 자식 관계)

나무가 가지를 치는 모양처럼 생겨 흔히 회사의 조직도나 파일시스템 같이 위 아래 계층을 나타낼 때 많이 쓰입니다.
또한 상위노드에서 하위노드로 연결되는 방향성이 있기 때문에, 위에서 아래로 내려가면 다시 올라갈 수 없게 순환을 허용하지 않습니다.

1.1. 트리에서 사용하는 용어를 알아보면...

노드(Node) : 데이터를 표현하는 하나의 덩어리를 말합니다. 위 그림의 A, B 같은 것들을 노드라고 부릅니다.
간선(Edge) : 각 노드를 연결하는 선을 간선이라고 부릅니다.
자식 노드(Child Node) : 간선으로 연결된 노드에서 아래에 있는 노드를 자식노드라고 부릅니다. 위그림에서 B와 C는 A의 자식노드 입니다.
부모 노드(Parent Node) : 자식노드의 관점에서 위에 있는 노드는 부모노드라고 부릅니다.
루트 노드(Root Node) : 트리에서 가장 위에 있는 노드를 말합니다.
리프 노드(Leaf Node) 또는 단말노드(Terminal Node) : 자식 노드가 없는 가장 아래의 노드를 리프 노드 또는 터미널 노드라고 부릅니다. 예를 들어, 위 그림에서 H, I, F, G 는 리프 노드입니다.
인터널 노드 (Internal Node) : 자식 노드가 하나라도 존재하는 내부의 노드를 말합니다.
서브트리(Subtree): 특정 노드를 루트로 하는 모든 하위 노드의 집합을 말합니다.
레벨(Level): 트리의 깊이를 나타내며, 루트 노드를 기준으로 0부터 시작합니다. 자식 노드는 부모 노드보다 한 레벨 아래에 있습니다.
높이(Height): 루트 노드에서 리프 노드까지의 가장 긴 경로의 길이를 말합니다.

2. 이진 트리 (Binary Tree)

이진 트리는 트리 구조 중에서도 가장 많이 쓰이는 트리입니다. 이진 트리의 주요 특징은 각각의 노드가 최대 두 개의 자식 노드를 가질 수 있다는 규칙이 추가된다는 점입니다. 이는 트리의 복잡성을 줄이고, 다양한 알고리즘에서 효율적으로 사용할 수 있도록 도와줍니다. 위 그림에서 왼쪽의 트리는 이진 트리이며, 각각의 노드가 두 개 이하의 자식 노드를 가집니다. 반면, 오른쪽의 트리는 자식 노드가 2개를 초과하기 때문에 이진 트리가 아닙니다.

3. 이진 트리를 표현하는 방법

구현의 영역으로 넘어가서 일반적인 두 가지 표현 방법으로는 배열 표현과 인접 리스트 표현이 있습니다.

3.1. 이진트리(BinaryTree)의 배열 표현

이진 트리를 배열로 표현하는 방법은 노드를 인덱스에 따라 배열의 원소로 배치하는 것입니다. 일반적으로, 루트 노드는 인덱스 1에 위치하며, 각 노드의 자식 노드는 다음과 같은 규칙에 따라 배열에 배치됩니다:

인덱스 i에 있는 노드의 왼쪽 자식은 인덱스 i * 2에 위치
인덱스 i에 있는 노드의 오른쪽 자식은 인덱스 i * 2 + 1에 위치
인덱스 공식만 활용하므로 구현난이도가 낮고, 빈공간이 많음

3.2. 이진트리(BinaryTree)의 인접리스트 표현

인접 리스트 표현은 각 노드에 연결된 자식 노드들을 리스트로 관리하는 방식입니다. 이를 통해 각 노드가 가리키는 자식 노드를 동적으로 관리할 수 있으며, 노드의 수가 많고 구조가 복잡한 경우 메모리를 절약할 수 있습니다.

각 리스트의 인덱스는 부모노드
자식 노드는 부모노드에 해당되는 인덱스에 추가

4. 이진트리를 순회하는 방법

이진 트리를 순회하는 방법은 여러 가지가 있으며, 각 방법은 트리의 노드를 방문하는 순서에 따라 다릅니다.

4.1. 전위 순회 (preorder traversal)

전위 순회는 루트 노드를 먼저 방문한 후, 왼쪽 서브트리와 오른쪽 서브트리를 순회하는 방법입니다. 전위 순회의 순서는 다음과 같습니다. 주로 트리 구조를 복제하거나, 트리의 노드 값을 출력할 때 사용합니다.

현재 노드 방문
왼쪽 서브트리 방문
오른쪽 서브트리 방문

구현

public class BinaryTree {
  private int data;
  private BinaryTree leftSubTree;
  private BinaryTree rightSubTree;

  public BinaryTree(int data) {
    this.data = data;
    this.leftSubTree = null;
    this.rightSubTree = null;
  }
  
  // 전위 순회 : (루트 노드를 먼저 방문하고, 그 다음 노드들을 방문하는 것)
  void preOrderTraversal(BinaryTree tree) {
    // 기저조건
    if (tree == null) return;
    // 루트 -> 왼쪽 -> 오른쪽
    System.out.println(tree.getData());
    preOrderTraversal(tree.getLeftSubTree());
    preOrderTraversal(tree.getRightSubTree());
  }
 }

4.2. 중위 순회 (Inorder traversal)

중위 순회는 왼쪽 서브트리를 먼저 방문한 후, 루트 노드를 방문하고, 마지막으로 오른쪽 서브트리를 방문하는 방법입니다. 중위 순회의 순서는 다음과 같습니다. 이진 탐색 트리에서 노드 값을 정렬된 순서로 출력하는 데 유용합니다.

왼쪽 서브트리 방문
현재 노드 방문
오른쪽 서브트리 방문

구현

public class BinaryTree {
  
  // 중위 순회 : (왼쪽 노드를 먼저 방문하고, 그다음의 자신의 노드, 그다음 오른쪽 노드를 방문)
  void inOrderTraversal(BinaryTree tree) {
    // 기저조건
    if(tree == null) return;
    // 왼쪽 -> 루트 -> 오른쪽
    inOrderTraversal(tree.getLeftSubTree());
    System.out.println(tree.getData());
    inOrderTraversal(tree.getRightSubTree());
  }
 }

4.3. 후위 순회 (postorder traversal)

후위 순회는 왼쪽 서브트리와 오른쪽 서브트리를 먼저 방문한 후, 마지막으로 루트 노드를 방문하는 방법입니다. 후위 순회의 순서는 다음과 같습니다. 폴더 삭제처럼 트리의 제일 깊은 노드부터 삭제할 때 사용합니다.

왼쪽 서브트리 방문
오른쪽 서브트리 방문
현재 노드 방문

구현

public class BinaryTree {
  
  // 후위 순회 : (자식 노드들을 먼저 방문하고, 자신의 노드를 방문)
  void postOrderTraversal(BinaryTree tree) {
    // 기저조건
    if(tree == null) return;
    // 왼쪽 -> 오른쪽 -> 루트
    postOrderTraversal(tree.getLeftSubTree());
    postOrderTraversal(tree.getRightSubTree());
    System.out.println(tree.getData());
  }
 }

4.4 순회 테스트 코드

public static void main(String[] args) {
    BinaryTree tree1 = new BinaryTree(1);
    BinaryTree tree2 = new BinaryTree(2);
    BinaryTree tree3 = new BinaryTree(3);
    BinaryTree tree4 = new BinaryTree(4);
    BinaryTree tree5 = new BinaryTree(5);
    BinaryTree tree6 = new BinaryTree(6);
    BinaryTree tree7 = new BinaryTree(7);

    tree1.setLeftSubTree(tree2);
    tree1.setRightSubTree(tree3);
    tree2.setLeftSubTree(tree4);
    tree2.setRightSubTree(tree5);
    tree3.setLeftSubTree(tree6);
    tree3.setRightSubTree(tree7);

    System.out.println("루트노드의 오른쪽 자식노드 = " + tree1.getRightSubTree().getData());
    System.out.println("루트노드의 오른쪽 자식노드의 왼쪽 자식노드 = "
                           + tree1.getRightSubTree().getLeftSubTree().getData());

    // 트리를 전체 출력하려면, 재귀를 이용할 수 있음
    System.out.println("전위 순회");
    tree1.preOrderTraversal(tree1);
    // 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

    System.out.println("중위 순회");
    tree1.inOrderTraversal(tree1);
    // 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7

    System.out.println("후위 순회");
    tree1.postOrderTraversal(tree1);
    // 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
    
  }

5. 이진 탐색 알고리즘은 들어봤니?

이진 탐색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 배열에서 특정한 값의 위치를 찾는 알고리즘입니다. 처음 임의의 값을 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교해서 찾아나가는 방식의 알고리즘 입니다.

업 and 다운 게임 해보셨나요?

내가 생각하는 숫자(33) 맞춰봐.!! 40 -> 다운, 20 -> 업, 30 -> 업, 34 -> 다운, 33 -> 정답 ㅎㅎ

쌩뚱맞게, 왠 알고리즘이라고 하시겠지만, 이진 탐색 알고리즘을 알고 있어야지 이진 탐색 트리를 설명할 수 있으니 이해해주세요.

5.1. 이진 탐색 알고리즘의 문제점

그러면 이진 탐색 트리를 설명하기 위해 이진 탐색 알고리즘을 설명했다고 했었죠? 이진 탐색 트리를 고려해야 하는 이유는 이진 탐색 알고리즘에 치명적인 문제점 때문입니다. 바로 배열로 되어있는 데이터들은 정렬되어 있어야 한다는 것 그리고, 배열은 데이터의 삽입과 제거에 많은 비용이 드는 것 입니다. 좀 더 나은게 없을까? 똑똑한 컴퓨터 과학자들이 가만히 있을수는 없겠죠? ㅎㅎ

6. 이진 탐색 트리(Binary Search Tree)

만약에 사용자가 삽입과 제거를 자주 하면서 탐색도 자주한다면? 어떤 자료구조를 사용하는게 좋을까요?

이전 주차에서 배웠던 해시테이블을 떠올릴 수 있는데, 해시테이블 자료구조는 테이블을 만들어야 하기때문에, 메모리가 많이 필요합니다. 그래서 이진 탐색 알고리즘의 장점만 취하고 단점은 제거한 이진 탐색 트리가 생겨났습니다. 해시 테이블처럼 삽입, 삭제, 탐색에 빠른 성능을 가지며, 메모리의 낭비 또한 없습니다.

이진 탐색 트리는 기본적으로 자식노드가 최대 두개 까지만 있고, 자식노드의 트리도 모두 이진트리의 모습을하고 있습니다.

다만 몇가지 규칙이 추가됩니다.

6.1. 이진 탐색 트리의 규칙

이진트리에서 아래의 규칙만 추가하면 이진 탐색트리가 됩니다.

유일성: 각 노드의 값은 유일하며, 중복된 값이 허용되지 않습니다.
왼쪽 자식 노드: 왼쪽 서브트리의 모든 노드는 부모 노드의 값보다 작아야 합니다.
오른쪽 자식 노드: 오른쪽 서브트리의 모든 노드는 부모 노드의 값보다 커야 합니다.

7. 이진 탐색 트리도 단점은 존재해

이진 탐색 트리도 단점이 존재하는데, 이로 인해 성능이 저하될 수 있습니다. 특히, 트리가 불균형하게 성장할 경우 성능 문제가 발생합니다.

위 그림처럼 노드를 삽입할 때 작은 데이터부터 먼저 삽입한다면 어떻게 될까요? 완전히 균형이 틀어져 한쪽으로만 치우치게 되지 않나요? 혹은 한쪽 방향의 노드들만 계속해서 제거한다면? 균형이 맞지 않게 되어 성능의 이점을 잃어 버리게 되는거죠. 이러면 그냥 연결리스트와 다를바가 없네요 ㅎㅎ

7.1. 그래서 균형 이진 트리라는 것도 있어

이러한 단점을 극복하기 위해 균형을 맞춰주는 트리들이 존재합니다.

대표적으로 Red-Black Tree나 AVL Tree가 있는데, 이러한 트리들은 노드 삽입 및 삭제 시 트리의 균형을 자동으로 조정하여 균형을 유지합니다. 많이 복잡하고, 짧은 글로 이해하기에는 다뤄야할 내용이 많기 때문에 정말 간단히만 알아보고 넘어가야 할 것 같네요.

AVL Tree

AVL 트리는 삽입 및 삭제 시 회전 연산을 통해 각 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1이 되도록 유지하게 하여, 모든 연산의 시간 복잡도를 O(log n)으로 보장합니다.

Red-Black Tree

레드블랙 트리(Red-Black Tree)는 각 노드에 색깔(빨간색 또는 검은색)을 부여하여 트리의 균형을 유지하는 이진 탐색 트리입니다. 적절한 색상 규칙과 회전을 통해 트리의 높이를 조절하여 균형을 유지하는데 삽입, 삭제 시에도 O(log n) 시간 복잡도를 보장합니다.

트리(Tree) 자료구조 부터 이진탐색트리(Binary Search Tree)를 살펴봤습니다.
트리에 대해서 조금 친해지셨나요? 더 나아가서 대부분 트리와 같은 자료구조에서는 더 최적화된 Red-Black Tree나 AVL Tree와 같은 균형 이진트리를 사용하게 되는데 관심 있으시면 찾아 보셨으면 좋겠네요. 저도 기회가 된다면 균형 이진트리인 Red-Black Tree나 데이터베이스 인덱스에 많이 사용하는 B, B+트리 같은 것도 정리 해보고 싶네요 ㅎㅎ

부족한 글 읽어 주셔서 감사합니다. 또한 잘못된 내용 있으면 지적해주시면 감사하겠습니다. 🙏

하얀종이 개발자

Reference

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0 - 트리구조 위키피디아

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC - 이진트리 위키피디아

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C - 트리순회 위키피디아

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 - 이진 탐색 알고리즘

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC - 이진 탐색 트리 위키피디아

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC - 레드블랙 트리 위키피디아

https://ko.wikipedia.org/wiki/AVL_%ED%8A%B8%EB%A6%AC - AVL 트리 위키피디아

https://www.youtube.com/watch?v=CXiVJgUjL6o - 코딩테스트 합격자 되기 c++편 - 트리

https://goldenrabbit.co.kr/product/cpppass/ - (골든래빗) 코딩테스트 합격자 되기 c++편 - 책소개

'Algorithm & Data Structure' 카테고리의 다른 글

그래프 탐색 완벽 가이드: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) (0)	2024.08.27
Union-Find로 배우는 집합(Set) 알고리즘: 개념부터 구현까지 (0)	2024.08.10
해시(Hash) 함수와 충돌(Collision) 해결 전략: 효율적인 데이터 관리 (0)	2024.07.29
선형 자료구조 탐구: 스택, 큐, 덱으로 배우는 알고리즘 기초 (0)	2024.07.19
코딩 테스트 필수 개념: 시간 복잡도를 알면 문제 해결이 쉬워진다 (2)	2024.07.12

하얀종이개발자

이진탐색트리(Binary Search Tree)의 핵심: 탐색, 구조, 순회 방법 쉽게 배우기

1. 트리(Tree) 자료구조가 뭐지?

1.1. 트리에서 사용하는 용어를 알아보면...

2. 이진 트리 (Binary Tree)

3. 이진 트리를 표현하는 방법

3.1. 이진트리(BinaryTree)의 배열 표현

3.2. 이진트리(BinaryTree)의 인접리스트 표현

4. 이진트리를 순회하는 방법

4.1. 전위 순회 (preorder traversal)

구현

4.2. 중위 순회 (Inorder traversal)

구현

4.3. 후위 순회 (postorder traversal)

구현

4.4 순회 테스트 코드

5. 이진 탐색 알고리즘은 들어봤니?

5.1. 이진 탐색 알고리즘의 문제점

6. 이진 탐색 트리(Binary Search Tree)

6.1. 이진 탐색 트리의 규칙

7. 이진 탐색 트리도 단점은 존재해

7.1. 그래서 균형 이진 트리라는 것도 있어

Reference

'Algorithm & Data Structure' 카테고리의 다른 글

티스토리툴바

이진탐색트리(Binary Search Tree)의 핵심: 탐색, 구조, 순회 방법 쉽게 배우기

1. 트리(Tree) 자료구조가 뭐지?

1.1. 트리에서 사용하는 용어를 알아보면...

2. 이진 트리 (Binary Tree)

3. 이진 트리를 표현하는 방법

3.1. 이진트리(BinaryTree)의 배열 표현

3.2. 이진트리(BinaryTree)의 인접리스트 표현

4. 이진트리를 순회하는 방법

4.1. 전위 순회 (preorder traversal)

구현

4.2. 중위 순회 (Inorder traversal)

구현

4.3. 후위 순회 (postorder traversal)

구현

4.4 순회 테스트 코드

5. 이진 탐색 알고리즘은 들어봤니?

5.1. 이진 탐색 알고리즘의 문제점

6. 이진 탐색 트리(Binary Search Tree)

6.1. 이진 탐색 트리의 규칙

7. 이진 탐색 트리도 단점은 존재해

7.1. 그래서 균형 이진 트리라는 것도 있어

Reference

'Algorithm & Data Structure' 카테고리의 다른 글

'Algorithm & Data Structure' Related Articles

티스토리툴바