무게균형수

컴퓨터 과학에서 무게 균형 이진수(WBT)는 자기 균형 이진수 검색 트리의 일종으로 동적 집합, 사전(맵) 및 시퀀스를 구현하는 데 사용할 수 있다.^[1]이 나무들은 니에베르겔트와 레이놀드에 의해 1970년대에 경계 균형 나무, 즉 BB[α] 나무로 소개되었다.^[2]^[3]그들의 더 흔한 이름은 크누스 때문이다.^[4]

WBT는 다른 자가 균형 트리와 마찬가지로 노드의 균형에 관련된 부기 정보를 저장하고 삽입 또는 삭제 작업으로 인해 균형이 흐트러졌을 때 균형을 회복하기 위해 회전을 수행한다.구체적으로, 각 노드는 노드에 뿌리를 둔 하위 트리의 크기를 저장하며, 좌우 하위 트리의 크기는 서로 어떤 요소 안에 유지된다.AVL 나무의 균형 정보(소계수의 높이에 대한 정보 사용)와 적색-흑색 나무(허구적인 "색" 비트를 저장하는 정보)와는 달리, WBT의 부기 정보는 응용 프로그램에 실제로 유용한 속성이다: 나무의 요소 수는 뿌리 크기와 같으며, 크기 정보는 정확히 정보다.순서 통계 트리 viz의 작동을 구현하기 위해 필요한 rmation. 집합에서 $n$ '번째 큰 요소를 얻거나 요소의 색인을 정렬된 순서로 결정.^[5]

무게 균형이 잡힌 나무는 기능 프로그래밍 커뮤니티에서 인기가 있으며 MIT Scheme, SLIB, Haskell의 구현에서 세트와 지도를 구현하는데 사용된다.^[6]^[4]

설명

무게 균형 트리는 노드에 하위 트리의 크기를 저장하는 이진 검색 트리입니다.즉, 노드는 필드를 가지고 있다.

키(순서된 키
값(옵션, 매핑 전용)
왼쪽, 오른쪽, 노드에 대한 포인터
크기, 정수 유형.

정의에 따르면 잎의 크기(일반적으로 a로 표현됨)nil 포인터)는 0이다.내부 노드의 크기는 두 자녀의 크기 합계에 1개(크기[n] = 크기[n.left] + 크기[n.right] + 1)를 더한 값이다.크기를 기준으로 무게[n] = 크기[n] + 1로 정의한다.^[a]

이진 트리 회전.

트리를 수정하는 작업에서는 AVL 트리에 사용되는 동일한 재조정 작업(회전 및 이중 회전)을 사용하여 모든 노드의 왼쪽 및 오른쪽 하위 트리의 무게가 서로 어떤 인자 $α$ 이내인지 확인해야 한다.공식적으로 노드 밸런스는 다음과 같이 정의된다.

노드는 무게[n.left] α·무게[n], 무게[n.right] α·무게[n]이면 α-무게

[n]이다.^[7]

여기서 $α$ 는 무게 균형 잡힌 나무를 구현할 때 결정해야 할 숫자 파라미터다. $α$ 값이 클수록 "더 균형 잡힌" 나무가 생기지만, $α$ 의 모든 값이 적절한 것은 아니다; Nievergelt와 Reingold가 증명했다.

\proc <1-{\frac {\sqrt{2}}:{2}}\약 0.29289

밸런싱 알고리즘이 작동하는 데 필요한 조건이다.나중 작업은 하한선을 보였다. $α$ 의 경우 2⁄11은 커스텀(및 더 복잡한) 리밸런싱 알고리즘을 사용하면 임의로 작게 만들 수 있지만,^[7]

균형을 올바르게 적용하면 $n개$ 의 원소가 있는 트리의 높이가^[7] 보장된다.

h\leq \log _{\frac {1}{1-\alpha }}}}{\frac {n}{2}n}\log _{2}\left({\frac {1}{1-\alpha }\right)}}=O(\log n)

$n개$ 의 삽입과 삭제의 순서에 필요한 밸런싱 작업의 수는 $n$ 으로 선형적이다. 즉, 밸런싱은 상각된 의미에서 일정한 오버헤드를 소모한다.^[8]

최소 검색 비용으로 트리를 유지하려면 삽입/삭제 작업에서 4종류의 이중 회전(LL, LR, RL, AVL 트리의 RR)이 필요하지만 로그 성능만 원한다면 LR과 RL이 단일 하향식 통과에서 필요한 회전이다.^[9]

작업 및 대량 작업 설정

무게 균형이 잡힌 나무에는 조합, 교차로, 설정 차이 등 여러 가지 세트 연산이 정의되었다.그런 다음 이러한 설정 함수에 따라 삽입 또는 삭제에 대한 빠른 대량 작업이 구현될 수 있다.이러한 설정 작업은 분할 및 결합이라는 두 가지 도우미 작업에 의존한다.새로운 운영으로, 무게 균형 잡힌 나무의 구현은 더 효율적이고 매우 평행할 수 있다.^[10]^[11]

조인: 조인 함수는 두 개의 $무게 2$ 균형이 잡힌 $t$ 와₁ t와 키 $k$ 에 있으며 $k$ 는 물론 $t 1$ , $t$ 의₂ 모든 원소가 포함된 트리를 반환한다. $k$ 는 t의 $모든 1$ 키보다 크고 $t$ 의₂ 모든 키보다 작아야 한다.두 트리의 무게가 균형 잡힌 경우 조인(Join)은 왼쪽 하위 트리 $t 1$ , 루트 $k$ 및 오른쪽 하위 트리 $t$ 로₂ 새 노드를 생성하면 된다. $t$ 의₁ $무게$ 가₂ t보다 무겁다고 가정한다(다른 경우는 대칭).조인은 t와 균형을 이루는 $노드$ $c$ 가₂ 될 때까지 $t$ 의₁ 오른쪽 척추를 따른다.이때 c를 대체하기 위해 왼쪽 child c, $루트$ $k$ , 오른쪽 child $t$ 가₂ 있는 새로운 노드가 생성된다.새 노드는 무게 균형 불변성을 무효화할 수 있다. $\alpha <1-{\frac {1}{\sqrt {2}}}$ < $\alpha <1-{\frac {1}{\sqrt {2}}}$ - $\alpha <1-{\frac {1}{\sqrt {2}}}$ 2 ${\$ 를 가정하여 단일 또는 이중 회전으로 고정할 수 있다.
분할: 무게 균형이 잡힌 나무를 키 x보다 작은 나무와 키 x보다 큰 나무 두 그루로 분할하려면 먼저 x를 나무에 삽입하여 루트부터 경로를 그린다.이 삽입 후 경로 왼쪽에서 x보다 작은 값을 모두 찾으며, 오른쪽에서 x보다 큰 값을 모두 찾는다.조인을 적용하면 왼쪽의 모든 하위 트리가 아래쪽부터 위쪽까지의 중간 노드로 경로의 키를 사용하여 상향식 통합되고 오른쪽 부분은 대칭이다.일부 응용 프로그램의 경우 분할은 x가 트리에 나타날 경우 나타내는 부울 값도 반환한다.분할 비용은 트리 높이의 순서인 $O(\log n)$ $O(\log n)$ ) ${\displaystyle$ O $(\log$ n $)}$ 이다.이 알고리즘은 실제로 무게 균형이 잡힌 트리의 어떤 특별한 특성과는 아무런 관련이 없으며, 따라서 AVL 트리와 같은 다른 균형잡힌 체계에 일반적이다.

조인 알고리즘은 다음과 같다.

함수 joinRightWB(T_L_R, k, T) (l, k', c) = 노출(T_L) = balance(T_L , T_R )가 Node_L(T_R, k, T)를 반환할 경우 다른 T' = joinRightWB(c, k, T_R)         (l', k', r') = expose(T')         if (balance( l , T' )) return Node(l, k', T')         else if (balance( l , l' ) and balance( l + l' , r' ))              return rotateLeft(Node(l, k', T'))         else return rotateLeft(Node(l, k', rotateRight(T')) function joinLeftWB(T_L, k, T_R)     /* symmetric to joinRightWB */ 함수 조인(T_L, T)이_R_R 반환되는 경우(Heavy(T_L, T_R) joinRightWB(T_L, k, T_R)가 반환되는 경우(Heavy(T_R_L, T_L) 노드(T_L, k, T_R)

여기서 균형 $(x,y)$ , $(x,y)$ ) ${\displaystyle(x,y)}$ 은 두 가중치 $x$ $x$ 과 $x$ y $y$ 이(가) 균형을 이룬다는 $y$ 것을 의미한다 $(x,y)$ .노출(v)=(l, k, r)은 트리 $노드$ v $v$ 의 $v$ 좌측 $차일드$ l{\ $displaystyle$ $l$ $}$ 을(를) 추출하는 것을 의미하며 $r$ $k$ (l $,$ k, r $)$ 는 좌측 $차일드$ $l$ ${\displaystyle l$ $키$ ${\displaystystytyle k}$ 및 우측 $k$ $차일드$ $r$ 의 노드를 생성하는 것을 의미한다. $(\displaystyle$ r $r$

분할 알고리즘은 다음과 같다.

function split(T, k)     if (T = nil) return (nil, false, nil)     (L, (m, c), R) = expose(T)     if (k = m) return (L, true, R)     if (k < m)         (L', b, R') = split(L, k)        return (L', b, join(R', m, R))     if (k > m)         (L', b, R') = split(R, k)        return (join(L, m, L'), b, R))

$A$ 와 $B$ 세트를 나타내는 두 개의 무게 균형 $t$ 와₁₂ t의 결합은 $A$ 와 $B$ 를 나타내는 무게 균형 $t$ 이다.다음과 같은 재귀 함수는 이 결합을 계산한다.

함수₁ 유니언(t₁, t₂): t = nil: return₂ t₁_<, t₁.root return join(left₁(t_<), t.root₁(t), union(오른쪽(t₁), t_>)에서 t_> = nil인 경우 t를₂₂ 반환한다.

여기서, 스플릿은 두 개의 나무를 돌려주는 것으로 추정된다. 하나는 키를 덜 쥐고 있고, 다른 하나는 더 큰 키를 쥐고 있다.(알고리즘은 비파괴적이지만, 내부 파괴 버전도 존재한다.)

교차점이나 차이에 대한 알고리즘은 유사하지만 조인(Join)과 동일하지만 중간 키가 없는 조인2 도우미 루틴이 필요하다.조합, 교차로 또는 차이에 대한 새로운 기능에 기초하여, 하나의 키 또는 복수의 키를 무게 균형이 잡힌 트리에 삽입하거나 삭제할 수 있다.스플릿(Split)과 유니온(Union)은 조인(Join)을 부르지만 무게 균형 잡힌 나무의 균형 기준을 직접 다루지 않기 때문에, 그러한 구현을 보통 조인 기반 알고리즘이라고 부른다.

조합, 교차로 $O\left(m\log \left({n \over m}+1\right)\right)$ 차이의 복잡도는 $m$ ${\displaystyle$ $m$ $}$ 과 $m$ $O\left(m\log \left({n \over m}+1\right)\right)$ 와) $n(\geq m)$ 와 $n(\geq m)$ 크기의 무게 균형이 잡힌 두 트리에 대해 $O\left(m\log \left({n \over m}+1\right)\right)$ $($ $lift ({$ $n(\geq m)$ $\n$ \ $over$ $O\left(m\log \left({n \over m}+1\right)\right)$ m $}+$ $1\$ $right$ $)\$ $right$ $)}$ 이다 $n(\geq m)$ 이 복잡성은 비교 횟수에 있어서 최적이다.이후 노조, 교차로 또는 차이에 반복적인 호출은 서로 독립적이다 더욱 중요한 것은, 그들은 병렬로 언제 m=1{\displaystyle m=1}O{O(m\log n\log)\displaystyle}.[10](로그 ⁡ m로그 ⁡ n)는 평행하는 깊이를 실행할 수 있으면join-based 구현은 같은 computational 원자가 비고리형인그램을 감독했다.aph(DAG) 작은 트리를 분할하는 데 큰 트리의 루트를 사용하는 경우 단일 요소 삽입 및 삭제로 한다.

메모들

^ 니에베르겔트와 레이놀드가 사용한 정의다.아담스는 그 크기를 직접 무게로 사용하며,^[6] 이것은 그의 변종 분석을 복잡하게 만들고 주요 구현에 버그로 이어졌다.^[4]

참조

^ Tsakalidis, A. K. (1984). "Maintaining order in a generalized linked list". Acta Informatica. 21: 101–112. doi:10.1007/BF00289142.
^ Nievergelt, J.; Reingold, E. M. (1973). "Binary Search Trees of Bounded Balance". SIAM Journal on Computing. 2: 33–43. doi:10.1137/0202005.
^ 이 문서에는 NIST 문서의 공용 도메인 자료가 포함되어 있다.
^ ^a ^b ^c Hirai, Y.; Yamamoto, K. (2011). "Balancing weight-balanced trees" (PDF). Journal of Functional Programming. 21 (3): 287. doi:10.1017/S0956796811000104.
^ Roura, Salvador (2001). A new method for balancing binary search trees. ICALP. Lecture Notes in Computer Science. Vol. 2076. pp. 469–480. doi:10.1007/3-540-48224-5_39. ISBN 978-3-540-42287-7.
^ ^a ^b Adams, Stephen (1993). "Functional Pearls: Efficient sets—a balancing act". Journal of Functional Programming. 3 (4): 553–561. doi:10.1017/S0956796800000885.
^ ^a ^b ^c Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. pp. 61–71.
^ Blum, Norbert; Mehlhorn, Kurt (1980). "On the average number of rebalancing operations in weight-balanced trees" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3.
^ Cho, Seonghun; Sahni, Sartaj (2000). "A New Weight Balanced Binary Search Tree". International Journal of Foundations of Computer Science. 11 (3): 485–513. doi:10.1142/S0129054100000296.
^ ^a ^b Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0.
^ Adams, Stephen (1992), Implementing sets efficiently in a functional language, CiteSeerX 10.1.1.501.8427.

[7] 니에베르겔트와 레이놀드가 사용한 정의다.아담스는 그 크기를 직접 무게로 사용하며,^[6] 이것은 그의 변종 분석을 복잡하게 만들고 주요 구현에 버그로 이어졌다.^[4]

[1] Tsakalidis, A. K. (1984). "Maintaining order in a generalized linked list". Acta Informatica. 21: 101–112. doi:10.1007/BF00289142.

[2] Nievergelt, J.; Reingold, E. M. (1973). "Binary Search Trees of Bounded Balance". SIAM Journal on Computing. 2: 33–43. doi:10.1137/0202005.

[3] 이 문서에는 NIST 문서의 공용 도메인 자료가 포함되어 있다.

[Hirai-4] Hirai, Y.; Yamamoto, K. (2011). "Balancing weight-balanced trees" (PDF). Journal of Functional Programming. 21 (3): 287. doi:10.1017/S0956796811000104.

[5] Roura, Salvador (2001). A new method for balancing binary search trees. ICALP. Lecture Notes in Computer Science. Vol. 2076. pp. 469–480. doi:10.1007/3-540-48224-5_39. ISBN 978-3-540-42287-7.

[Adams-6] Adams, Stephen (1993). "Functional Pearls: Efficient sets—a balancing act". Journal of Functional Programming. 3 (4): 553–561. doi:10.1017/S0956796800000885.

[brass-8] Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. pp. 61–71.

[9] Blum, Norbert; Mehlhorn, Kurt (1980). "On the average number of rebalancing operations in weight-balanced trees" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3.

[10] Cho, Seonghun; Sahni, Sartaj (2000). "A New Weight Balanced Binary Search Tree". International Journal of Foundations of Computer Science. 11 (3): 485–513. doi:10.1142/S0129054100000296.

[join-based-11] Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0.

[adams-12] Adams, Stephen (1992), Implementing sets efficiently in a functional language, CiteSeerX 10.1.1.501.8427.

[1]

[2]

[3]

[4]

[5]

[6]

[a]

[7]

[8]

[9]

[10]

[11]

v t 트리 데이터 구조
나무 검색 (이중 세트/관련 배열)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (최적) 이진 검색 춤 HTree 간격 오더통계 (좌편향) 빨강-검은색 희생양 스플레이 T 트레프 UB 무게균형
힙스	이진수 이항체 브로달 피보나치 좌익 페어링 스큐 판 엠드 보아스 약한
시도하다	씨트리 C-트리(압축 ADT) 해시 라딕스 접미사 3차 검색 X-fast Y-fast
공간 데이터 분할 트리	볼 BK BSP 카르테시안 힐베르트 R k-d(일반적으로 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 세그먼트 부사장 X
다른 나무들	커버 지수적 펜윅 손가락 프랙탈 트리 지수 퓨전 해시 캘린더 아이 디스턴스 케이애리 왼손잡이 우시블링 링크/컷 로그 구조 병합 머클 p q. 범위 SPQR 톱

Search

무게균형수

네임스페이스

더

목차

설명

작업 및 대량 작업 설정

메모들

참조