목록red black tree (1)

블로그

[자료구조] 5. STL Map

1. Map 간단 요약 STL에 속한 Map은 key로 정렬되는 Red-Black Tree 구조이며, key마다 value를 가진다. 데이터의 삽입/삭제 및 탐색의 시간복잡도가 O(logn)으로 빠르다. 2. Map 구조 - Map은 Red-Black Tree로 구현되어있다. 이 때 노드의 크기 비교는 key값을 이용한다. - Red-Black Tree : 자가 균형 이진 탐색 트리 1) 조건 - 모든 노드는 빨간색 또는 검은색이다. - 루트 노드는 항상 검은색이다. - 모든 리프 노드(Null leaf, NIL : 값을 가지지 않는 트리의 끝에 있는 노드)는 검은색이다. - 빨간색 노드의 자식은 검은색이다. 빨간색 노드가 연속될 시 Double Red라고 부르고, 아래 소개하는 방법들로 해결한다. - ..
프로그래밍/자료구조와 알고리즘 2023. 7. 25. 23:36
이전 Prev 1 Next 다음