GO · 컬렉션
이진 검색 트리 구현
제네릭으로 이진 검색 트리(BST)를 구현합니다. 정렬된 데이터의 삽입/검색에 사용됩니다.
컬렉션고급bsttreegenericsdata-structure
핵심 설명
제네릭으로 이진 검색 트리(BST)를 구현합니다. 정렬된 데이터의 삽입/검색에 사용됩니다.
Go code
package main
import (
"cmp"
"fmt"
)
type Node[T cmp.Ordered] struct {
Value T
Left *Node[T]
Right *Node[T]
}
type BST[T cmp.Ordered] struct {
Root *Node[T]
}
func (t *BST[T]) Insert(val T) {
t.Root = insert(t.Root, val)
}
func insert[T cmp.Ordered](n *Node[T], val T) *Node[T] {
if n == nil { return &Node[T]{Value: val} }
if val < n.Value {
n.Left = insert(n.Left, val)
} else if val > n.Value {
n.Right = insert(n.Right, val)
}
return n
}
func (t *BST[T]) InOrder() []T {
var result []T
inOrder(t.Root, &result)
return result
}
func inOrder[T cmp.Ordered](n *Node[T], result *[]T) {
if n == nil { return }
inOrder(n.Left, result)
*result = append(*result, n.Value)
inOrder(n.Right, result)
}
func main() {
tree := &BST[int]{}
for _, v := range []int{5, 3, 7, 1, 4, 6, 8} {
tree.Insert(v)
}
fmt.Println(tree.InOrder()) // [1 3 4 5 6 7 8]
}학습 팁
cmp.Ordered 제약을 사용하면 , > 연산자를 제네릭 함수에서 사용할 수 있습니다.
주의할 점
균형 잡히지 않은 BST는 최악의 경우 O(n) 검색 시간이 됩니다. 실무에서는 btree 라이브러리나 표준 맵을 사용하세요.
자주 묻는 질문
이진 검색 트리 구현란 무엇인가요?
제네릭으로 이진 검색 트리(BST)를 구현합니다. 정렬된 데이터의 삽입/검색에 사용됩니다.
이진 검색 트리 구현 학습 시 주의할 점은 무엇인가요?
균형 잡히지 않은 BST는 최악의 경우 O(n) 검색 시간이 됩니다. 실무에서는 btree 라이브러리나 표준 맵을 사용하세요.