algorithm 알고리즘 Data Structure 자료구조 AVL Tree AVL 트리

[Algorithm] Data Structure - AVL Tree

자료구조 AVL 트리

Posted by lim.Chuck on September 14, 2024

Trie?

트라이는 문자열의 집합을 저장하는 데 사용되는 특수한 자료구조입니다. 특히 공통된 접두사를 공유하는 문자열을 검색하는 데 매우 효율적입니다.

구조

트라이는 노드로 구성되며, 각 노드는 문자를 나타냅니다.

  • 각 노드는 하나의 문자를 나타내며, 트리의 경로는 문자열 또는 문자열의 접두사를 나타냅니다.
  • 루트 노드는 일반적으로 빈 노드이고, 그 다음 각 노드는 문자열의 다음 문자를 나타냅니다.
  • 경로가 유효한 단어를 형성하는지를 나타내기 위해 특별한 “단어의 끝” 표시를 사용할 수 있습니다.

주요 연산

  • 삽입: 트라이에 단어를 추가합니다.
  • 검색: 트라이에 단어가 존재하는지 확인합니다.
  • 접두사 검색: 주어진 접두사로 시작하는 모든 단어를 찾습니다.

검색과 삽입의 시간 복잡도는 O(m)이며, 여기서 m은 삽입하거나 검색하려는 단어의 길이입니다. 이는 접두사 기반 쿼리를 처리할 때 매우 효율적이며, 특히 사전, 자동완성 시스템 또는 IP 라우팅과 같은 대규모 데이터 세트에서 유용합니다.

사용 사례

  • 자동완성: 트라이는 접두사로 시작하는 모든 단어를 빠르게 찾을 수 있어 자동완성 기능을 구현하는 데 유용합니다.
  • 맞춤법 검사: 입력된 접두사를 기준으로 단어를 제안하는 데 사용할 수 있습니다.
  • IP 라우팅: 라우팅 테이블에서 접두사와 네트워크 주소를 일치시키는 데 도움이 됩니다.
  • DNA 서열 분석: DNA 염기 서열을 저장하고 검색하는 데 사용할 수 있습니다.

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

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // 단어를 트라이에 삽입
  insert(word) {
    let currentNode = this.root;
    for (let char of word) {
      if (!currentNode.children[char]) {
        currentNode.children[char] = new TrieNode();
      }
      currentNode = currentNode.children[char];
    }
    currentNode.isEndOfWord = true;
  }

  // 트라이에서 단어 검색
  search(word) {
    let currentNode = this.root;
    for (let char of word) {
      if (!currentNode.children[char]) {
        return false;
      }
      currentNode = currentNode.children[char];
    }
    return currentNode.isEndOfWord;
  }

  // 주어진 접두사로 시작하는 단어가 있는지 확인
  startsWith(prefix) {
    let currentNode = this.root;
    for (let char of prefix) {
      if (!currentNode.children[char]) {
        return false;
      }
      currentNode = currentNode.children[char];
    }
    return true;
  }
}

// 사용 예시:
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // true
console.log(trie.search("app")); // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app")); // true

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

use std::collections::HashMap;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end_of_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_end_of_word: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode::new(),
        }
    }

    // 단어를 트라이에 삽입
    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for c in word.chars() {
            node = node.children.entry(c).or_insert(TrieNode::new());
        }
        node.is_end_of_word = true;
    }

    // 트라이에서 단어 검색
    fn search(&self, word: &str) -> bool {
        let mut node = &self.root;
        for c in word.chars() {
            match node.children.get(&c) {
                Some(n) => node = n,
                None => return false,
            }
        }
        node.is_end_of_word
    }

    // 주어진 접두사로 시작하는 단어가 있는지 확인
    fn starts_with(&self, prefix: &str) -> bool {
        let mut node = &self.root;
        for c in prefix.chars() {
            match node.children.get(&c) {
                Some(n) => node = n,
                None => return false,
            }
        }
        true
    }
}

// 사용 예시:
fn main() {
    let mut trie = Trie::new();
    trie.insert("apple");
    println!("{}", trie.search("apple")); // true
    println!("{}", trie.search("app"));   // false
    println!("{}", trie.starts_with("app")); // true
    trie.insert("app");
    println!("{}", trie.search("app"));   // true
}

요약

트라이는 문자열을 관리하고 접두사 기반 연산을 효율적으로 수행하는 강력한 자료구조입니다. JavaScript와 Rust 예제에서 삽입, 단어 검색, 접두사 매칭과 같은 기본 기능을 구현하는 방법을 보여줍니다.

Trie?

A Trie (also known as a Prefix Tree) is a specialized data structure used to store a collection of strings. It’s particularly efficient for searching strings that share common prefixes.

Structure

A Trie is composed of nodes where:

  • Each node represents a character.
  • Each path down the tree represents a string or a prefix of strings.
  • The root node is typically an empty node, and each subsequent node represents the next character of a string.
  • A special “end of word” marker may be used to denote that a path forms a valid word.

Key Operations

  • Insert: Add a word to the Trie.
  • Search: Check if a word exists in the Trie.
  • Prefix Search: Find all words in the Trie that start with a given prefix.

The time complexity of searching and inserting in a Trie is O(m), where m is the length of the word being inserted or searched. This makes it efficient for prefix-based queries, especially when dealing with large datasets such as dictionaries, autocomplete systems, or IP routing.

Use Cases

  • Autocomplete: A Trie can quickly find all words starting with a prefix, which is useful for implementing autocomplete features.
  • Spell Checking: Can be used to suggest words based on an input’s prefix.
  • IP Routing: Helps in matching network addresses with prefixes in routing tables.
  • DNA Sequencing: Used to store and search for sequences of DNA bases.

JavaScript Example

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

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // Insert a word into the Trie
  insert(word) {
    let currentNode = this.root;
    for (let char of word) {
      if (!currentNode.children[char]) {
        currentNode.children[char] = new TrieNode();
      }
      currentNode = currentNode.children[char];
    }
    currentNode.isEndOfWord = true;
  }

  // Search for a word in the Trie
  search(word) {
    let currentNode = this.root;
    for (let char of word) {
      if (!currentNode.children[char]) {
        return false;
      }
      currentNode = currentNode.children[char];
    }
    return currentNode.isEndOfWord;
  }

  // Search for words that start with a prefix
  startsWith(prefix) {
    let currentNode = this.root;
    for (let char of prefix) {
      if (!currentNode.children[char]) {
        return false;
      }
      currentNode = currentNode.children[char];
    }
    return true;
  }
}

// Example usage:
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple")); // true
console.log(trie.search("app")); // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app")); // true

Rust Example

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

use std::collections::HashMap;

#[derive(Default)]
struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_end_of_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_end_of_word: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode::new(),
        }
    }

    // Insert a word into the Trie
    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for c in word.chars() {
            node = node.children.entry(c).or_insert(TrieNode::new());
        }
        node.is_end_of_word = true;
    }

    // Search for a word in the Trie
    fn search(&self, word: &str) -> bool {
        let mut node = &self.root;
        for c in word.chars() {
            match node.children.get(&c) {
                Some(n) => node = n,
                None => return false,
            }
        }
        node.is_end_of_word
    }

    // Search for words that start with a prefix
    fn starts_with(&self, prefix: &str) -> bool {
        let mut node = &self.root;
        for c in prefix.chars() {
            match node.children.get(&c) {
                Some(n) => node = n,
                None => return false,
            }
        }
        true
    }
}

// Example usage:
fn main() {
    let mut trie = Trie::new();
    trie.insert("apple");
    println!("{}", trie.search("apple")); // true
    println!("{}", trie.search("app"));   // false
    println!("{}", trie.starts_with("app")); // true
    trie.insert("app");
    println!("{}", trie.search("app"));   // true
}

Summary

Tries are a powerful data structure for managing strings and performing efficient prefix-based operations. The examples provided in both JavaScript and Rust show basic functionality such as insertion, searching for a word, and prefix matching.

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