search

ajroot5685 / ajroot5685.github.io

MIT License
0 stars 0 forks source link

posts/Binary-Search-Tree/ #16

Open utterances-bot opened 5 months ago

utterances-bot commented 5 months ago

이진 탐색 트리 BST(Binary Search Tree) | 안정적인 블로그

🤔 BST 란? 이진 트리 기반의 탐색을 위한 자료구조이다. 노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야 하며 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가져야 한다.

https://ajroot5685.github.io/posts/Binary-Search-Tree/

mikio999 commented 5 months ago

BST의 worst case(시간 복잡도 O(n))에 대해 설명해주실 수 있나요?

ajroot5685 commented 5 months ago

BST의 worst case(시간 복잡도 O(n))에 대해 설명해주실 수 있나요?

@mikio999

BST는 한 노드에 대해 왼쪽에 있는 노드들은 무조건 자신보다 작고, 오른쪽에 있는 노드들은 무조건 자신보다 크다 라는 단순한 규칙이 있습니다.

이때 삽입 과정에서 100개의 데이터가 내림차순으로 들어온다면 높이가 100인 왼쪽으로 편향된 트리가 만들어지고, 가장 작은 값을 찾고자 할 때 100개의 노드를 다 거쳐야 합니다. 때문에 최악의 경우 O(n) 이 소요됩니다.

이러한 균형 문제를 해결한 것이 B Tree 입니다!