나는 여기에서 아주 간단한 질문을 가지고있다 : 붉은 검은 색 나무가 정렬 된 순서로 있어야만 하는가? 나는 wikipedia 페이지 (http://en.wikipedia.org/wiki/Red-black_tree)의 오른쪽에있는 작은 상자가 검색 시간이 O (log (n))라고 말하기 때문에 이것을 묻습니다. 그러나 나무가 분류되어 있다면 이것은 사실 일 수 없습니다. 반면에 속성 s는빨강 - 검정 나무가 정렬 된 순서 여야합니까?
빨강 검정 나무는 정렬 된 나무입니다 (전체 RB 나무는 모두 이진 나무로 정렬되지만 모든 정렬 된 이진 나무는 빨간색 검정 나무입니다). 일반 이진 트리와 빨간색 검정 트리의 차이는 RB 나무가 균형을 이루기 때문에 검색 시간이 로그 (n) 인 RB 트리를 보장한다는 것입니다. 본질적으로, n 노드에 대한 레이어 수가 로그 (n)이되도록 보장하여 이진 검색을 점검합니다.
없는 균형있는 일반 이진 트리 항상 로그 (N) 시간 복잡성을 생산하지 않습니다. 나는이 같은 트리가있는 경우 예를 들어,이 불균형 트리
4
/\
3 6
\
7
\
10
\
12
을 실제 검색 시간은 12 (최악의 경우 시간 복잡도, 5 개 비교를) 찾을 거의 선형이다. 이 균형 잡힌 트리를 들어 최대 로그 (N) 층 위의 나무가 될 수있다 :
7
/ \
4 10
/\ \
3 6 12
그리고 최대 3 개 비교를 취할 것입니다 가장 낮은 계층 노드 중 하나를 찾는 (이 적합한 2 [ 2 (6)에 로그온 = 3)의 층수는 기능적으로 동등한
여기서 중요한 기억하는(N)가 실제로 올림 이후, CEIL 로그이다것을 루트에서 시작할 때 만들어야하는 비교의 수입니다. 빨강 - 검정 나무는 바닐라, 언밸런스 바이너리 트리가 밸런싱을 통해 레이어의 수를 최소한으로 제한합니다.
빨강 - 검정 나무는 O (log n)의 자연스러운 순서로 노드를 설정하는 방법 때문에 검색 시간이 있습니다.
노드 비교를 수행하면 이론적으로 분기를 수행 할 때 옵션의 절반을 무시합니다.
당신은 하나 개의 요소에 도착하기 전에 당신은 단지 "절반"log n times이 다음 검색의 복잡성이 O(log n)
레드 - 블랙 트리 이진 검색 트리입니다 수 있기 때문이다. 이진 검색 트리의 정의에 따라 왼쪽 자식 (및 모든 하위 항목)은 부모보다 작아야하며 오른쪽 자식 (모든 하위 항목)은 부모보다 커야합니다. 따라서 주문이 있습니다.
빨강 - 검정 나무의 전체 점은 나무를 어느 정도 균형있게 유지하는 것입니다. 정렬 제약 조건을 완화하면 원하는 곳마다 노드를 배치 할 수 있으므로 트리를 균형있게 유지하는 것이 쉽습니다.
정렬 된 주문이란 무엇입니까? 모든 이진 검색 나무는 주문 – gtgaxiola