이진 탐색 트리를 배열로 표현하기

4/13/2023
46 minutes to read

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 다양한 프로그래밍 언어를 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

예제

이진 탐색 트리를 배열로 표현하는 C# 언어 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 C# 언어를 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

코드: binary_search_tree_array.cs

Node 클래스 정의

class Node {
    public int PrevNode; // 왼쪽 부분 트리를 가리키는 포인터
    public string Name; // 이름 저장
    public int NextNode; // 오른쪽 부분 트리를 가리키는 포인터
}

Node 클래스는 이진 탐색 트리의 노드를 나타내며, 왼쪽 자식 노드를 가리키는 PrevNode, 이름을 저장하는 Name, 그리고 오른쪽 자식 노드를 가리키는 NextNode를 가지고 있습니다.

이진 탐색 트리 초기화

Node[] tree = new Node[] {
    new Node { PrevNode = 1, Name = "mm", NextNode = 2 }, // 0
    new Node { PrevNode = 3, Name = "cc", NextNode = 4 }, // 1
    new Node { PrevNode = 5, Name = "rr", NextNode = -1 }, // 2
    new Node { PrevNode = -1, Name = "aa", NextNode = -1 }, // 3
    new Node { PrevNode = 6, Name = "ee", NextNode = 7 }, // 4
    new Node { PrevNode = -1, Name = "nn", NextNode = -1 }, // 5
    new Node { PrevNode = -1, Name = "dd", NextNode = -1 }, // 6
    new Node { PrevNode = -1, Name = "ll", NextNode = -1 } // 7
};

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다.

특정 값 찾기

Console.Write("찾을 내용(aa~zz) : ");
string key = Console.ReadLine();
int current = 0;
while (current != -1) {
    if (key == tree[current].Name) {
        Console.WriteLine("찾았습니다.");
        break;
    }
    else if (string.Compare(key, tree[current].Name) < 0) {
        current = tree[current].PrevNode; // 왼쪽 부분 트리로 이동
    }
    else {
        current = tree[current].NextNode; // 오른쪽 부분 트리로 이동
    }
}

사용자로부터 찾고자 하는 값을 입력받아 이진 탐색 트리를 순회하며 값을 찾습니다. 찾고자 하는 값이 현재 노드의 값보다 작으면 왼쪽 자식 노드로 이동하고, 크면 오른쪽 자식 노드로 이동합니다. 이 과정을 반복하여 찾고자 하는 값을 발견하면 "찾았습니다."라는 메시지를 출력합니다. 만약 찾고자 하는 값이 트리에 존재하지 않으면 루프에서 빠져나옵니다.

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이진 탐색 트리를 순회하는 동안에는 항상 정렬된 상태를 유지하므로 탐색 시간이 일반적으로 O(log n)입니다. 따라서 이진 탐색 트리는 정렬된 데이터에 대한 빠른 검색을 수행할 수 있는 효율적인 데이터 구조입니다.

이 글에서는 이진 탐색 트리를 배열로 표현하는 C# 언어 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다.

이진 탐색 트리를 배열로 표현하는 C 언어 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 C 언어를 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

코드: binary_search_tree_array.c

Node 구조체 정의

struct Node {
    int prev_node;       //왼쪽 부분 트리를 가리키는 포인터
    char name[25];   //이름 저장
    int next_node;       //오른쪽 부분 트리를 가리키는 포인터
};

Node 구조체는 이진 탐색 트리의 노드를 나타내며, 왼쪽 자식 노드를 가리키는 prev_node, 이름을 저장하는 name, 그리고 오른쪽 자식 노드를 가리키는 next_node를 가지고 있습니다.

이진 탐색 트리 초기화

struct Node tree[MAX_SIZE] = {
      {1, "mm", 2},       //0
      {3, "cc", 4},       //1
      {5, "rr", NIL},     //2
      {NIL, "aa", NIL},   //3
      {6, "ee", 7},       //4
      {NIL, "nn", NIL},   //5
      {NIL, "dd", NIL},   //6
      {NIL, "ll", NIL}    //7
};

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다.

특정 값 찾기

printf("찾을 내용(aa~zz) : ");
scanf("%s", key);
current = 0;
while (current != NIL) {
    if (strcmp(key, tree[current].name) == 0) {
        printf("찾았습니다.\n");
        break;
    }
    else if (strcmp(key, tree[current].name) < 0) {
        current = tree[current].prev_node; //왼쪽 부분 트리로 이동
    }
    else {
        current = tree[current].next_node; //오른쪽 부분 트리로 이동
    }
}

전체 소스 코드는 다음과 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

#define NIL -1	//아무것도 가리키지 않는 포인터
#define MAX_SIZE 10

struct Node {
    int prev_node;		//왼쪽 부분 트리를 가리키는 포인터
    char name[25];	//이름 저장
    int next_node;		//오른쪽 부분 트리를 가리키는 포인터
};

int main(void) {
    struct Node tree[MAX_SIZE] = {
      {1, "mm", 2},       //0
      {3, "cc", 4},       //1
      {5, "rr", NIL},     //2
      {NIL, "aa", NIL},   //3
      {6, "ee", 7},       //4
      {NIL, "nn", NIL},   //5
      {NIL, "dd", NIL},   //6
      {NIL, "ll", NIL}    //7
    };

    char key[20];
    int current;

    printf("찾을 내용(aa~zz) : ");
    scanf("%s", key);
    current = 0;
    while (current != NIL) {
        if (strcmp(key, tree[current].name) == 0) {
            printf("찾았습니다.\n");
            break;
        }
        else if (strcmp(key, tree[current].name) < 0) {
            current = tree[current].prev_node;	//왼쪽 부분 트리로 이동
        }
        else {
            current = tree[current].next_node;	//오른쪽 부분 트리로 이동
        }
    }

    return 0;
}
/*
찾을 내용(aa~zz) : aa
찾았습니다.
*/

찾을 내용(aa~zz) : rr
찾았습니다.

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이 글에서는 이진 탐색 트리를 배열로 표현하는 C 언어 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다.

이진 탐색 트리를 배열로 표현하는 Java 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 Java를 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

코드: BinarySearchTreeArray.java

Node 클래스 정의

class Node {
    int prevNode;      // 왼쪽 부분 트리를 가리키는 포인터
    String name;       // 이름 저장
    int nextNode;      // 오른쪽 부분 트리를 가리키는 포인터

    public Node(int prevNode, String name, int nextNode) {
        this.prevNode = prevNode;
        this.name = name;
        this.nextNode = nextNode;
    }
}

Node 클래스는 이진 탐색 트리의 노드를 나타내며, 왼쪽 자식 노드를 가리키는 prevNode, 이름을 저장하는 name, 그리고 오른쪽 자식 노드를 가리키는 nextNode를 가지고 있습니다.

이진 탐색 트리 초기화

Node[] tree = new Node[] {
    new Node(1, "mm", 2),
    new Node(3, "cc", 4),
    new Node(5, "rr", -1),
    new Node(-1, "aa", -1),
    new Node(6, "ee", 7),
    new Node(-1, "nn", -1),
    new Node(-1, "dd", -1),
    new Node(-1, "ll", -1)
};

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다. 노드가 존재하지 않을 경우 -1을 사용합니다.

특정 값 찾기

import java.util.Scanner;

public class BinarySearchTreeArray {
    public static void main(String[] args) {
        Node[] tree = new Node[] {
            new Node(1, "mm", 2),
            new Node(3, "cc", 4),
            new Node(5, "rr", -1),
            new Node(-1, "aa", -1),
            new Node(6, "ee", 7),
            new Node(-1, "nn", -1),
            new Node(-1, "dd", -1),
            new Node(-1, "ll", -1)
        };

        Scanner scanner = new Scanner(System.in);
        System.out.print("찾을 내용(aa~zz) : ");
        String key = scanner.next();
        int current = 0;

        while (current != -1) {
            if (key.equals(tree[current].name)) {
                System.out.println("찾았습니다.");
                break;
            } else if (key.compareTo(tree[current].name) < 0) {
                current = tree[current].prevNode; // 왼쪽 부분 트리로 이동
            } else {
                current = tree[current].nextNode; // 오른쪽 부분 트리로 이동
            }
        }
        scanner.close();
    }
}

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이 글에서는 이진 탐색 트리를 배열로 표현하는 Java 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다. 또한, Java에서는 자바 컬렉션 프레임워크의 TreeSet이나 TreeMap과 같은 구현체를 사용하여 이진 탐색 트리를 사용할 수 있습니다. 이들은 내부적으로 이진 탐색 트리를 사용하여 데이터를 정렬하고 관리하며, 사용자 친화적인 인터페이스를 제공합니다.

이진 탐색 트리를 배열로 표현하는 Python 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 Python을 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

코드: binary_search_tree_array.py

Node 클래스 정의

class Node:
    def __init__(self, prev_node, name, next_node):
        self.prev_node = prev_node  # 왼쪽 부분 트리를 가리키는 포인터
        self.name = name  # 이름 저장
        self.next_node = next_node  # 오른쪽 부분 트리를 가리키는 포인터

Node 클래스는 이진 탐색 트리의 노드를 나타내며, 왼쪽 자식 노드를 가리키는 prev_node, 이름을 저장하는 name, 그리고 오른쪽 자식 노드를 가리키는 next_node를 가지고 있습니다.

이진 탐색 트리 초기화

NIL = -1
MAX_SIZE = 10

tree = [
    Node(1, "mm", 2),  # 0
    Node(3, "cc", 4),  # 1
    Node(5, "rr", NIL),  # 2
    Node(NIL, "aa", NIL),  # 3
    Node(6, "ee", 7),  # 4
    Node(NIL, "nn", NIL),  # 5
    Node(NIL, "dd", NIL),  # 6
    Node(NIL, "ll", NIL),  # 7
]

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다.

특정 값 찾기

key = input("찾을 내용(aa~zz) : ")
current = 0

while current != NIL:
    if key == tree[current].name:
        print("찾았습니다.")
        break
    elif key < tree[current].name:
        current = tree[current].prev_node  # 왼쪽 부분 트리로 이동
    else:
        current = tree[current].next_node  # 오른쪽 부분 트리로 이동

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이 글에서는 이진 탐색 트리를 배열로 표현하는 Python 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다.

이진 탐색 트리를 배열로 표현하는 JavaScript 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 JavaScript를 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

코드: binary_search_tree_array.js

Node 클래스 정의

class Node {
    constructor(prev_node, name, next_node) {
        this.prev_node = prev_node;    // 왼쪽 부분 트리를 가리키는 포인터
        this.name = name;              // 이름 저장
        this.next_node = next_node;    // 오른쪽 부분 트리를 가리키는 포인터
    }
}

이진 탐색 트리 초기화

const NIL = -1;   // 아무것도 가리키지 않는 포인터
const MAX_SIZE = 10;

const tree = [
    new Node(1, "mm", 2),       // 0
    new Node(3, "cc", 4),       // 1
    new Node(5, "rr", NIL),     // 2
    new Node(NIL, "aa", NIL),   // 3
    new Node(6, "ee", 7),       // 4
    new Node(NIL, "nn", NIL),   // 5
    new Node(NIL, "dd", NIL),   // 6
    new Node(NIL, "ll", NIL)    // 7
];

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다.

특정 값 찾기

const searchTree = (key) => {
    let current = 0;
    while (current !== NIL) {
        if (key === tree[current].name) {
            console.log("찾았습니다.");
            break;
        } else if (key < tree[current].name) {
            current = tree[current].prev_node; // 왼쪽 부분 트리로 이동
        } else {
            current = tree[current].next_node; // 오른쪽 부분 트리로 이동
        }
    }
};

const key = prompt("찾을 내용(aa~zz) : ");
searchTree(key);

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이 글에서는 이진 탐색 트리를 배열로 표현하는 JavaScript 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다.

이진 탐색 트리를 배열로 표현하는 C++ 언어 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 C++을 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

코드: binary_search_tree_array.cpp

Node 구조체 정의

#include <iostream>
#include <string>
using namespace std;

const int NIL = -1;  // 아무것도 가리키지 않는 포인터
const int MAX_SIZE = 10;

struct Node {
    int prev_node;  // 왼쪽 부분 트리를 가리키는 포인터
    string name;    // 이름 저장
    int next_node;  // 오른쪽 부분 트리를 가리키는 포인터
};

Node 구조체는 이진 탐색 트리의 노드를 나타내며, 왼쪽 자식 노드를 가리키는 prev_node, 이름을 저장하는 name, 그리고 오른쪽 자식 노드를 가리키는 next_node를 가지고 있습니다.

이진 탐색 트리 초기화

Node tree[MAX_SIZE] = {
    {1, "mm", 2},  // 0
    {3, "cc", 4},  // 1
    {5, "rr", NIL},  // 2
    {NIL, "aa", NIL},  // 3
    {6, "ee", 7},  // 4
    {NIL, "nn", NIL},  // 5
    {NIL, "dd", NIL},  // 6
    {NIL, "ll", NIL}  // 7
};

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다.

특정 값 찾기

string key;
int current;

cout << "찾을 내용(aa~zz): ";
cin >> key;
current = 0;

while (current != NIL) {
    if (key == tree[current].name) {
        cout << "찾았습니다." << endl;
        break;
    } else if (key < tree[current].name) {
        current = tree[current].prev_node;  // 왼쪽 부분 트리로 이동
    } else {
        current = tree[current].next_node;  // 오른쪽 부분 트리로 이동
    }
}

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이 글에서는 이진 탐색 트리를 배열로 표현하는 C++ 언어 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다.

이진 탐색 트리를 배열로 표현하는 Go 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 Go를 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

코드: binary_search_tree_array.go

Node 구조체 정의

package main

import (
	"fmt"
	"strings"
)

const (
	NIL = -1
)

type Node struct {
	prev_node int    // 왼쪽 부분 트리를 가리키는 포인터
	name      string // 이름 저장
	next_node int    // 오른쪽 부분 트리를 가리키는 포인터
}

이진 탐색 트리 초기화

func main() {
	const MAX_SIZE = 10

	tree := [MAX_SIZE]Node{
		{1, "mm", 2},
		{3, "cc", 4},
		{5, "rr", NIL},
		{NIL, "aa", NIL},
		{6, "ee", 7},
		{NIL, "nn", NIL},
		{NIL, "dd", NIL},
		{NIL, "ll", NIL},
	}
	//...
}

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다.

특정 값 찾기

func main() {
	// 이진 탐색 트리 초기화 (앞서 작성한 코드와 연결되어 있습니다.)

	//...

	var key string
	var current int

	fmt.Print("찾을 내용(aa~zz) : ")
	fmt.Scan(&key)

	current = 0
	for current != NIL {
		if key == tree[current].name {
			fmt.Println("찾았습니다.")
			break
		} else if key < tree[current].name {
			current = tree[current].prev_node // 왼쪽 부분 트리로 이동
		} else {
			current = tree[current].next_node // 오른쪽 부분 트리로 이동
		}
	}
}

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이 글에서는 이진 탐색 트리를 배열로 표현하는 Go 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다.

이진 탐색 트리를 배열로 표현하는 Rust 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 Rust를 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

코드: binary_search_tree_array.rs

Node 구조체 정의

const NIL: i32 = -1;
const MAX_SIZE: usize = 10;

struct Node {
    prev_node: i32,      // 왼쪽 부분 트리를 가리키는 포인터
    name: String,    // 이름 저장
    next_node: i32,      // 오른쪽 부분 트리를 가리키는 포인터
}

이진 탐색 트리 초기화

fn main() {
    let tree: [Node; MAX_SIZE] = [
        Node { prev_node: 1, name: String::from("mm"), next_node: 2 },
        Node { prev_node: 3, name: String::from("cc"), next_node: 4 },
        Node { prev_node: 5, name: String::from("rr"), next_node: NIL },
        Node { prev_node: NIL, name: String::from("aa"), next_node: NIL },
        Node { prev_node: 6, name: String::from("ee"), next_node: 7 },
        Node { prev_node: NIL, name: String::from("nn"), next_node: NIL },
        Node { prev_node: NIL, name: String::from("dd"), next_node: NIL },
        Node { prev_node: NIL, name: String::from("ll"), next_node: NIL },
    ];
    //...
}

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다.

특정 값 찾기

use std::io::{self, Write};

fn main() {
    // 이진 탐색 트리 초기화 부분 (이전 페이지 참고)
    //...

    print!("찾을 내용(aa~zz) : ");
    io::stdout().flush().unwrap();

    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let key = input.trim();

    let mut current = 0;
    while current != NIL as usize {
        if key == tree[current].name {
            println!("찾았습니다.");
            break;
        } else if key < tree[current].name {
            current = tree[current].prev_node as usize; // 왼쪽 부분 트리로 이동
        } else {
            current = tree[current].next_node as usize; // 오른쪽 부분 트리로 이동
        }
    }
}

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이 글에서는 이진 탐색 트리를 배열로 표현하는 Rust 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다.

이진 탐색 트리를 배열로 표현하는 TypeScript 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 TypeScript를 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

코드: binary_search_tree_array.ts

Node 인터페이스 정의

interface Node {
    prev_node: number;    // 왼쪽 부분 트리를 가리키는 포인터
    name: string;         // 이름 저장
    next_node: number;    // 오른쪽 부분 트리를 가리키는 포인터
}

Node 인터페이스는 이진 탐색 트리의 노드를 나타내며, 왼쪽 자식 노드를 가리키는 prev_node, 이름을 저장하는 name, 그리고 오른쪽 자식 노드를 가리키는 next_node를 가지고 있습니다.

이진 탐색 트리 초기화

const MAX_SIZE = 8;
const NIL = -1;

const tree: Node[] = [
    { prev_node: 1, name: "mm", next_node: 2 },       // 0
    { prev_node: 3, name: "cc", next_node: 4 },       // 1
    { prev_node: 5, name: "rr", next_node: NIL },     // 2
    { prev_node: NIL, name: "aa", next_node: NIL },   // 3
    { prev_node: 6, name: "ee", next_node: 7 },       // 4
    { prev_node: NIL, name: "nn", next_node: NIL },   // 5
    { prev_node: NIL, name: "dd", next_node: NIL },   // 6
    { prev_node: NIL, name: "ll", next_node: NIL }    // 7
];

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다.

특정 값 찾기

const findValue = (key: string, tree: Node[]): boolean => {
    let current = 0;
    while (current !== NIL) {
        if (key === tree[current].name) {
            return true;
        } else if (key < tree[current].name) {
            current = tree[current].prev_node; // 왼쪽 부분 트리로 이동
        } else {
            current = tree[current].next_node; // 오른쪽 부분 트리로 이동
        }
    }
    return false;
}

const key = "aa";
const found = findValue(key, tree);
if (found) {
    console.log("찾았습니다.");
} else {
    console.log("찾을 수 없습니다.");
}

findValue 함수는 사용자로부터 찾고자 하는 값을 입력받아 이진 탐색 트리를 순회하며 값을 찾습니다. 찾고자 하는 값이 현재 노드의 값보다 작으면 왼쪽 자식 노드로 이동하고, 크면 오른쪽 자식 노드로 이동합니다. 이 과정을 반복하여 찾고자 하는 값을 발견하면 true를 반환합니다. 만약 찾고자 하는 값이 트리에 존재하지 않으면 false를 반환합니다.

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이 글에서는 이진 탐색 트리를 배열로 표현하는 TypeScript 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다.

이진 탐색 트리를 배열로 표현하는 Kotlin 예제

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 정렬된 상태를 유지하면서 빠른 탐색 속도를 제공하는 효율적인 데이터 구조입니다. 이 글에서는 Kotlin을 사용하여 이진 탐색 트리를 배열로 표현하고, 특정 값을 찾는 프로그램을 작성하는 예제를 살펴봅니다.

Node 클래스 정의

data class Node(
    val prev_node: Int,
    val name: String,
    val next_node: Int
)

이진 탐색 트리 초기화

const val MAX_SIZE = 8
const val NIL = -1

val tree = arrayOf(
    Node(1, "mm", 2), //0
    Node(3, "cc", 4), //1
    Node(5, "rr", NIL), //2
    Node(NIL, "aa", NIL), //3
    Node(6, "ee", 7), //4
    Node(NIL, "nn", NIL), //5
    Node(NIL, "dd", NIL), //6
    Node(NIL, "ll", NIL) //7
)

이진 탐색 트리를 배열로 표현하며, 각 노드의 인덱스는 왼쪽과 오른쪽 자식 노드를 가리키는 포인터로 사용됩니다.

특정 값 찾기

fun main() {
    print("찾을 내용(aa~zz) : ")
    val key = readLine()
    var current = 0

    while (current != NIL) {
        when {
            key == tree[current].name -> {
                println("찾았습니다.")
                break
            }
            key < tree[current].name -> {
                current = tree[current].prev_node //왼쪽 부분 트리로 이동
            }
            else -> {
                current = tree[current].next_node //오른쪽 부분 트리로 이동
            }
        }
    }
}

이 예제에서는 다음과 같은 이진 탐색 트리를 배열로 표현하였습니다.

        mm
       /  \
     cc    rr
    /  \      \
  aa    ee     nn
      /   \
    dd    ll

이 글에서는 이진 탐색 트리를 배열로 표현하는 Kotlin 예제를 살펴보았습니다. 이 방법을 사용하면 트리에 저장된 데이터를 빠르게 검색할 수 있으며, 구현이 상대적으로 간단하다는 장점이 있습니다. 그러나 배열을 사용하여 이진 탐색 트리를 구현할 때는 배열의 크기를 미리 정해야 한다는 단점도 있습니다. 이를 해결하기 위해 동적으로 메모리를 할당하는 방식을 사용할 수도 있습니다.

마무리

이진 탐색 트리를 배열로 표현하는 예제를 여러 프로그래밍 언어로 살펴보았습니다. 배열을 사용하면 이진 탐색 트리의 노드를 쉽게 관리할 수 있으며, 정렬된 상태를 유지하는 이진 탐색 트리의 특성을 활용하여 빠른 검색이 가능합니다. 각 언어마다 조금씩 다른 구현 방법이 있지만, 이 예제를 통해 이진 탐색 트리의 개념과 구현 방법을 이해할 수 있을 것입니다.

더 깊이 공부하고 싶다면

DevLec에서는 실무 중심의 C#, .NET, ASP.NET Core, Blazor, 데이터 액세스 강좌를 단계별로 제공합니다. 현재 수강 가능한 강좌 외에도 더 많은 과정이 준비되어 있습니다.
DevLec.com에서 자세한 커리큘럼을 확인해 보세요.

DevLec 공식 강의

C# Programming

C# 프로그래밍 입문

프로그래밍을 처음 시작하는 입문자를 위한 C# 기본기 완성 과정입니다.

ASP.NET Core 10.0

ASP.NET Core 10.0 시작하기 MVC Fundamentals Part 1 MVC Fundamentals Part 2

웹 애플리케이션의 구조와 MVC 패턴을 ASP.NET Core로 실습하며 익힐 수 있습니다.

Blazor Server

풀스택 웹개발자 과정 Part 1 풀스택 웹개발자 과정 Part 2 풀스택 웹개발자 과정 Part 3

실무에서 바로 활용 가능한 Blazor Server 기반 관리자·포털 프로젝트를 만들어 봅니다.

Data & APIs

Entity Framework Core 시작하기 ADO.NET Fundamentals Blazor Server Fundamentals Minimal APIs

데이터 액세스와 Web API를 함께 이해하면 실무 .NET 백엔드 개발에 큰 도움이 됩니다.

추천 자료: ASP.NET Core 인증 및 권한 부여

추천 자료: .NET Blazor에 대해 알아보시겠어요? .NET Blazor 알아보기를 확인해보세요!