빨강 - 검정 나무 연결

Question

OCaml 표준 라이브러리는 매우 효율적인 divide-and-conquer 알고리즘을 사용하여 union 2 세트를 계산하는 멋진 Set 구현을 제공합니다. 나는 하나의 세트에서 전체 하위 트리 (단일 요소 만이 아닌)를 취하여 다른 세트에 삽입하고 필요시 재조정한다고 생각한다.

OCaml이 사용하는 AVL 트리에 보관되는 높이 정보가 필요한지, 아니면 이것이 빨강 - 검정 나무에서도 가능할 지 궁금합니다. 예를 들어 첫 번째 트리 끝에 요소를 추가하는 두 번째 트리를 반복하는 것보다 더 효율적으로 한 쌍의 빨강 - 검정 나무를 연결할 수 있습니까?

Answer 1

당신이 유니온 또는 연결 또는 둘 모두를 설정하는 데 관심이 있거나 OCaml이나 임시 구조에서도 일반적인 데이터 구조에만 관심이 있다면 확실하지 않습니다.

구현은 red-black trees with fingers is described by Heather D. Booth in a chapter from her thesis입니다. 손가락으로 크기 n의 빨강 - 검정 나무는 크기가 amorized O (lg (min (p, q))) 시간의 크기 p와 q의 두 나무로 나눌 수 있고 크기 p와 q의 두 개의 빨강 - 검정 나무는 동일한 경계에서 연결됨. 또한 요소는 상각 된 O (1) 시간에 rb 트리의 양쪽 끝에 추가되거나 삭제 될 수 있습니다. 이러한 작업을 통해 정보 이론적으로 최적 인 상각 된 O (p lg (q/p)) 시간 합집합 (p < q의 경우)을 달성 할 수 있습니다. 아마도 이러한 경계를 확보하기위한 핵심 아이디어는 왼쪽 및 오른쪽 등뼈에 대한 하위 포인터의 역전입니다.

위의 경계는 전통적인 의미로 상각됩니다. OCaml과 같은 함수형 언어의 경우, 데이터 구조가 지속적으로 사용될 때 적용되는 범위를 원할 수 있습니다. 나는 나무가 지속적으로 사용될 때 Booth의 묘사가 모든 범위를 달성 할 것이라고 생각하지 않습니다. 예를 들어 손가락에 삽입하면 ω (1) 번식을 할 수 있습니다. 이 문제는 lazy recolorings discussed in Driscoll et al.'s "Making Data Structures Persistent"을 통해 해결할 수 있습니다.

한편, Booth의 분석에 따르면 지속적으로 사용하더라도 연결은 여전히 ​​O (lg (max (p, q))라고 표시 될 수 있습니다. 나는 집합체 경계에 대해 덜 낙관적이다.

기능적 설정에서 점근 적으로 최적의 시간 범위로 작업을 설정할 수 있습니다. 그러한 described by Hinze & Paterson은 상각 된 (그러나 영구적 인) 의미로 경계를 이루며, treaps described by Blandford & Blelloch achieve the bounds in a randomized sense과 그 described by Kaplan & Tarjan은 최악의 경우이를 달성합니다. 후자는 또한 Hinze & Paterson이 그 주장을 모호하지만 O (lg lg (min (p, q))) 연결을 제공합니다. 이 나무들은 빨강 검정 나무에 대한 질문에 대한 직접적인 대답은 아니지만 가능한 한 맛을 내기를 희망하며 H & P 종이에는 코드가 포함되어 있고 has been verified correct using Coq은 OCaml 코드로 추출 할 수 있습니다.

관심이있을만한 포인터가 두 개 더 있습니다. Brodal et al. presented search trees with O(lg n) find, insert, and delete and O(1) concat even in a functional setting. 또한 Atallah et al. claim to describe a red-black tree that has amortized O(1) concat (presumably ephemerally only)이지만 Buchsbaum and Goodrich claim that there are several flaws in that structure.

는 은 레드 - 블랙 트리의 유틸리티에 대한

마지막으로 참고 :이 질문에 대한 답변 중 하나에 대한 의견 중 하나는, 당신은 말 :

이

레드 - 블랙 트리의 유일한 장점이다 보조 정보 (빨간색 또는 검은 색)는 분기마다 1 비트입니다. 높이를 추가함으로써, 당신은 그 이점을 잃어 버렸고, 단지 높이가 균형 잡힌 나무를 사용했을 것입니다.

다른 장점이 있습니다. 예를 들어, 계산 구조에 사용되는 일부 데이터 구조는 이진 검색 트리를 기반으로하지만 트리 로테이션 비용이 높습니다. Red-black trees can be rebalanced in at most 3 rotations per insert and delete 인 반면, AVL trees can take Ω(lg n) rotations for these operations. As Ralf Hinze noticed, Okasaki's rebalancing scheme for red-black trees (코드는 ML, Haskell, Java, and Ada)은 동일한 경계를 제공하지 않으므로 삽입시 Ω (lg n) 회전을 끝낼 수 있습니다. (Okasaki는 삭제되지 않습니다.)

또한 노드 당 하나의 비트 균형 정보 만 사용하도록 높이 균형을 맞춘 검색 트리 (심지어 AVL 트리)를 저장할 수 있습니다. 일부 나무는 일방 높이 균형 나무와 같이 각 노드에서 두 가지 가능한 균형 위치를 갖지만 노드 당 최대 네 가지 가능한 균형 위치가있는 나무는 각 자식에 한 비트의 균형 정보를 저장할 수 있습니다.

편집 : 질문의 끝에서 특정 질의에 대한 답변에서

, 여기에 두 개의 레드 - 블랙 트리을 연결하는 알고리즘에 대한 설명입니다. 그것은 O (lg (max (| L |, | R |))) 시간을 필요로하는데, 이것은 위에 설명 된 점근 적으로 최적의 통합 시간을 얻기에는 너무 깁니다. 비교를 위해, the "join" implementation for AVL sets in OCaml's stdlib은 O (h1-h2) 성능을 얻습니다. h1은 키가 큰 트리의 높이입니다.하지만 실제로는 두 개의 AVL 트리를 결합합니다. 아래 알고리즘은 찾아서 제거해야합니다. 그 모르타르 성분을 그 주장 중 하나에서. B + 트리처럼 리프에 요소를 저장하는 것만으로 피할 수는 있지만 검색을 안내하기 위해 비 잎 노드의 요소에 대한 포인터를 유지해야하는 공간상의 불이익이 있습니다. 어쨌든 OCaml stdlib의 AVL join 코드와 같은 높이의 나무에 대한 결합 상수 시간을 만들지는 못합니다. 왜냐하면 아래에 설명 된 것처럼 각 트리의 검정 높이를 계산해야하기 때문입니다.

두 개의 비어 있지 않은 빨강 - 검정 나무 L과 R이 주어지면 L과 R의 연결 인 새로운 빨강 - 검정 나무가 생성됩니다. 이렇게하면 O (lg (max (| L |, | R |))), 여기서 | L | L의 노드 수를 나타냅니다.

먼저 L, c에서 가장 큰 요소를 제거합니다. 다음으로, 검정색 높이의 L과 R을 찾으십시오. "검은 색 높이"란, 루트에서 잎까지의 모든 경로에있는 검정색 노드의 수를 의미합니다. 붉은 검정색 불변량에 의해, 이것은 주어진 나무의 모든 경로에서 일정합니다. L의 검은 높이 p와 R의 검은 높이 q를 호출하고 w.l.o.g를 가정합니다. q ≤ q.

R의 루트로부터 높이 p 인 검정 노드 R '에 도달 할 때까지 왼쪽 자식을 따릅니다. 루트 요소 c, 왼쪽 자식 L 및 오른쪽 자식 R '을 사용하여 새 빨간색 트리 C를 만듭니다. L은 자체적으로 빨강 - 검정 나무이기 때문에 뿌리가 검은 색이고 불변의 색이 C 이하에서 위반되지 않습니다. 또한 검은 색 높이가 C 입니다.

그러나 R '대신 C를 R에 다시 연결할 수 없습니다. 첫째, p = q이면 R '은 R이지만 C는 적색 루트를가집니다. 이 경우 간단히 C 검정의 색을 다시 칠하십시오. 새 연결 트리 입니다.

둘째, R '이 루트가 아니면 빨간색 부모가있을 수 있습니다. 빨간 부모는 빨간 아이들을 가질 수 없으므로 균형을 다시 잡아야합니다. 여기서 우리는 R '(현재 C로 대체 됨)과 R의 루트 사이의 모든 부분에서 오카사키의 rebalancing 스키마를 적용합니다.

두 가지 가능한 경우가 있습니다. C에 조부모가 없으면 C 색이 검정색으로 변합니다. 이제 트리가 유효합니다.

C의 조부모가있는 경우 C의 부모가 빨간색이기 때문에 검정색과 검정색 높이 p + 1이어야합니다. C의 조부모를 C의 부모 루트 인 루트가되는 새로운 빨간색 트리로 교체하고 왼쪽 자식이 C이고 왼쪽이 자식이고 C의 형제, C의 조부모로 구성된 검은 색 트리의 오른쪽 자식을 오른쪽 자식으로 바꿉니다. 루트, C의 삼촌, 그 순서는 입니다. 이것은 C의 조부모의 검은 색 높이를 증가시키지 않지만 색상을 빨간색으로 변경하여 빨간색 부모의 뿌리 또는 빨간 색 어린이로 만들 수 있으므로 다시 균형을 조정해야합니다. 두 나무의 검은 높이 찾기 트리

• : O를 (LG | L |) + O (LG | R |) 정확한 지점에 R을 추적
• : O (LG | R | - LG 전자 | L |)
• 회전 수있는 모든 방법 다시 루트까지 : O (LG | R | - LG 전자 | L |)이의

없음 O (LG 전자보다 더 큰 없습니다 | R | + LG 전자 |

이 O (lg (min (| L |, | R |))))를 만들려면 먼저 척추 포인터를 뒤집으십시오. 그런 다음 큰 나무의 검은 색 높이가 필요하지 않습니다. 하나의 나무에 등뼈가 떨어질 때까지 검정색 척추를 계산하면됩니다. 그런 다음 원래 (오카사키가 아닌) 재조정 구성표를 사용하여 O (1) 노드 만 다시 균형을 잡습니다. 마지막으로 필요할 때마다 게으른 색 재현을 위해 균형을 조정할 필요가없는 척추의 나머지 부분을 표시하십시오.

Answer 2

트리를 낮은 겹침으로 결합 할 때 뭔가를 얻을 수 있지만 일반적으로 노드를 다시 교 정해야합니다. 균형을 유지하면 노드 하나를 만진 후 회전하는 규칙이있을 수 있으므로 상황이 악화됩니다. 이것은이 나무에이 ​​경우 조인 작업이라고

Given two red-black trees T1 and T2, such that keys of T1 <= keys of T2, 
find union of the two. 

, 그것은 가능하다 : 당신이 연결할 +가 마지막에 추가하는 방법에 대해 이야기 할 것 때문에

Answer 3

, 다음과 같은 문제가있는 것 같아 O (log n) 시간에 나무의 조인을하려면 체크 아웃 : http://www.cs.tau.ac.il/~wein/publications/pdfs/rb_tree.pdf

체크 아웃 : http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm, 문제 14.2.

Answer 4

각 노드의 높이 정보를 연결하여 트리를 확장하지 않을 때 O (log^2 (n))보다 좋을 수 있습니다. 2 * [log (n1) + log (n2)]에서 연결할 수 있습니다. 여기서 n1과 n2는 연결하려는 트리의 노드 수를 나타냅니다. O (log (n))에서 높이를 계산 한 후, 오른쪽으로 연결점을 찾기 위해 트리를 내려갈 때 각 노드의 잔액 정보를 사용하십시오!