Red black tree1 [자료구조] Red-Black 트리 [ 이진 탐색 트리(BST, Binary Search Tree)의 단점 ] 균등 트리 : 노드 개수가 N개일 때 O(logN) 편향 트리 : 노드 개수가 N개일 때 O(N) 이진 탐색 트리는 최악의 경우 한쪽으로 편향된 트리일 때 O(N) 시간이 걸린다. 이 말은 모든 노드를 한 번씩 다 확인해줘야 한다는 의미이다. 이러한 단점을 개선한 균형 트리인 Red-Black 트리에 대해서 알아보자. 🔴 Red-Black 트리 ⚫️ 이진 탐색 트리의 단점을 개선하기 위한 자료구조 이진 탐색 트리(BST)의 한 종류 스스로 균형(balancing) 잡는 트리 BST의 worst case의 단점을 개선해서 모든 경우에 O(logN) 모든 노드는 red 혹은 black ✔️ 5가지 속성 모든 노드는 red 혹은 bla.. 2023. 3. 2. 이전 1 다음 반응형
