목록Tree/AVL (1)

SuperVingo

Self-balancinig BST 자가 균형 이진 탐색 트리

여기에서는 AVL과 Red-Black Tree에 대해서 설명한다. Self-balancing Binary Search Tree "자가 균형 이진 탐색 트리(Self-balancing Binary Search Tree)"라고 한다. 이 트리는 트리의 전체적인 균형을 맞추는데, 이러한 과정이 필요한 이유는 BST의 Worst Case를 보아야한다. 바로 편향 이진 트리 상황이다. 만약 N개의 노드가 있다면, 최대 트리의 높이는 logN이므로, 탐색 시간은 $$ O(log N) $$ 이 된다. 하지만, 편향 이진 트리의 경우에는 만약 N개의 노드가 있다면, 최대 트리의 높이가 N이 되어 탐색시간은 $$ O(N) $$ 이 된다. 이러한 문제를 해결하는 것은 이진 트리의 양쪽 높이를 일정하게 유지하는 것이다. 이..
Computer Science[CS]/Data Structure[자료구조] 2024. 1. 4. 21:20
이전 Prev 1 Next 다음