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

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

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

์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ(Complete Binary Tree)๋Š” ์ด์ง„ ํŠธ๋ฆฌ์˜ ํ•œ ์ข…๋ฅ˜์ž…๋‹ˆ๋‹ค.

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

  1. ๋ชจ๋“  ๋ ˆ๋ฒจ์ด ์™„์ „ํžˆ ์ฑ„์›Œ์ ธ ์žˆ๋‹ค.
    • ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ œ์™ธํ•œ ๋ชจ๋“  ๋ ˆ๋ฒจ์˜ ๋…ธ๋“œ๊ฐ€ ์ตœ๋Œ€ ๊ฐœ์ˆ˜๋กœ ์ฑ„์›Œ์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์˜ ๋…ธ๋“œ๋“ค์€ ์™ผ์ชฝ๋ถ€ํ„ฐ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ฑ„์›Œ์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  2. ๋…ธ๋“œ์˜ ๋ฐฐ์น˜
    • ํŠธ๋ฆฌ์˜ ๋†’์ด๊ฐ€ โ€˜hโ€™ ๋ผ๋ฉด, ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ œ์™ธํ•œ ๋ชจ๋“  ๋ ˆ๋ฒจ์—๋Š” โ€˜2^kโ€™ ๊ฐœ์˜ ๋…ธ๋“œ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ โ€˜kโ€™ ๋Š” ํ•ด๋‹น ๋ ˆ๋ฒจ์˜ ๊นŠ์ด ์ž…๋‹ˆ๋‹ค.
    • ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์—๋Š” 1๊ฐœ ์ด์ƒ โ€˜2^hโ€™ ๊ฐœ ์ดํ•˜์˜ ๋…ธ๋“œ๊ฐ€ ์žˆ์œผ๋ฉฐ, ์ด ๋…ธ๋“œ๋“ค์€ ์™ผ์ชฝ๋ถ€ํ„ฐ ์ฑ„์›Œ์ง‘๋‹ˆ๋‹ค.

2๏ธโƒฃ ์™„์ „ ์ด์นœ ํŠธ๋ฆฌ์˜ ์˜ˆ.

        1
      /   \
     2     3
    / \   / \
   4   5 6   7
  / \
 8   9

์œ„์˜ ํŠธ๋ฆฌ๋Š” ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ์˜ ์˜ˆ์ž…๋‹ˆ๋‹ค.

๋ชจ๋“  ๋ ˆ๋ฒจ์ด ์™„์ „ํžˆ ์ฑ„์›Œ์ ธ ์žˆ๊ณ , ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์˜ ๋…ธ๋“œ๋“ค์€ ์™ผ์ชฝ๋ถ€ํ„ฐ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ฑ„์›Œ์ ธ์žˆ์Šต๋‹ˆ๋‹ค.

3๏ธโƒฃ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ์˜ ์†์„ฑ.

  1. ๋…ธ๋“œ ์ˆ˜
    • ๋†’์ด๊ฐ€ โ€˜hโ€™ ์ธ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋Š” ์ตœ๋Œ€ โ€˜2^(h+1) - 1โ€™ ๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ œ์™ธํ•œ ๋ชจ๋“  ๋…ธ๋“œ๋Š” โ€˜2^h - 1โ€™ ๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง‘๋‹ˆ๋‹ค.
  2. ๋†’์ด
    • ๋…ธ๋“œ ์ˆ˜๊ฐ€ โ€˜nโ€™ ์ธ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ์˜ ๋†’์ด๋Š” โ€˜O(log n)โ€™ ์ž…๋‹ˆ๋‹ค.
  3. ๋ฐฐ์—ด ํ‘œํ˜„
    • ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋Š” ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ ์‰ฝ๊ฒŒ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋Š” ํž™ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ ๋งŽ์ด ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.

4๏ธโƒฃ ๋ฐฐ์—ด์„ ํ†ตํ•œ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ํ‘œํ˜„

์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋Š” ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ ํšจ์œจ์ ์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค๋ฅผ ๊ธฐ์ค€์œผ๋กœ ๋ถ€๋ชจ-์ž์‹ ๊ด€๊ณ„๋ฅผ ์‰ฝ๊ฒŒ ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋…ธ๋“œ์˜ ์ธ๋ฑ์Šค ๊ทœ์น™

  • ๋ฃจํŠธ ๋…ธ๋“œ : ์ธ๋ฑ์Šค 0
  • ์ธ๋ฑ์Šค โ€˜iโ€™์˜ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ : โ€˜2*i + 1โ€™
  • ์ธ๋ฑ์Šค โ€˜iโ€™์˜ ๋ถ€๋ชจ ๋…ธ๋“œ : โ€˜(i - 1) / 2โ€™

5๏ธโƒฃ ์˜ˆ์ œ ์ฝ”๋“œ

์•„๋ž˜๋Š” ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ๋ฐฐ์—ด๋กœ ํ‘œํ˜„ํ•˜๊ณ , ์ด๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๊ฐ„๋‹จํ•œ ์˜ˆ์ œ ์ฝ”๋“œ์ž…๋‹ˆ๋‹ค.

public class CompleteBinaryTree {

  public static void main(String[] args) {
    int[] tree = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    // ํŠธ๋ฆฌ ์ถœ๋ ฅ
    printTree(tree);
  }

  // ๋ฐฐ์—ด๋กœ ํ‘œํ˜„๋œ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ์ถœ๋ ฅ
  public static void printTree(int[] tree) {
    for (int i = 0; i < tree.length; i++) {
      int leftChildIndex = 2 * i + 1;
      int rightChildIndex = 2 * i + 2;

      System.out.print("Node " + tree[i] + ": ");

      if (leftChildIndex < tree.length) {
        System.out.print("Left Child: " + tree[leftChildIndex] + ", ");
      } else {
        System.out.print("Left Child: null, ");
      }

      if (rightChildIndex < tree.length) {
        System.out.print("Right Child: " + tree[rightChildIndex]);
      } else {
        System.out.print("Right Child: null");
      }
      System.out.println();
    }
  }
}

/* ์ถœ๋ ฅ
Node 1: Left Child: 2, Right Child: 3
Node 2: Left Child: 4, Right Child: 5
Node 3: Left Child: 6, Right Child: 7
Node 4: Left Child: 8, Right Child: 9
Node 5: Left Child: null, Right Child: null
Node 6: Left Child: null, Right Child: null
Node 7: Left Child: null, Right Child: null
Node 8: Left Child: null, Right Child: null
Node 9: Left Child: null, Right Child: null
*/

์„ค๋ช…

  1. ํŠธ๋ฆฌ ๋ฐฐ์—ด ์ดˆ๊ธฐํ™” : int[] tree = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    • ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ๋ฐฐ์—ด๋กœ ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค.
  2. ํŠธ๋ฆฌ ์ถœ๋ ฅ : printTree(tree)
    • ๋ฐฐ์—ด๋กœ ํ‘œํ˜„๋œ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ•จ์ˆ˜์ž…๋‹ˆ๋‹ค.
    • ๊ฐ ๋…ธ๋“œ์— ๋Œ€ํ•ด ์™ผ์ชฝ ์ž์‹๊ณผ ์˜ค๋ฅธ์ชฝ ์ž์‹์„ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.

์‹œ๊ฐ„ ๋ณต์žก๋„

  • ์‚ฝ์ž…(Insertion) : O(log n)
  • ์‚ญ์ œ(Deletion) : O(log n)
  • ํƒ์ƒ‰(Search) : O(n) (์ผ๋ฐ˜์ ์œผ๋กœ ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋Š” ํƒ์ƒ‰๋ณด๋‹ค ์‚ฝ์ž…/์‚ญ์ œ๊ฐ€ ์ฃผ๋œ ์—ฐ์‚ฐ์ž…๋‹ˆ๋‹ค.)

์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋Š” ๋ฐ์ดํ„ฐ์˜ ๊ตฌ์กฐ์  ํŠน์„ฑ ๋•Œ๋ฌธ์— ํž™๊ณผ ๊ฐ™์€ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ ๋งŽ์ด ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.
์ด๋Š” ํšจ์œจ์ ์ธ ์‚ฝ์ž… ๋ฐ ์‚ญ์ œ ์—ฐ์‚ฐ์„ ์ œ๊ณตํ•˜๋ฉฐ, ๋ฐฐ์—ด์„ ํ†ตํ•œ ํ‘œํ˜„์ด ๊ฐ„ํŽธํ•˜์—ฌ ๋‹ค์–‘ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ์œ ์šฉํ•˜๊ฒŒ ์‚ฌ์šฉ๋ฉ๋‹ˆ๋‹ค.