algorithm 알고리즘 Data Structure 자료구조 Binary search tree 이진 탐색 트리

[Algorithm] Data Structure - Binary search tree

자료구조 이진 탐색 트리

Posted by lim.Chuck on September 14, 2024

이진 탐색 트리(BST) 개요

이진 탐색 트리(BST)는 다음과 같은 속성을 따르는 이진 트리의 일종입니다:

  1. 왼쪽 서브트리: 노드의 왼쪽 서브트리는 노드의 키보다 작은 키를 가진 노드만 포함합니다.
  2. 오른쪽 서브트리: 노드의 오른쪽 서브트리는 노드의 키보다 큰 키를 가진 노드만 포함합니다.
  3. 중복 노드 없음: 모든 노드는 고유한 값을 가지며, 중복된 값이 없습니다.

BST는 효율적인 검색, 삽입, 삭제 연산을 제공합니다. 이러한 연산의 평균 시간 복잡도는 O(log n)이며, 최악의 경우(트리가 균형을 이루지 않을 때)에는 O(n)이 될 수 있습니다.

이진 탐색 트리의 사용 사례

BST는 정렬된 데이터를 저장해야 하거나 빠른 검색, 삽입, 삭제가 필요한 상황에서 널리 사용됩니다. 일반적인 사용 사례는 다음과 같습니다:

  • 데이터베이스: 빠른 데이터 검색을 위한 인덱스 구현.
  • 검색 알고리즘: 선형 구조에 비해 더 빠른 검색을 가능하게 함.
  • 심볼 테이블: 컴파일러나 인터프리터에서 사용.
  • 우선순위 큐: 힙 구조와 함께 사용될 수 있음.
  • 자동 완성 및 접두사 트리: 검색 엔진 및 단어 예측 기능에 활용.

JavaScript로 구현한 이진 탐색 트리 예제

JavaScript에서 구현한 이진 탐색 트리 예제는 다음과 같습니다:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // BST에 노드를 삽입하는 메소드
  insert(value) {
    const newNode = new Node(value);

    if (this.root === null) {
      this.root = newNode;
      return this;
    }

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else if (value > current.value) {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      } else {
        // 이미 값이 존재하는 경우
        return this;
      }
    }
  }

  // 주어진 값이 있는지 탐색하는 메소드
  search(value) {
    let current = this.root;

    while (current !== null) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        return current; // 값을 찾은 경우
      }
    }

    return null; // 값을 찾지 못한 경우
  }
}

// 사용 예시:
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(15);

console.log(bst.search(15)); // 값이 15인 노드
console.log(bst.search(100)); // null (값을 찾지 못함)

Rust로 구현한 이진 탐색 트리 예제

Rust에서 구현한 이진 탐색 트리 예제는 다음과 같습니다:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#[derive(Debug)]
struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(value: i32) -> Node {
        Node {
            value,
            left: None,
            right: None,
        }
    }
}

struct BinarySearchTree {
    root: Option<Box<Node>>,
}

impl BinarySearchTree {
    fn new() -> BinarySearchTree {
        BinarySearchTree { root: None }
    }

    fn insert(&mut self, value: i32) {
        self.root = Self::insert_recursive(self.root.take(), value);
    }

    fn insert_recursive(node: Option<Box<Node>>, value: i32) -> Option<Box<Node>> {
        match node {
            Some(mut n) => {
                if value < n.value {
                    n.left = Self::insert_recursive(n.left.take(), value);
                } else if value > n.value {
                    n.right = Self::insert_recursive(n.right.take(), value);
                }
                Some(n)
            }
            None => Some(Box::new(Node::new(value))),
        }
    }

    fn search(&self, value: i32) -> bool {
        Self::search_recursive(&self.root, value)
    }

    fn search_recursive(node: &Option<Box<Node>>, value: i32) -> bool {
        match node {
            Some(n) => {
                if value == n.value {
                    true
                } else if value < n.value {
                    Self::search_recursive(&n.left, value)
                } else {
                    Self::search_recursive(&n.right, value)
                }
            }
            None => false,
        }
    }
}

fn main() {
    let mut bst = BinarySearchTree::new();
    bst.insert(10);
    bst.insert(5);
    bst.insert(20);
    bst.insert(15);

    println!("15이 있는가? {}", bst.search(15)); // true
    println!("100이 있는가? {}", bst.search(100)); // false
}

결론

이진 탐색 트리(BST)는 정렬된 데이터를 효율적으로 관리할 수 있는 기본적인 자료구조입니다. 다양한 시스템에서 빠른 검색과 업데이트 시간이 중요한 경우 널리 사용되며, JavaScript와 Rust와 같은 언어에서도 쉽게 구현할 수 있습니다.

Binary Search Tree (BST) Overview

A Binary Search Tree (BST) is a type of binary tree where each node follows the following properties:

  1. Left Subtree: The left subtree of a node contains only nodes with keys less than the node’s key.
  2. Right Subtree: The right subtree of a node contains only nodes with keys greater than the node’s key.
  3. No Duplicate Nodes: There are no duplicate nodes, i.e., all nodes have unique values.

BST allows efficient searching, insertion, and deletion operations. The average time complexity of these operations is O(log n), but in the worst case (unbalanced tree), it could degrade to O(n).

Where Binary Search Tree is Used?

BSTs are widely used in scenarios where sorted data needs to be stored and where fast search, insertion, and deletion are required. Some common use cases include:

  • Databases: Implementing indexes for fast data retrieval.
  • Searching algorithms: Faster searching in comparison to linear structures.
  • Symbol Tables: In compilers or interpreters.
  • Priority Queues: When combined with heap-like structures.
  • Autocomplete and Prefix Trees: In search engines and word prediction.

Binary Search Tree Example in JavaScript

Here’s an implementation of a BST in JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // Insert a node into the BST
  insert(value) {
    const newNode = new Node(value);

    if (this.root === null) {
      this.root = newNode;
      return this;
    }

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else if (value > current.value) {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      } else {
        // Value already exists
        return this;
      }
    }
  }

  // Search for a node with a given value
  search(value) {
    let current = this.root;

    while (current !== null) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        return current; // Value found
      }
    }

    return null; // Value not found
  }
}

// Example usage:
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(15);

console.log(bst.search(15)); // Node with value 15
console.log(bst.search(100)); // null (value not found)

Binary Search Tree Example in Rust

Here’s a similar implementation in Rust:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#[derive(Debug)]
struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(value: i32) -> Node {
        Node {
            value,
            left: None,
            right: None,
        }
    }
}

struct BinarySearchTree {
    root: Option<Box<Node>>,
}

impl BinarySearchTree {
    fn new() -> BinarySearchTree {
        BinarySearchTree { root: None }
    }

    fn insert(&mut self, value: i32) {
        self.root = Self::insert_recursive(self.root.take(), value);
    }

    fn insert_recursive(node: Option<Box<Node>>, value: i32) -> Option<Box<Node>> {
        match node {
            Some(mut n) => {
                if value < n.value {
                    n.left = Self::insert_recursive(n.left.take(), value);
                } else if value > n.value {
                    n.right = Self::insert_recursive(n.right.take(), value);
                }
                Some(n)
            }
            None => Some(Box::new(Node::new(value))),
        }
    }

    fn search(&self, value: i32) -> bool {
        Self::search_recursive(&self.root, value)
    }

    fn search_recursive(node: &Option<Box<Node>>, value: i32) -> bool {
        match node {
            Some(n) => {
                if value == n.value {
                    true
                } else if value < n.value {
                    Self::search_recursive(&n.left, value)
                } else {
                    Self::search_recursive(&n.right, value)
                }
            }
            None => false,
        }
    }
}

fn main() {
    let mut bst = BinarySearchTree::new();
    bst.insert(10);
    bst.insert(5);
    bst.insert(20);
    bst.insert(15);

    println!("Is 15 present? {}", bst.search(15)); // true
    println!("Is 100 present? {}", bst.search(100)); // false
}

Conclusion

A Binary Search Tree is a fundamental data structure for efficiently managing sorted data. It’s used in various systems, from databases to compilers, and its main advantages lie in its quick lookup and update times. Both JavaScript and Rust offer powerful tools for implementing BSTs, demonstrating the versatility of the structure across different programming languages.

FEATURED TAGS
git 알고리즘 algorithm js 기초 js 기초 문법 js 문법 자료구조 Data Structure Graphs React 그래프 러스트 rust 집합 Sets front 수학 정렬 Math Sorting 간단예제 문자열 Strings github AWS 이벤트 버블링 이벤트 캡처링 탐색 LLM MCP Searches 컴파일러 트리 AI Cloud Front Cursor MCP 사용법 bubbling capturing s3 개발자도구 광고 구글 자동색인 깃허브 광고 라이브러리 러스트 설치 리엑트 버킷 비교 사이트맵 아마존 예제 웹 접근성 이미지 업로드 최장 공통 부분수열 캐시 텍스트 프레임워크 AI통합 API Adsense Claude Compiler SQL SWC Speedy Web Compiler Trees js 변수 js 생성자함수 npm nuxt pipeline project management robots rust 구축 rust setting rust setup text utterances
FRIENDS