Home > Algorithm > 2024 > ๐Ÿ“ฆ[DS,Algorithm] ์ด์ง„ ํŠธ๋ฆฌ(Binary Tree)

๐Ÿ“ฆ[DS,Algorithm] ์ด์ง„ ํŠธ๋ฆฌ(Binary Tree)
DataStructure Algorithm

1๏ธโƒฃ ์ด์ง„ ํŠธ๋ฆฌ(Binary Tree).

์ด์ง„ ํŠธ๋ฆฌ(Binary Tree) ๋Š” ๊ฐ ๋…ธ๋“œ๊ฐ€ ์ตœ๋Œ€ ๋‘ ๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ํŠธ๋ฆฌ ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.

์ด ๋‘ ์ž์‹ ๋…ธ๋“œ๋Š” ์ผ๋ฐ˜์ ์œผ๋กœ ์™ผ์ชฝ ์ž์‹(Left Child) ๊ณผ ์˜ค๋ฅธ์ชฝ ์ž์‹(Right Child) ์ด๋ผ๊ณ  ๋ถˆ๋ฆฝ๋‹ˆ๋‹ค.

์ด์ง„ ํŠธ๋ฆฌ๋Š” ๋‹ค์–‘ํ•œ ์‘์šฉ ํ”„๋กœ๊ทธ๋žจ์—์„œ ์ค‘์š”ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.

1๏ธโƒฃ ์ด์ง„ ํŠธ๋ฆฌ์˜ ๊ตฌ์„ฑ ์š”์†Œ.

  • ๋…ธ๋“œ(Node) : ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋Š” ๊ธฐ๋ณธ ๋‹จ์œ„์ž…๋‹ˆ๋‹ค.
  • ๋ฃจํŠธ(Root) : ํŠธ๋ฆฌ์˜ ์ตœ์ƒ์œ„ ๋…ธ๋“œ์ž…๋‹ˆ๋‹ค.
  • ์ž์‹(Child) : ํŠน์ • ๋…ธ๋“œ๋กœ๋ถ€ํ„ฐ ์—ฐ๊ฒฐ๋œ ํ•˜์œ„ ๋…ธ๋“œ์ž…๋‹ˆ๋‹ค.
  • ๋ถ€๋ชจ(Parent) : ํŠน์ • ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๋Š” ์ƒ์œ„ ๋…ธ๋“œ์ž…๋‹ˆ๋‹ค.
  • ์žŽ(Leaf) : ์ž์‹ ๋…ธ๋“œ๊ฐ€ ์—†๋Š” ๋…ธ๋“œ์ž…๋‹ˆ๋‹ค.
  • ์„œ๋ธŒํŠธ๋ฆฌ(Subtree) : ํŠน์ • ๋…ธ๋“œ์™€ ๊ทธ ๋…ธ๋“œ์˜ ๋ชจ๋“  ์ž์‹ ๋…ธ๋“œ๋กœ ๊ตฌ์„ฑ๋œ ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

2๏ธโƒฃ ์ด์ง„ ํŠธ๋ฆฌ์˜ ์ข…๋ฅ˜.

  1. ํฌํ™” ์ด์ง„ ํŠธ๋ฆฌ(Full Binary Tree) : ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ 0๊ฐœ ๋˜๋Š” 2๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋Š” ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

  2. ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ(Complete Binary Tree) : ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ œ์™ธํ•œ ๋ชจ๋“  ๋ ˆ๋ฒจ์ด ์™„์ „ํžˆ ์ฑ„์›Œ์ ธ ์žˆ์œผ๋ฉฐ, ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์˜ ๋…ธ๋“œ๋Š” ์™ผ์ชฝ๋ถ€ํ„ฐ ์ฑ„์›Œ์ ธ ์žˆ๋Š” ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

  3. ๋†’์ด ๊ท ํ˜• ์ด์ง„ ํŠธ๋ฆฌ(Height-balanced binary Tree) : AVL ํŠธ๋ฆฌ์™€ ๊ฐ™์ด ๊ฐ ๋…ธ๋“œ์˜ ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์™€ ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๋†’์ด ์ฐจ์ด๊ฐ€ 1 ์ดํ•˜์ธ ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

  4. ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(Binary Search Tree, BST) : ์™ผ์ชฝ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ๋ฃจํŠธ ๋…ธ๋“œ๋ณด๋‹ค ์ž‘๊ณ , ์˜ค๋ฅธ์ชฝ ์„œ๋ธŒ ํŠธ๋ฆฌ์˜ ๋ชจ๋“  ๋…ธ๋“œ๊ฐ€ ๋ฃจํŠธ ๋…ธ๋“œ๋ณด๋‹ค ํฐ ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.

3๏ธโƒฃ ์ด์ง„ ํŠธ๋ฆฌ์˜ ์ฃผ์š” ์—ฐ์‚ฐ ๋ฐ ์‹œ๊ฐ„ ๋ณต์žก๋„.

  1. ์‚ฝ์ž…(Insertion) : ์ƒˆ๋กœ์šด ๋…ธ๋“œ๋ฅผ ํŠธ๋ฆฌ์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.
    • ์ผ๋ฐ˜์ ์ธ ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„ : O(log n)(์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์—์„œ)
    • ์ตœ์•…์˜ ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„ : O(n)(ํŽธํ–ฅ๋œ ํŠธ๋ฆฌ์—์„œ)
  2. ์‚ญ์ œ(Deletion) : ํŠธ๋ฆฌ์—์„œ ํŠน์ • ๋…ธ๋“œ๋ฅผ ์ œ๊ฑฐํ•ฉ๋‹ˆ๋‹ค.
    • ์ผ๋ฐ˜์ ์ธ ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„ : O(log n)(์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์—์„œ)
    • ์ตœ์•…์˜ ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„: O(n)(ํŽธํ–ฅ๋œ ํŠธ๋ฆฌ์—์„œ)
  3. ํƒ์ƒ‰(Search) : ํŠธ๋ฆฌ์—์„œ ํŠน์ • ๊ฐ’์„ ์ฐพ์Šต๋‹ˆ๋‹ค.
    • ์ผ๋ฐ˜์ ์ธ ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„: O(log n)(์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์—์„œ)
    • ์ตœ์•…์˜ ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„ : O(n)(ํŽธํ–ฅ๋œ ํŠธ๋ฆฌ์—์„œ)
  4. ์ˆœํšŒ(Traversal) : ํŠธ๋ฆฌ์˜ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•ฉ๋‹ˆ๋‹ค. ์ˆœํšŒ ๋ฐฉ๋ฒ•์—๋Š” ์ „์œ„(Preorder), ์ค‘์œ„(Inorder), ํ›„์œ„(Postorder) ์ˆœํšŒ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ์‹œ๊ฐ„ ๋ณต์žก๋„: O(n)(๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๊ธฐ ๋•Œ๋ฌธ์—)

4๏ธโƒฃ ์ด์ง„ ํŠธ๋ฆฌ์˜ ์˜ˆ์ œ

์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(BST)์˜ ๊ตฌํ˜„

// TreeNode
public class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;

  public TreeNode(int data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

// BinarySearchTree
public class BinarySearchTree {
  private TreeNode root;

  public BinarySearchTree() {
    this.root = null;
  }

  // ์‚ฝ์ž… ์—ฐ์‚ฐ
  public void insert(int data) {
    root = insertRec(root, data);
  }

  private TreeNode insertRec(TreeNode root, int data) {
    if (root == null) {
      root = new TreeNode(data);
      return root;
    }

    if (data < root.data) {
      root.left = insertRec(root.left, data);
    } else if (data > root.data) {
      root.right = insertRec(root.right, data);
    }
    return root;
  }

  // ํƒ์ƒ‰ ์—ฐ์‚ฐ
  public boolean search(int data) {
    return searchRec(root, data);
  }

  private boolean searchRec(TreeNode root, int data) {
    if (root == null) {
      return false;
    }

    if (root.data == data) {
      return true;
    }

    if (data < root.data) {
      return searchRec(root.left, data);
    } else {
      return searchRec(root.right, data);
    }
  }

  // ์ค‘์œ„ ์ˆœํšŒ(Inorder Traversal)
  public void inorder() {
    inorderRec(root);
  }

  private void inorderRec(TreeNode root) {
    if (root != null) {
      inorderRec(root.left);
      System.out.print(root.data + " ");
      inorderRec(root.right);
    }
  }
}

// Main
public class Main {

  public static void main(String[] args) {
    BinarySearchTree bst = new BinarySearchTree();

    bst.insert(50);
    bst.insert(30);
    bst.insert(20);
    bst.insert(40);
    bst.insert(70);
    bst.insert(60);
    bst.insert(80);

    System.out.println("Inorder traversal of the BST:");
    bst.inorder(); // ์ถœ๋ ฅ: 20 30 40 50 60 70 80

    System.out.println("\nSearch for 40: " + bst.search(40)); // ์ถœ๋ ฅ: true
    System.out.println("Search for 90: " + bst.search(90)); // ์ถœ๋ ฅ: false
  }
}