반응형 알고리즘1 레드-블랙 트리 이진검색트리는 저장과 검색에 평균 Θ( ))시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 Θ(n)에 근접한 시간이 소요될 수도 있다. 그래서 고안해 낸 것이 균형잡힌 이진검색트리이다. 균형잡힌 이진검색트리는 최악의 경우에도 이진트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진검색트리로 대표적인 것은 레드블랙트리와 AVL트리다. 자바의 TreeSet과 TreeMap은 레드-블랙 트리를 베이스로 한 구현을 사용한다. 레드-블랙 트리의 조건 모든 트리의 노드에 검은색 혹은 빨간색을 색칠한다. 루트 노드는 항상 검은색이다. 모든 리프 노드 들은 검은색이다. 빨간색 노드의 자식은 양쪽 다 항상 검은색이다. 4.1. 즉, 빨간색 노드는 연달아 나타날 수 없다. 4.2. .. 2021. 6. 28. 이전 1 다음 728x90 반응형