WAVL 트리

컴퓨터 과학에서 WAVL 트리나 약한 AVL 트리는 자가 균형 이진 검색 트리다.WAVL 트리는 균형잡힌 탐색 나무의 또 다른 유형인 AVL 트리의 이름을 따서 명명되었으며, AVL 트리와 적흑흑백나무 둘 다와 밀접한 관련이 있으며, 모두 순위 균형잡힌 나무의 공통된 틀에 속한다.WAVL 트리는 균형 잡힌 다른 바이너리 검색 트리와 마찬가지로 삽입, 삭제, 검색 작업을 작업당 O(log n) 시간에 처리할 수 있다.^[1][2]

WAVL 트리는 AVL 트리와 빨간색-검은색 트리의 가장 좋은 특성 중 일부를 결합하도록 설계되었다.One advantage of AVL trees over red–black trees is being more balanced: they have height at most ${\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}$ (for a tree with n data items, where ${\displaystyle \varphi }$ is the golden ratio), while red–black trees have larger maximum height, ${\displaystyle 2{\mathrm{lo}}_{}}$${\displaystyle g_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}n}$ ${\displaystyle 2\log _{2}n$ WAVL 트리를 삭제하지 않고 삽입만 사용하여 생성하는 경우 AVL 트리와 동일한 작은 높이를 가진다.반면 적색-흑색 나무는 AVL 나무보다 나무 재조정이 덜하다는 장점이 있다.AVL 트리의 경우, 각 삭제에는 로그의 트리 회전 작업이 필요할 수 있으며, 적색-흑색 트리는 일정한 수의 트리 회전만 사용하는 더 간단한 삭제 작업이 있다.WAVL 나무는 적색-흑색 나무와 마찬가지로 일정한 나무 회전수만 사용하며, 상수는 적색-흑색 나무보다 훨씬 좋다.^[1][2]

WAVL 트리는 Haupler, Sen & Tarjan(2015년)에 의해 소개되었다.같은 저자는 또한 AVL 나무, WAVL 나무, 적-흑색 나무를 모두 순위 균형의 나무의 한 종류로 보는 공통점을 제공했다.^[2]

정의

보다 일반적으로 이진 검색 트리와 마찬가지로 WAVL 트리는 내부 노드와 외부 노드의 두 가지 유형으로 구성된 노드 모음으로 구성된다.내부 노드는 데이터 항목을 저장하며, 상위 항목(부모가 없는 지정된 루트 노드 제외)과 트리 내의 정확히 두 하위 항목(왼쪽 자식 및 오른쪽 자식)에 연결된다.외부 노드는 데이터를 전송하지 않으며 트리의 상위 노드에 대한 링크만 가지고 있다.이 노드들은 이진 트리를 형성하도록 배열되어 있어서, 어떤 내부 노드 x에 대해서도 x의 좌우 자식들의 부모는 x 그 자체다.외부 노드가 나무의 잎을 형성한다.^[3]데이터 항목은 트리의 inorder traversal이 데이터 항목을 정렬된 순서로 나열하는 방식으로 트리에 배열된다.^[4]

WAVL 트리와 다른 유형의 바이너리 검색 트리를 구별하는 것은 순위를 사용하는 것이다.이것들은 각 노드와 관련된 숫자로, 노드에서 가장 먼 잎 후손까지의 거리에 근사치를 제공한다.순위가 노드의 높이와 같도록 정의된 AVL 트리에서와 달리, 순위는 WAVL 트리의 높이와 항상 같지 않다.노드 x의 순위 차이는 x의 상위와 x의 순위 차이로 정의된다.등급은 다음과 같은 특성을 준수해야 한다.^[1][2]

• 외부 노드 속성:모든 외부 노드에 순위 0이^[5] 있음
• 순위 차이 속성: 루트 노드가 아닌 노드에 r 등급이 있는 경우 상위 노드의 등급은 r + 1 또는 r + 2여야 한다.즉, 루트 노드가 아닌 노드의 순위 차이는 1 또는 2이다.^[1]
• 내부 노드 속성:두 명의 외부 자녀가 있는 내부 노드는 정확히 1위를 가져야 한다.

운영

검색 중

WAVL 트리에서 키 k를 검색하는 것은 균형 잡힌 이진 검색 트리 데이터 구조에서와 매우 동일하다.하나는 트리의 뿌리에서 시작하여, 그 다음 k가 노드의 값보다 작을 때 노드의 왼쪽 자식까지의 경로를 따라, 대신 노드의 오른쪽 자식까지의 경로를 따라 루트로부터 경로의 각 노드에 저장된 데이터 항목과 k를 반복적으로 비교한다.값이 k인 노드에 도달하거나 외부 노드에 도달하면 검색이 중지된다.^[6]

내부 노드에서 검색이 중지되면 키 k가 발견된 것이다.대신 외부 노드에서 검색이 중지되면 k가 삽입될 위치(삽입된 경우)가 발견된 것이다.^[6]

삽입

키 k가 있는 내부 노드를 WAVL 트리에 삽입하려면 트리에서 k를 검색하여 외부 노드에서 종료한 다음, 해당 외부 노드를 외부 자식 두 명이 있는 새 내부 노드로 교체하고 마지막으로 트리의 재조정 작업이 필요하다.리밸런싱 단계는 하향식 또는 상향식 중 하나를 수행할 수 있지만 상향식 리밸런싱은 AVL 트리와 가장 밀접하게 일치하는 버전이다.^[2][1][2]

상향식 균형 재조정은 처음에 새로 삽입된 노드와 그 상위 노드 사이의 순위 차이를 고려하는 것으로 시작된다.부모가 없으면 균형이 회복된다.삽입이 시작되기 전에는 상위와 노드 간 순위 차이가 1이나 2였지만, 노드에 뿌리를 둔 하위 트리가 더 커졌기 때문에 그 차이가 1로 줄었다.상위와 노드 간의 새로운 순위 차이가 1이면 균형이 복원된다.그렇지 않으면, 부모의 다른 자녀인 형제자매가 부모와의 순위 차이가 1인 경우, 부모를 승진시키고, 형제자매와 자식 간의 순위 차이를 증가시킴으로써 그 순위를 증가시키며, 오래된 부모를 새로운 노드로 계속 재조정한다.

마지막으로, 노드와 형제자매에 대한 순위 차이가 0과 2인 경우, 하나 또는 두 개의 트리 회전과 순위 차이에 대한 관련 조정은 균형을 회복할 수 있다.노드의 중간 자식은 노드와 부모 키 사이에 키를 가진 자이다.해당 아동과 노드의 순위 차이가 2인 경우, 회전하여 트리의 노드를 위로 이동하고 상위 노드를 아래로 이동한 다음 상위 - 상위 - 주변의 순위 차이를 조정하여 순위를 낮추고 균형을 복원한다.그렇지 않은 경우 회전하여 아이를 위아래로 이동한 다음 다시 회전하여 아이를 위아래로 이동시킨다.자식을 승격시키고, 노드와 부모를 강등시키고, 균형이 회복된다.

따라서 전체적으로 삽입 절차는 검색, 일정한 수의 새 노드 생성, 로그의 순위 변경, 일정한 트리 회전수로 구성된다.^[1][2]

삭제

WAVL 트리에서 내부 노드를 삭제하는 것은 일반적인 이진 검색 트리 삭제로 시작한다.외부 자식이 없는 내부 노드에 대해서는, 그것은 트리에서 후계자를 찾고, 그 후계자와 노드를 교환한 다음, 그 왼쪽 노드가 반드시 외부 노드인 새로운 트리 위치에서 노드를 제거하는 것을 의미한다.외부 자식 노드가 있는 내부 노드를 제거하려면 노드를 다른 자식 노드로 교체하십시오.

상향식 균형 재조정은 노드-초기, 삭제된 노드를 대체한 노드-와 그 상위 노드 간의 순위 차이를 고려하는 것으로 시작된다.부모가 없으면 균형이 회복된다.삭제가 시작되기 전에는 상위와 노드 간 순위 차이가 1이나 2였지만, 노드에 뿌리를 둔 하위 트리가 짧아져 그 차이가 1이 늘었다.현재 부모에게 두 명의 외부 자녀가 있는 경우, 부모가 2위를 차지하기 때문에 내부 노드 속성이 침해된다.상위 항목을 강등해야 하며, 너무 짧은 하위 트리의 루트인 노드로 상위 항목을 재조정하는 작업이 계속되었다.

노드에 상위 노드가 없으면 밸런스가 복원된다.노드와 상위 간 순위 차이가 1에서 2로 커지면 균형이 복원된다.그렇지 않은 경우, 부모의 다른 자식인 형제자매가 부모와의 순위 차이가 2인 경우, 부모를 강등시키고, 형제자매와 자식 간의 순위 차이를 감소시켜 순위를 낮추고, 오래된 부모를 새로운 노드로 계속 재조정한다.그렇지 않으면 형제자매의 두 자녀가 형제자매와 순위 차이가 2인 경우 부모 및 형제자매를 강등시키고 이전 부모와의 균형을 새 노드로 계속 재조정한다.

마지막으로, 노드와 형제자매의 순위 차이가 3과 1이고, 형제자매가 순위 차이 1인 아이를 가지면, 순위 차이에 대한 관련 조정과 함께 한 두 개의 나무 회전이 균형을 회복할 수 있다.형제자매의 자녀들을 조카딸과 조카딸로 구분하되, 조카딸의 열쇠는 부모와 형제자매의 열쇠 사이에 놓여 있고 조카의 열쇠는 그렇지 않다.형제자매와 조카의 순위 차이가 1인 경우에는 회전하여 형제자매를 위아래로 이동시키고 형제자매를 승진시키며, 필요시 내부노드 속성을 위반하지 않도록 최소한 한 번, 그리고 두 번 부모를 강등시킨다.그렇지 않으면 형제와 조카의 계급차가 1인 상태에서 조카딸을 위아래로 이동시키기 위해 회전하고, 조카딸을 위아래로 이동시키기 위해 다시 회전하며, 조카딸을 두 번 승진시키고, 동생을 한 번 강등시키고, 부모를 두 번 강등시킨다.

전체적으로 삭제는 외부 자녀가 있는 노드를 찾기 위한 하향 검색, 일정한 수의 새 노드 제거, 로그 수 순위 변경, 일정한 나무 회전 수로 이루어진다.[1][2]

AVL 트리의 여러 수준에서 회전을 유발하는 삭제 결과와 WAVL 트리에서 수행되는 회전 및 순위 변경을 비교할 수 있다.두 번째 이미지에서 값이 12인 노드가 삭제된 후 오른쪽 회전하고 모든 외부 노드의 순위를 0으로 할당했다.

계산 복잡성

WAVL 트리의 각 검색, 삽입 또는 삭제는 트리의 단일 경로를 추적하고 경로의 각 노드에 대해 일정한 수의 단계를 수행하는 것을 포함한다.In a WAVL tree with n items that has only undergone insertions, the maximum path length is ${\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}$. If both insertions and deletions may have happened, the maximum path length is ${\displaystyle 2\log _{2}n}$.따라서 두 경우 모두 데이터 항목이 n개인 WAVL 트리에서 각 검색, 삽입 또는 삭제에 대한 최악의 시간은 O(log n)이다.

또한 삽입과 삭제를 위한 노드를 찾은 후에는 트리 구조 조정 작업의 상각 복잡성이 일정하게 유지된다.노드 자체를 추가하거나 삭제하는 것은 일정한 시간이고, 회전량은 항상 일정하며, 노드의 총 순위 변화량은 삽입과 삭제 횟수가 모두 선형임을 알 수 있다.

관련 구조물

WAVL 트리는 AVL 트리와 빨간색-검은색 트리와 밀접한 관련이 있다.모든 AVL 트리는 WAVL 트리로 만드는 방식으로 노드에 순위를 할당할 수 있다.그리고 모든 WAVL 트리는 노드가 빨간색과 검은색(그리고 그 등급은 재배정)으로 색칠되어 빨강-검은색 트리로 만들어질 수 있다.그러나 일부 WAVL 트리는 이런 방식으로 AVL 나무에서 나오지 않으며, 일부 적색-검은색 나무는 이런 방식으로 WAVL 나무에서 나오지 않는다.

AVL 나무

AVL 트리는 균형 잡힌 이진 검색 트리의 일종으로, 각 내부 노드의 두 하위 노드의 높이가 최대 한 개씩 달라야 한다.^[7]외부 노드의 높이는 0이며, 내부 노드의 높이는 항상 1에 최대 2자녀의 키까지 더한다.따라서 AVL 트리의 높이 함수는 WAVL 트리의 제약 조건을 준수하며, 우리는 각 노드의 높이를 순위로 사용하여 모든 AVL 트리를 WAVL 트리로 변환할 수 있다.^[1][2]

AVL 트리와 WAVL 트리의 주요 차이는 노드가 같은 순위나 키를 가진 두 아이를 가질 때 발생한다.AVL 트리에서, 노드 x가 서로 같은 키의 두 아이를 가지고 있다면, x의 높이는 정확히 h + 1이어야 한다.이와는 대조적으로 WAVL 트리에서 노드 x가 r 등급이 같은 두 자녀를 가지고 있는 경우 x의 등급은 r + 1 또는 r + 2가 될 수 있다.WAVL 트리에서 등급이 키와 엄격히 같지 않기 때문이다.이러한 순위 유연성은 구조에서도 더 큰 유연성을 가져온다. 일부 WAVL 트리는 아이들의 키가 둘 이상 차이가 나는 노드를 포함하기 때문에 순위를 수정해도 AVL 트리로 만들 수 없다.^[2]그러나 우리는 모든 AVL 나무는 WAVL 나무라고 말할 수 있다.AVL 트리는 2등급 차이의 자녀를 둘 다 가진 노드 유형이 없는 WAVL 트리다.^[1]

WAVL 트리가 삽입 연산만을 사용하여 생성되는 경우 그 구조는 동일한 삽입 시퀀스에 의해 생성된 AVL 트리의 구조와 같으며, 그 등급은 해당 AVL 트리의 등급과 같게 된다.WAVL 트리는 삭제 작업을 통해서만 AVL 트리와 다를 수 있다.특히 삽입을 통해서만 생성된 WAVL 트리의 높이가 최대 ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {log}_{}}$ ${\displaystyle n{}_{}}$ ${\displaystyle 1.44}$ ${\displaystyle {\mathrm{로그}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle n}$ ${\displaystyle \log _{\varphi }n\$ 약 $1.44\log _{2}n}$임을 의미한다$.$^[2]

붉은-검은 나무

빨간색-검은색 트리는 각 노드의 색(빨간색 또는 검은색)이 있는 균형 잡힌 이진 검색 트리로서, 다음과 같은 속성을 만족한다.

• 외부 노드는 검은색이다.
• 내부 노드가 빨간색이면 두 자녀 모두 검은색이다.
• 루트에서 외부 노드로의 모든 경로에는 동일한 수의 검은색 노드가 있다.

적색-흑색 트리는 다음과 같은 요건을 충족하면서 노드에 저장되는 등급 체계로 동등하게 정의될 수 있다(WAVL 트리의 등급 요구사항과 다름).

• 외부 노드의 순위는 항상 0이고 그 부모의 순위는 항상 1이다.
• 루트 노드가 아닌 노드의 순위는 상위 노드의 순위 또는 상위 노드의 - 1과 동일하다.
• 어떤 루트-리프 경로에서도 순위 차이가 0인 연속된 두 에지는 없다.

색상 기반 정의와 순위 기반 정의 사이의 동등성은 한 방향으로 상위 항목이 더 큰 경우 노드를 검은색으로, 상위 항목이 같은 경우 빨간색으로 염색하여 확인할 수 있다.다른 방향에서는 검정 노드의 순위를 외부 노드의 경로에 있는 검정 노드 수와 같게 하고, 빨간색 노드의 순위를 상위 노드와 같게 하여 색상을 등급으로 변환할 수 있다.^[8]

WAVL 트리의 노드 순위는 각 순위를 2로 나누고 가장 가까운 정수로 반올림하여 적색-흑색 트리에 대한 요구 사항을 준수하는 노드 순위 시스템으로 변환할 수 있다.^[9]이러한 변환 때문에 모든 WAVL 트리에 대해 동일한 구조를 가진 유효한 빨간색-검은색 트리가 존재한다.적색-검은색 트리의 최대 $높이{\displaystyle \mathrm{}}$ 2 ${\displaystyle {로그\mathrm{}}_{}}$ 2${\displaystyle {}_{}\mathrm{nn}}${\$displaystyle 2\log _{2$}n$}$이(가) 있기 때문에 WAVL 트리의 경우도 마찬가지다$.$^[1][2]그러나 유효한 WAVL 트리 순위 기능을 부여할 수 없는 적색-흑색 트리가 존재한다.^[2]

WAVL 트리는 나무 구조상 적색-흑색의 특별한 경우임에도 불구하고 업데이트 운영은 다르다.WAVL 트리 업데이트 작업에 사용되는 트리 회전은 트리의 단일 경로에서만 색상을 변경하기 보다는 사실상 빨간색-검은색 트리의 큰 하위 트리를 기억하기 때문에 빨간색-검은색 트리에서 허용되지 않는 변경을 할 수 있다.^[2]이를 통해 WAVL 트리는 적색 흑색 트리보다 삭제당 나무 회전을 더 적게 수행할 수 있다.^[1][2]

참조