shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
재귀 문법과 일부 입력의 경우, 파스 트리의 깊이가 입력 크기에 비례할 수 있으므로, LR 파서와 팩랫 파서 모두 동일한 최악의 경우 점근적 성능을 가지는 것으로 보인다. 그러나 많은 도메인, 예를 들어 수기로 작성된 소스 코드에서는 표현식 중첩 깊이가 프로그램 길이에 관계없이 효과적으로 일정한 한계를 가지는데, 특정 깊이 이상으로 중첩된 표현식은 리팩터링되는 경향이 있기 때문이다. 전체 파스 트리를 유지할 필요가 없을 때, 더 정확한 분석은 입력 크기와 별도로 파스 트리의 깊이를 고려할 것이다.
계산 모델.
선형적 전체 복잡성을 달성하기 위해서는 메모이제이션에 사용되는 저장 공간이 개별 메모이제이션된 데이터 항목에 대한 분할 상환 상수 시간 접근을 제공해야 한다. 실제로는 문제가 되지 않는다. 예를 들어 동적으로 크기가 조정되는 해시 테이블이 이를 달성한다. 하지만 이는 포인터 산술을 사용하므로, 랜덤 접근 기계를 전제한다. 데이터 구조와 알고리즘에 대한 이론적 논의는 더 제한적인 모델(아마도 람다 대수 또는 스킴의 모델)을 전제하는 경향이 있는데, 여기서 희소 테이블은 트리로 구축되어야 하며 데이터 항목 접근은 상수 시간이 아니다. LL 파서와 같은 전통적인 파싱 알고리즘은 이에 영향을 받지 않지만, 팩랫 파서의 평판에 불이익이 된다: 팩랫 파서는 겉보기에 평판이 좋지 않은 연산에 의존한다.
반대로 보면, 이는 팩랫 파서가 실제 시스템에서 쉽게 사용할 수 있는 계산 능력을 활용하며, 오래된 파싱 알고리즘은 이를 활용하는 방법을 알지 못했다는 것을 의미한다.
간접 좌측 재귀.
PEG는 좌측 재귀 규칙, 즉 비단말이 동일한 비단말이 가장 왼쪽에 있는 기호로 나타나는 표현식으로 확장될 수 있는 규칙을 포함하지 않으면 잘 형성되었다고 한다. 좌측에서 우측으로의 하향식 파서의 경우, 이러한 규칙은 무한 회귀를 야기한다. 즉, 파싱은 문자열에서 앞으로 나아가지 않고 동일한 비단말을 계속 확장할 것이다. 따라서 팩랫 파싱을 허용하려면 좌측 재귀를 제거해야 한다.
실제적 중요성.
좌측 또는 우측이든 직접 재귀는 문맥 자유 문법에서 중요하다. 왜냐하면 재귀가 반복을 설명하는 유일한 방법이기 때문이다.
Sum → Term | Sum '+' Term | Sum '-' Term
Args → Arg | Arg ',' Args
문맥 자유 문법 사용에 익숙한 사람들은 종종 동일한 관용구를 사용하기 위해 PEG를 기대하지만, 파싱 표현식은 재귀 없이 반복을 수행할 수 있다.
Sum ← Term ( '+' Term / '-' Term )*
Args ← Arg ( ',' Arg )*
차이점은 생성되는 추상 구문 트리에 있다. 재귀를 사용하면 각 codice_43 또는 codice_44가 최대 두 개의 자식을 가질 수 있지만, 반복을 사용하면 임의의 많은 자식을 가질 수 있다. 예를 들어 마이크로프로세서의 덧셈 명령어는 일반적으로 두 개의 피연산자만 허용하므로, 후속 처리 단계에서 이러한 자식 목록을 유한 차수를 가진 트리로 재구성해야 하는 경우, 좌측 결합성과 같은 속성은 PEG 지향 파싱 단계 이후에 부여될 것이다.
따라서 좌측 재귀는 문맥 자유 관용구를 고집하지 않는 한 LL(k) 문맥 자유 파서보다 PEG 팩랫 파서에 문제를 일으킬 가능성이 실제로는 적다. 그러나 모든 재귀의 경우가 반복에 관한 것은 아니다.
비반복 좌측 재귀.
예를 들어, 위 산술 문법에서 연산자 우선순위를 순서 선택으로 표현하려는 유혹이 있을 수 있다. — codice_45는 먼저 codice_43으로 보려고 시도하고(하향식으로 파싱하므로), 두 번째로 codice_47로 보려고 시도하고, 세 번째로 codice_48로 보려고 시도한다는 의미이다. — 이는 정의의 중첩을 통하는 것보다 더 간단하다. 이 (잘못 형성된) 문법은 우선순위 순서를 한 줄에만 유지하려고 한다.
Value ← [0-9.]+ / '(' Expr ')'
Product ← Expr (('*' / '/') Expr)+
Sum ← Expr (('+' / '-') Expr)+
Expr ← Sum / Product / Value
불행히도 codice_49을 일치시키려면 codice_43이 일치하는지 테스트해야 하고, codice_43을 일치시키려면 codice_49이 일치하는지 테스트해야 한다. 이 항이 가장 왼쪽에 나타나기 때문에 이러한 규칙들은 해결할 수 없는 순환 정의를 이룬다. (원래 첫 번째 예시의 공식화처럼 해결될 수 있는 순환 정의도 존재하지만, 그러한 정의는 병리적 재귀를 보이지 않아야 한다.) 그러나 좌측 재귀 규칙은 항상 좌측 재귀를 제거하도록 다시 작성될 수 있다. 예를 들어, 다음 좌측 재귀 CFG 규칙:
는 플러스 연산자를 사용하여 PEG로 다시 작성될 수 있다.
간접 좌측 재귀 규칙을 다시 작성하는 과정은 일부 팩랫 파서에서 복잡하며, 특히 의미론적 동작이 관련될 때 더욱 그렇다.
일부 수정으로 전통적인 팩랫 파싱은 직접 좌측 재귀를 지원할 수 있지만, 그렇게 하면 선형 시간 파싱 속성이 손실된다. 이는 원래 PEG 및 팩랫 파싱을 사용하는 정당성이다. 오직 OMeta 파싱 알고리즘만이 추가 복잡성 없이 완전한 직접 및 간접 좌측 재귀를 지원하며(다시 말하지만, 선형 시간 복잡성은 손실된다), 모든 GLR 파서들은 좌측 재귀를 지원한다.
예상치 못한 동작.
PEG에 대한 흔한 첫인상은 정규 표현식과 같은 반복 연산자 codice_53와 미리보기 조건자 codice_54와 같은 특정 편의 기능과 모호성 해결을 위한 순서 선택을 가진 CFG처럼 보인다는 것이다. 이러한 이해는 언어 파서를 만들려는 목표를 가질 때 충분할 수 있지만, 파싱 표현식의 계산 능력에 대한 더 이론적인 논의에는 충분하지 않다. 특히 문맥 자유 문법의 비순서 선택 codice_55에 내재된 비결정론은 결정론적 순서 선택 codice_32와 매우 다르다.
중간 지점 문제.
PEG 팩랫 파서는 다음과 같은 모호하지 않은 비결정적 CFG 규칙을 인식할 수 없다.
S ← 'x' S 'x' | 'x'
LL(k) 및 LR(k) 파싱 알고리즘 모두 이 예시를 인식할 수 없다. 그러나 이 문법은 CYK 알고리즘과 같은 일반 CFG 파서에서 사용될 수 있다. 그럼에도 불구하고, 이 문제의 언어는 실제로 정규 언어(홀수 개의 x 문자열)이므로 이러한 모든 종류의 파서에서 인식될 수 있다.
PEG 파서가 codice_57 문자열에 대해
S ← 'x' S 'x' / 'x'
를 일치시키려고 시도할 때 정확히 어떤 일이 발생하는지 살펴보는 것은 유익하다. 예상대로, codice_58에 대한 일치에 실패할 때까지 문자열의 증가하는 위치에서 비단말 codice_59를 재귀적으로 일치시키려고 시도하며, 그 후 퇴각검색을 시작한다. 과정은 다음과 같다:
위치: 123456
문자열: xxxxxq
결과: ↑ 위치 6: S의 어떤 분기도 일치하지 않음
↑ 위치 5: S의 첫 번째 분기 실패, 두 번째 분기 성공, 길이 1 일치 결과.
↑ 위치 4: S의 첫 번째 분기 실패, 두 번째 분기 성공, 길이 1 일치 결과.
↑ 위치 3: S의 첫 번째 분기 성공, 길이 3 일치 결과.
↑ 위치 2: S의 첫 번째 분기 실패, 3에서의 S 일치 후 q가 오기 때문.
두 번째 분기 성공, 길이 1 일치 결과.
↑ 위치 1: S의 첫 번째 분기 성공, 길이 3 일치 결과.
파싱 표현식에 대한 일치는 탐욕적이다. 즉, 발견된 첫 번째 성공만이 고려된다. 비록 지역적으로 선택이 가장 긴 것을 먼저 하도록 순서가 지정되어 있더라도, 이 탐욕적인 일치가 전역적으로 가장 긴 일치를 찾을 것이라는 보장은 없다.
모호성 감지 및 규칙 순서가 일치하는 언어에 미치는 영향.
LL(k) 및 LR(k) 파서 생성기는 입력 문법이 모호하면 완료되지 않는다. 이는 문법이 모호하지 않아야 하지만 결함이 있는 일반적인 경우에 유용한 기능이다. PEG 파서 생성기는 의도하지 않은 모호성을 가장 먼저 일치하는 것으로 해결하며, 이는 임의적일 수 있고 예상치 못한 구문 분석으로 이어질 수 있다.
PEG 문법에서 생성의 순서는 모호성 해결뿐만 아니라 일치하는 언어에도 영향을 미친다. 예를 들어, 포드(Ford)의 논문에 있는 첫 번째 PEG 예시(pegjs.org/online 표기법으로 다시 작성하고 및 로 레이블링함)를 고려하라:
포드는 후자의 PEG 규칙에서 두 번째 대안은 입력 문자열이 'a'로 시작하면 첫 번째 선택이 항상 이루어지기 때문에 결코 성공하지 못한다고 언급한다.
구체적으로, (즉, 과 일치하는 언어)는 입력 "ab"를 포함하지만, 는 포함하지 않는다.
따라서 PEG 문법에 새로운 옵션을 추가하면 일치하는 언어에서 문자열을 제거할 수 있다. 예를 들어, 는 에 의해 일치되지 않는 문자열을 포함하는 단일 생성 문법 에 규칙을 추가한 것이다.
더욱이 PEG 문법 과 로부터 와 일치하는 문법을 구성하는 것은 항상 사소한 작업이 아니다.
이는 새로운 생성이 문자열을 제거할 수 없는 CFG와는 극명한 대조를 이룬다(모호성 형태로 문제를 도입할 수는 있지만),
그리고 에 대한 (잠재적으로 모호한) 문법은 다음과 같이 구성될 수 있다.
S → start(G1) | start(G2)
파싱 표현식 문법 이론.
파싱 표현식 문법으로 인식할 수 없는 문맥 자유 언어의 구체적인 예시를 제시하는 것은 미해결 문제이다. 특히, 파싱 표현식 문법이 회문 언어를 인식할 수 있는지 여부는 미해결이다.
파싱 표현식 언어 클래스는 집합 교차 및 여집합에 대해 닫혀 있으며, 따라서 집합 합집합에 대해서도 닫혀 있다.
공백성 결정 불가능.
문맥 자유 문법의 경우와는 극명한 대조를 이루게도, 파싱 표현식 문법으로부터 파싱 표현식 언어의 요소를 생성하는 것은 불가능하다. 실제로, 파싱 표현식 문법에 의해 인식되는 언어가 비어있는지 여부를 알고리즘적으로 결정하는 것은 불가능하다! 이에 대한 한 가지 이유는 포스트 대응 문제의 모든 인스턴스가 파싱 표현식 언어가 비어있는지 결정하는 문제의 인스턴스로 환원되기 때문이다.
포스트 대응 문제의 인스턴스는 문자열(단말 기호) 쌍의 목록 formula_24으로 구성된다는 것을 상기하라. 문제는 formula_25 범위의 인덱스 시퀀스 formula_26가 존재하여 formula_27을 만족하는지 결정하는 것이다. 이것을 파싱 표현식 문법으로 환원하려면, formula_28을 임의의 서로 다른 동일한 길이의 단말 기호 문자열로 두고(이미 2개의 다른 기호가 단말 기호 알파벳에 있으면, formula_29 길이가 충분하다) 다음 파싱 표현식 문법을 고려하라.
비단말 formula_31에 의해 일치되는 모든 문자열은 일부 인덱스 formula_32에 대해 formula_33 형식을 가진다. 마찬가지로 비단말 formula_34에 의해 일치되는 모든 문자열은 formula_35 형식을 가진다. 따라서 formula_36에 의해 일치되는 모든 문자열은 formula_37인 formula_38 형식을 가질 것이다.
PEG는 아래 뜻을 함의한다.
온 더 플라이(On the fly)는 변경 사항이 영향을 미치는 프로세스가 진행 중인 동안 변경되는 것을 설명하는 데 사용되는 구문이다. 이는 자동차, 컴퓨터 및 요리 산업에서 사용된다. 자동차에서 온 더 플라이는 자동차가 여전히 주행 중일 때 자동차의 구성을 변경하는 것을 설명하는 데 사용될 수 있다. 자동차가 여전히 주행 중일 때 발생할 수 있는 프로세스에는 일부 자동차에서 2륜 구동과 4륜 구동 간 전환, 일부 컨버터블 자동차에서 지붕 열고 닫기가 포함된다. 컴퓨팅에서 온 더 플라이 CD 라이터는 한 CD에서 데이터를 읽어 컴퓨터 메모리에 저장하지 않고 다른 CD에 쓸 수 있다. 멀티태스킹 운영 체제에서 프로그램을 온 더 플라이로 전환한다는 것은 네이티브 및 에뮬레이트된 프로그램이나 애플리케이션을 일시 중지, 정지 또는 지연시키거나 기타 원치 않는 이벤트 없이 작업을 수행하면서 여전히 실행 중이고 병렬로 실행되는 프로그램이나 애플리케이션 간에 전환할 수 있는 기능을 의미한다. 컴퓨터 부품을 온 더 플라이로 전환한다는 것은 컴퓨터가 여전히 실행 중인 동안 컴퓨터 부품을 교체하는 것을 의미한다. 또한 프로그래밍에서 프로그램이 여전히 실행 중인 동안 프로그램을 변경하는 것을 설명하는 데 사용될 수도 있다. 레스토랑 및 기타 음식 준비와 관련된 장소에서 이 용어는 주문을 즉시 처리해야 함을 나타내는 데 사용된다.
구어적 용법.
구어적으로 "온 더 플라이"는 필요할 때 만들어지는 것을 의미한다. 이 구문은 다음을 의미하는 데 사용된다.
자동차 용법.
자동차 산업에서 이 용어는 차량이 엔진에 의해 구동되고 움직이는 동안 특정 작업을 수행하는 상황을 나타낸다. 4륜구동 차량과 관련하여 이 용어는 차량이 기어를 넣고 움직이는 동안 2륜 구동에서 4륜 구동으로 전환할 수 있는 기능을 설명한다. 일부 컨버터블 모델에서는 지붕을 온 더 플라이로 전기로 접을 수 있지만, 다른 경우에는 자동차를 멈춰야 한다.
수확기에서는 최신 모니터링 시스템을 통해 운전자는 곡물의 품질을 추적하면서 수확이 진행됨에 따라 회전자 속도를 온 더 플라이로 조정할 수 있다.
컴퓨터 용법.
멀티태스킹 컴퓨팅에서 운영 체제는 여러 프로그램을 처리할 수 있다. 네이티브 애플리케이션이든 에뮬레이트된 소프트웨어든 모두 같은 장치에서 동시에 독립적으로, 병렬로 실행되며, 분리되거나 공유된 리소스 및 데이터를 사용하여 작업을 개별적으로 또는 함께 수행한다. 사용자는 시간 낭비나 성능 저하 없이 이러한 프로그램이나 그룹 간에 온 더 플라이로 전환하여 얻은 효과를 사용하거나 목적을 감독할 수 있다. GUI를 사용하는 운영 체제에서는 특정 소프트웨어의 활성 창(또는 유사한 역할을 하는 객체)에서 다른 소프트웨어의 다른 창으로 전환하여 이 작업을 수행하는 경우가 매우 많다.
컴퓨터는 온 더 플라이로 결과를 계산하거나 이전에 저장된 결과를 검색할 수 있다.
이는 이동식 미디어(CD-ROM, DVD 등)를 중간 매체(하드 디스크)에 먼저 저장하지 않고 직접 복사하는 것을 의미할 수 있다. 예를 들어, CD-ROM 드라이브에서 CD-라이터 드라이브로 CD-ROM을 복사하는 것이다. 복사 프로세스는 각 데이터 블록을 검색하고 즉시 대상으로 기록하여 작업 메모리에 다음 데이터 블록을 검색할 공간을 확보해야 한다.
암호화된 데이터 저장에 사용될 때, 데이터 스트림은 기록될 때 자동으로 암호화되고 다시 읽을 때 다시 해독되어 소프트웨어에 투명하게 적용된다. 약어 OTFE가 일반적으로 사용된다.
온 더 플라이 프로그래밍은 프로그램을 중지하지 않고 수정하는 기술이다.
유사한 개념인 핫 스와핑은 컴퓨터 하드웨어의 온 더 플라이 교체를 의미한다.
온 더 플라이 컴퓨팅.
온 더 플라이 컴퓨팅(OTF 컴퓨팅)은 사용자의 필요에 맞게 소프트웨어를 자동화하고 맞춤화하는 것이다. 요구 사항 사양에 따라 이 소프트웨어는 기본 구성 요소, 즉 기본 서비스로 구성되며, 이러한 기본 구성 요소의 사용자 지정 설정이 이루어진다. 따라서 요청된 서비스는 사용자의 요청에 따라서만 컴파일된 다음, 특별히 설계된 데이터 센터에서 실행되어 사용자가 (온 더 플라이로) 생성된 서비스의 기능에 액세스할 수 있도록 한다.
레스토랑 용법.
레스토랑, 카페, 연회장 등 음식 준비와 관련된 장소에서 이 용어는 주문을 즉시 처리해야 함을 나타내는 데 사용된다. 이는 이전에 제공된 요리가 먹을 수 없거나, 웨이터가 실수를 했거나 지연되었거나, 손님이 즉시 떠나야 하는 경우에 자주 발생한다.
스포츠 용법.
아이스하키에서 퍽이 경기 중에 있을 때 팀이 라인 변경(선수 교체)을 하는 것은 합법적이고 흔한 일이다. 이러한 라인 변경은 "온 더 플라이"로 이루어진다고 한다.
컴퓨터 과학에서 2–3 트리는 모든 자식 노드(내부 노드)가 두 개의 자식(2-노드)과 하나의 데이터 요소 또는 세 개의 자식(3-노드)과 두 개의 데이터 요소를 가지는 트리 자료 구조이다. 2–3 트리는 3차 B 트리이다. 트리의 바깥쪽에 있는 노드(리프 노드)는 자식이 없고 하나 또는 두 개의 데이터 요소를 가진다. 2–3 트리는 1970년 존 홉크로프트가 발명했다.
2–3 트리는 균형이 맞춰져 있어야 하는데, 이는 각 리프가 같은 레벨에 있다는 것을 의미한다. 따라서 노드의 각 오른쪽, 중앙, 왼쪽 서브트리는 같거나 거의 같은 양의 데이터를 포함한다.
내부 노드에 데이터 요소가 하나 있고 두 개의 자식이 있으면 이를 2-노드라고 한다.
내부 노드에 데이터 요소가 두 개 있고 세 개의 자식이 있으면 이를 3-노드라고 한다.
데이터 요소가 세 개인 4-노드는 트리를 조작하는 동안 일시적으로 생성될 수 있지만, 트리 내에 영구적으로 저장되지는 않는다.
가 2–3 트리인 경우는 다음 문장 중 하나만 참일 때이다:
2–3 트리에서 항목을 탐색하는 것은 이진 탐색 트리에서 항목을 탐색하는 것과 유사하다. 각 노드의 데이터 요소가 정렬되어 있으므로, 탐색 함수는 올바른 서브트리와 결국 항목을 포함하는 올바른 노드로 향하게 된다.
삽입은 트리의 균형 속성을 유지한다.
2-노드에 삽입할 때, 새 키는 적절한 순서로 2-노드에 추가된다.
3-노드에 삽입할 때는 3-노드의 위치에 따라 더 많은 작업이 필요할 수 있다. 트리가 3-노드로만 구성되어 있다면, 노드는 적절한 키와 자식을 가진 세 개의 2-노드로 분할된다.
대상 노드가 부모가 2-노드인 3-노드인 경우, 키는 3-노드에 삽입되어 임시 4-노드를 생성한다. 그림에서 키 10은 6과 9를 가진 2-노드에 삽입된다. 중간 키는 9이며, 부모 2-노드로 승격된다. 이렇게 되면 6과 10의 3-노드가 남게 되며, 이는 부모 3-노드의 자식으로 유지되는 두 개의 2-노드로 분할된다.
대상 노드가 3-노드이고 부모도 3-노드인 경우, 임시 4-노드가 생성된 다음 위와 같이 분할된다. 이 과정은 루트까지 트리 위로 계속된다. 루트를 분할해야 하는 경우, 단일 3-노드의 과정이 따른다: 임시 4-노드 루트는 세 개의 2-노드로 분할되며, 그중 하나가 루트로 간주된다. 이 연산은 트리의 높이를 하나 증가시킨다.
비-리프 노드에서 키를 삭제하는 것은 즉각적인 선행자 또는 후속자로 대체한 다음 리프 노드에서 선행자 또는 후속자를 삭제함으로써 수행할 수 있다. 리프 노드에서 키를 삭제하는 것은 리프가 3-노드인 경우 쉽다. 그렇지 않은 경우, 임시 1-노드를 생성해야 할 수 있으며, 이는 트리를 재구성하여 흡수되거나, 삽입의 경우 임시 4-노드처럼 흡수되기 전에 반복적으로 위로 이동해야 할 수 있다. 또는 하향식과 상향식을 모두 사용하는 알고리즘을 사용할 수 있는데, 이는 내려가는 길에 임시 4-노드를 생성하고 다시 올라오면서 파괴하는 방식이다. 삭제 방법은 참조에서 더 자세히 설명한다.
병렬 연산.
2–3 트리는 레드-블랙 트리와 구조가 유사하므로, 레드-블랙 트리를 위한 병렬 알고리즘도 2–3 트리에 적용할 수 있다.
컴퓨터 과학에서 2–3–4 트리 (또는 2–4 트리)는 사전을 구현하는 데 사용할 수 있는 자가 균형 자료 구조이다. 이 숫자는 자식 노드가 있는 모든 노드 (내부 노드)가 두 개, 세 개 또는 네 개의 자식 노드를 갖는 트리를 의미한다.
2–3–4 트리는 차수 4의 B 트리이다. 일반적인 B 트리와 마찬가지로, O(log n) 시간 내에 검색, 삽입 및 삭제를 수행할 수 있다. 2–3–4 트리의 한 가지 특징은 모든 외부 노드가 동일한 깊이에 있다는 것이다.
2–3–4 트리는 레드 링크(즉, 빨간색 자식에 대한 링크)를 3-노드 및 4-노드의 내부 링크로 해석함으로써 레드-블랙 트리와 밀접하게 관련되어 있지만, 이 대응 관계는 일대일이 아니다. 왼쪽 기울어진 레드-블랙 트리는 단일 빨간색 오른쪽 자식을 가진 노드를 금지함으로써 레드-블랙 트리를 제한하며, 이는 왼쪽 기울어진 레드-블랙 트리와 2–3–4 트리 사이에 일대일 대응을 이룬다.
값을 삽입하려면 2–3–4 트리의 루트에서 시작한다.
2–3–4 트리에 "25" 값을 삽입하려면:
요소를 삭제하는 가장 간단한 방법은 요소를 그대로 두고 "삭제됨"으로 표시하여 이전 알고리즘이 삭제된 요소를 무시하도록 조정하는 것이다. 삭제된 요소는 나중에 삽입을 수행할 때 덮어쓰기하여 재사용할 수 있다. 그러나 이 방법의 단점은 트리의 크기가 줄어들지 않는다는 것이다. 트리의 요소 중 상당 부분이 삭제되면 트리는 현재 저장된 요소의 크기보다 훨씬 커지고 다른 작업의 성능이 삭제된 요소의 영향을 받아 불리해진다.
이것이 바람직하지 않은 경우, 2–3–4 트리에서 값을 제거하기 위해 다음 알고리즘을 따를 수 있다.
제거하려는 리프로 가는 도중에 2-노드(루트 노드 제외)가 발견되면 다음 조정을 수행한다.
찾는 값에 도달하면 리프 노드에 1개 이상의 키가 있음을 확인했으므로 이제 제거된 항목의 위치에 문제없이 배치할 수 있다.
2–3–4 트리에서 삭제는 전송 및 합병이 상수 시간(O(1))으로 실행된다고 가정할 때 O(log n)이다.
2–3–4 트리는 레드-블랙 트리와 구조가 유사하므로, 레드-블랙 트리에 대한 병렬 알고리즘도 2–3–4 트리에 적용될 수 있다.
컴퓨터 과학에서 스케이프고트 트리(Scapegoat tree)는 1989년 아르네 안데르손이, 그리고 1993년 이갈 갈페린과 로널드 L. 리베스트가 다시 발명한 자가 균형 이진 탐색 트리이다. 이 트리는 최악의 경우 formula_1 탐색 시간(n은 엔트리 개수)과 formula_2의 분할 상환 삽입 및 삭제 시간을 제공한다.
최악의 경우 formula_2 탐색 시간을 제공하는 다른 대부분의 자가 균형 이진 탐색 트리와 달리, 스케이프고트 트리는 일반적인 이진 탐색 트리에 비해 노드당 추가 메모리 오버헤드가 없다: 키와 값 외에, 노드는 자식 노드에 대한 두 개의 포인터만 저장한다. 이는 스케이프고트 트리를 구현하기 쉽게 만들고, 데이터 구조 정렬 덕분에 노드 오버헤드를 최대 3분의 1까지 줄일 수 있다.
대부분의 균형 트리 알고리즘에서 사용되는 작고 점진적인 재균형 작업 대신, 스케이프고트 트리는 드물지만 비용이 많이 드는 "희생양"을 선택하여 희생양을 뿌리로 하는 서브트리를 완전한 이진 트리로 완전히 재구성한다. 따라서 스케이프고트 트리는 최악의 경우 formula_4의 갱신 성능을 가진다.
이진 탐색 트리는 노드의 절반이 루트의 왼쪽에 있고 절반이 오른쪽에 있으면 무게 균형이 잡혀 있다고 말한다.
알파-무게 균형 노드는 완화된 무게 균형 기준을 충족하는 것으로 정의된다:
여기서 size는 재귀적으로 정의될 수 있다:
함수 size(node) 는
만약 node = nil 이면
반환 0
반환 size(node-&gt;left) + size(node-&gt;right) + 1
함수 종료
심지어 퇴화된 트리(연결 리스트)도 α=1이면 이 조건을 만족하지만, α=0.5이면 거의 완전 이진 트리만 일치한다.
알파-무게 균형 이진 탐색 트리는 또한 알파-높이 균형이어야 한다. 즉,
height(tree) ≤ floor(log1/α(size(tree)))
대우에 의해, 알파-높이 균형이 아닌 트리는 알파-무게 균형이 아니다.
스케이프고트 트리는 항상 알파-무게 균형을 유지한다고 보장되지는 않지만, 항상 느슨하게 알파-높이 균형을 유지한다. 즉,
height(scapegoat tree) ≤ floor(log1/α(size(tree))) + 1.
이 높이 균형 조건의 위반은 삽입 시점에 감지될 수 있으며, 이는 무게 균형 조건의 위반이 존재해야 함을 의미한다.
이것은 스케이프고트 트리를 레드-블랙 트리와 유사하게 만들며, 둘 다 높이에 대한 제약이 있다. 그러나 회전(또는 스케이프고트 트리의 경우, 재균형)이 발생하는 위치를 결정하는 구현 방식에서는 크게 다르다. 레드-블랙 트리는 각 노드에 추가 '색상' 정보를 저장하여 위치를 결정하는 반면, 스케이프고트 트리는 알파-무게 균형이 아닌 희생양을 찾아 재균형 작업을 수행한다. 이는 AVL 트리와 느슨하게 유사하며, 실제 회전은 노드의 '균형'에 따라 달라지지만, 균형을 결정하는 방식은 크게 다르다. AVL 트리는 모든 삽입/삭제 시 균형 값을 확인하므로 일반적으로 각 노드에 저장되지만, 스케이프고트 트리는 필요할 때만 계산할 수 있으며, 이는 희생양을 찾아야 할 때만 해당된다.
다른 대부분의 자가 균형 탐색 트리와 달리, 스케이프고트 트리는 균형에 있어 완전히 유연하다. 이들은 0.5 &lt; α &lt; 1인 모든 α 값을 지원한다. 높은 α 값은 재균형을 적게 발생시켜 삽입을 빠르게 하지만, 탐색과 삭제는 느려지며, 낮은 α 값은 그 반대이다. 따라서 실제 응용에서는 이러한 작업이 얼마나 자주 수행되어야 하는지에 따라 α 값을 선택할 수 있다.
탐색은 표준 이진 탐색 트리에서 수정되지 않았으며, 최악의 경우 시간은 formula_2이다. 이는 최악의 경우 시간이 formula_4인 스플레이 트리와 대조된다. 다른 자가 균형 이진 탐색 트리에 비해 노드 메모리 오버헤드가 줄어들어 참조 국부성 및 캐싱을 더욱 향상시킬 수 있다.
삽입은 불균형 이진 탐색 트리와 동일한 기본 아이디어로 구현되지만, 몇 가지 중요한 변경 사항이 있다.
삽입 지점을 찾을 때, 새 노드의 깊이도 기록해야 한다. 이는 탐색의 각 반복 중에 증가하는 간단한 카운터를 통해 구현되며, 루트와 삽입된 노드 사이의 에지 수를 효과적으로 계산한다. 이 노드가 알파-높이 균형 속성(위에서 정의됨)을 위반하면 재균형이 필요하다.
재균형을 위해 희생양을 루트로 하는 전체 서브트리가 균형화 작업을 거친다. 희생양은 삽입된 노드의 조상 중에서 알파-무게 균형이 아닌 노드로 정의된다. 이러한 조상은 항상 하나 이상 존재한다. 그 중 하나를 재균형하면 알파-높이 균형 속성이 복원된다.
희생양을 찾는 한 가지 방법은 새 노드에서 루트로 다시 올라가서 알파-무게 균형이 아닌 첫 번째 노드를 선택하는 것이다.
루트로 다시 올라가려면 스택에 할당되거나 부모 포인터로 사용되는 formula_2의 저장 공간이 필요하다. 이는 각 자식을 내려갈 때 부모를 가리키게 하고, 다시 올라갈 때 수정함으로써 실제로 피할 수 있다.
잠재적인 노드가 유효한 희생양인지 확인하려면 해당 노드의 알파-무게 균형 속성을 확인해야 한다. 이를 위해 정의로 돌아갈 수 있다:
그러나 세 가지 크기 중 두 가지를 이미 알고 있으므로 세 번째만 계산하면 된다는 것을 깨달으면 큰 최적화를 할 수 있다.
이를 시연하기 위해 다음 예제를 고려해보자. 루트로 다시 올라간다고 가정하면:
그러나:
이 경우는 다음과 같이 단순화된다:
여기서 x = 이 노드, x + 1 = 부모이며 size(sibling)이 실제로 필요한 유일한 함수 호출이다.
희생양을 찾으면 희생양을 루트로 하는 서브트리는 완전히 균형 잡힌 상태로 재구성된다. 이는 서브트리의 노드를 순회하여 정렬된 순서로 값을 찾고 재귀적으로 중앙값을 서브트리의 루트로 선택함으로써 formula_4 시간 안에 수행할 수 있다.
재균형 작업은 formula_4 시간(서브트리 노드 수에 따라 달라짐)이 걸리므로, 삽입은 최악의 경우 formula_4 시간이 걸린다. 그러나 이러한 최악의 시나리오가 분산되어 있으므로 삽입은 formula_2의 분할 상환 시간이 걸린다.
삽입 비용 증명 스케치.
노드 v의 불균형(Imbalance)을 왼쪽 노드와 오른쪽 노드의 크기 차이의 절댓값에서 1을 뺀 값 또는 0 중 큰 값으로 정의한다. 다시 말해:
v를 뿌리로 하는 서브트리를 재구성한 직후, I(v) = 0이다.
보조 정리: v를 뿌리로 하는 서브트리를 재구성하기 직전,
보조 정리의 증명:
formula_15가 재구성 직후 서브트리의 루트라고 하자. formula_16이다. 만약 formula_17개의 퇴화 삽입(즉, 삽입된 각 노드가 높이를 1씩 증가시키는 경우)이 있다면,
formula_19 이고
formula_20이다.
재구성 전에 formula_21이므로, formula_22를 뿌리로 하는 서브트리에 formula_23개의 삽입이 있었고, 이 삽입들은 재구성으로 이어지지 않았다. 이 삽입들은 각각 formula_2 시간에 수행될 수 있다. 재구성을 유발하는 마지막 삽입 비용은 formula_25이다. 총합 분석을 사용하면 삽입의 분할 상환 비용이 formula_2이라는 것이 분명해진다:
스케이프고트 트리는 삭제가 삽입보다 쉽다는 점에서 특이하다. 삭제를 가능하게 하려면 스케이프고트 트리는 트리 데이터 구조와 함께 추가 값을 저장해야 한다. 이 속성을 MaxNodeCount라고 부르며, 이는 단순히 도달한 최고 NodeCount를 나타낸다. 전체 트리가 재균형될 때마다 NodeCount로 설정되며, 삽입 후에는 max(MaxNodeCount, NodeCount)로 설정된다.
삭제를 수행하려면 단순 이진 탐색 트리에서와 같이 노드를 제거하면 되지만,
NodeCount ≤ α*MaxNodeCount
이면 루트를 중심으로 전체 트리를 재균형하고, MaxNodeCount를 NodeCount로 설정하는 것을 잊지 말아야 한다.
이는 삭제에 최악의 경우 formula_4 시간을 제공하며, 분할 상환 시간은 formula_2이다.
삭제 비용 증명 스케치.
스케이프고트 트리가 formula_30개의 요소를 가지고 방금 재구성되었다고 가정해 보자(다시 말해, 완전 이진 트리이다). 트리가 재구성되기 전에 최대 formula_31개의 삭제가 수행될 수 있다. 이 삭제들은 각각 formula_2 시간이 걸린다(요소를 찾고 삭제된 것으로 표시하는 데 걸리는 시간). formula_33번째 삭제는 트리가 재구성되도록 하고 formula_34(또는 그냥 formula_4) 시간이 걸린다. 총합 분석을 사용하면 삭제의 분할 상환 비용이 formula_2이라는 것이 분명해진다:
컴퓨터 과학에서 트립(Treap)과 확률적 이진 탐색 트리는 순서 있는 키의 동적 집합을 유지하고 키 간의 이진 검색 알고리즘을 허용하는 서로 밀접하게 관련된 두 가지 형태의 이진 탐색 트리 자료 구조이다. 어떤 키 삽입 및 삭제 시퀀스 후에도 트리의 모양은 무작위 이진 트리와 동일한 확률 분포를 가진 무작위 변수이다. 특히, 높은 확률로 높이는 키 수의 로그에 비례하므로 각 검색, 삽입 또는 삭제 작업은 로그 시간 안에 수행된다.
트립은 1989년 라이문트 자이델과 세실리아 R. 아라곤에 의해 처음 기술되었다. 그 이름은 혼성어로 트리와 힙을 합친 것이다.
이는 각 키에 (무작위로 선택된) 숫자 우선순위가 부여된 카르테시안 트리이다. 다른 이진 탐색 트리와 마찬가지로 노드의 중위 순회 순서는 키의 정렬된 순서와 같다. 트리의 구조는 힙 순서를 유지해야 한다는 요구 사항에 의해 결정된다. 즉, 모든 비리프 노드의 우선순위는 자식의 우선순위보다 크거나 같아야 한다. 따라서 일반적으로 카르테시안 트리와 마찬가지로 루트 노드는 최대 우선순위 노드이며, 왼쪽 및 오른쪽 서브트리는 해당 노드의 왼쪽과 오른쪽에 있는 정렬된 순서의 서브시퀀스에서 동일한 방식으로 형성된다.
트립을 설명하는 동등한 방법은 가장 높은 우선순위부터 노드를 이진 탐색 트리에 삽입하여 재조정 없이 형성될 수 있다는 것이다. 따라서 우선순위가 독립적인 무작위 숫자(두 노드가 동일한 우선순위를 가질 가능성이 거의 없도록 충분히 큰 우선순위 공간에서 분포된)라면 트립의 모양은 무작위 이진 탐색 트리의 모양과 동일한 확률 분포를 갖는다. 무작위 이진 탐색 트리는 무작위로 선택된 삽입 순서로 재조정 없이 노드를 삽입하여 형성된 탐색 트리이다. 무작위 이진 탐색 트리는 높은 확률로 로그 높이를 갖는 것으로 알려져 있으므로 트립도 마찬가지이다. 이는 퀵 정렬의 이진 탐색 트리 논증과 유사하며 퀵 정렬이 예상 formula_1 시간에 실행된다. 이진 탐색 트리가 정렬의 동적 문제 버전의 해법이라면, 트립은 우선순위가 피벗 선택을 안내하는 동적 퀵 정렬에 특히 해당한다.
아라곤과 자이델은 또한 자주 접근되는 노드에 더 높은 우선순위를 부여하는 것을 제안한다. 예를 들어, 각 접근 시 무작위 숫자를 선택하고 이전 우선순위보다 높으면 해당 숫자로 노드의 우선순위를 대체하는 프로세스를 통해서이다. 이 수정은 트리가 무작위 형태를 잃게 할 것이다. 대신, 자주 접근되는 노드는 트리 루트 근처에 있을 가능성이 더 높아져 해당 노드에 대한 검색이 더 빨라질 것이다.
나오르와 니심은 공개 키 암호 시스템에서 인증 인증서를 유지하는 응용 분야를 설명한다.
기본 연산.
트립은 다음 기본 연산을 지원한다:
대량 연산.
단일 요소 삽입, 삭제 및 조회 작업 외에도 트립에서 여러 빠른 "대량" 작업이 정의되었다: 합집합, 교집합 및 집합 차이. 이들은 두 가지 도우미 작업인 분할(split) 및 결합(join)에 의존한다.
결합 알고리즘은 다음과 같다:
함수 join(L, k, R)
만약 prior(k, k(L)) 그리고 prior(k, k(R)) 이면 반환 Node(L, k, R)
만약 prior(k(L), k(R)) 이면 반환 Node(left(L), k(L), join(right(L), k, R))
반환 Node(join(L, k, left(R)), k(R), right(R))
분할 알고리즘은 다음과 같다:
함수 split(T, k)
만약 (T = nil) 이면 반환 (nil, false, nil)
(L, (m, c), R) = expose(T)
만약 (k = m) 이면 반환 (L, true, R)
만약 (k &lt; m)
(L', b, R') = split(L, k)
반환 (L', b, join(R', m, R))
만약 (k &gt; m)
(L', b, R') = split(R, k)
반환 (join(L, m, L'), b, R'))
집합 와 를 나타내는 두 트립 과 의 합집합은 를 나타내는 트립 이다. 다음 재귀 알고리즘은 합집합을 계산한다.
함수 union(t1, t2):
만약 t1 = nil:
반환 t2
만약 t2 = nil:
반환 t1
만약 priority(t1) &lt; priority(t2):
교환 t1과 t2
t&lt;, t&gt; ← key(t1)에서 t2를 분할
반환 join(union(left(t1), t&lt;), key(t1),
union(right(t1), t&gt;))
여기서 분할은 두 개의 트리를 반환하는 것으로 가정한다: 하나는 입력 키보다 작은 키를 포함하고, 다른 하나는 더 큰 키를 포함한다. (이 알고리즘은 비파괴적이지만, 제자리 파괴적 버전도 존재한다.)
교집합 알고리즘도 유사하지만, join 도우미 루틴이 필요하다. 합집합, 교집합, 차집합 각각의 복잡성은 크기 과 을 가진 트립의 경우 일 때 이다. 또한, 합집합에 대한 재귀 호출은 서로 독립적이므로 병렬로 실행될 수 있다.
Split과 Union은 Join을 호출하지만 트립의 균형 기준을 직접 다루지 않는다. 이러한 구현은 일반적으로 "join-based" 구현이라고 불린다.
키의 해시 값이 우선순위로 사용되고, 구조적으로 동일한 노드가 이미 생성 시 병합된다면, 각 병합된 노드는 키 집합의 고유한 표현이 될 것이다. 주어진 키 집합을 나타내는 동시 루트 노드가 하나만 있을 수 있다면, 두 집합은 포인터 비교를 통해 동일한지 테스트할 수 있으며, 이는 상수 시간이다.
이 기술은 두 집합 간의 차이가 작을 때에도 병합 알고리즘을 빠르게 수행하도록 향상시키는 데 사용될 수 있다. 입력 집합이 동일하다면, 합집합 및 교집합 함수는 즉시 입력 집합 중 하나를 결과로 반환하며 중단할 수 있고, 차집합 함수는 빈 집합을 반환해야 한다.
를 대칭 차이의 크기라고 하자. 수정된 병합 알고리즘은 로도 제한된다.
확률적 이진 탐색 트리.
트립에 대한 아라곤과 자이델의 연구 이후 마르티네스와 로우라가 도입한 확률적 이진 탐색 트리는 동일한 노드를 동일한 무작위 트리 형태 분포로 저장하지만, 무작위 구조를 유지하기 위해 트리 노드 내에 다른 정보를 유지한다.
각 노드에 무작위 우선순위를 저장하는 대신, 확률적 이진 탐색 트리는 각 노드에 작은 정수(자신을 포함하여 자손의 수)를 저장한다. 이 숫자는 트리 회전 작업 중에 회전당 상수 추가 시간만으로 유지될 수 있다. n개의 노드를 이미 가진 트리에 키 x를 삽입해야 할 때, 삽입 알고리즘은 1/(n + 1)의 확률로 x를 트리의 새 루트로 배치하고, 그렇지 않으면 (키가 루트보다 작거나 큰지에 따라) x를 왼쪽 또는 오른쪽 서브트리에 삽입하기 위해 삽입 프로시저를 재귀적으로 호출한다. 자손의 수는 알고리즘에 의해 각 단계에서 무작위 선택에 필요한 확률을 계산하는 데 사용된다. 서브트리의 루트에 x를 배치하는 것은 트립에서와 같이 리프에 삽입한 다음 위로 회전시키거나, 마르티네스와 로우라가 설명한 대체 알고리즘으로 서브트리를 두 조각으로 분할하여 새 노드의 왼쪽 및 오른쪽 자식으로 사용하는 방식으로 수행할 수 있다.
확률적 이진 탐색 트리의 삭제 프로시저는 삽입 프로시저와 동일한 노드당 정보를 사용하지만, 삽입 프로시저와 달리 삭제된 노드의 왼쪽 및 오른쪽 자식에서 내려오는 두 서브트리를 하나의 트리로 결합하는 데 평균적으로 O(1) 무작위 결정만 필요하다. 이는 결합할 서브트리가 평균적으로 Θ(log n) 깊이에 있기 때문이다. 크기 n과 m의 두 트리를 결합하는 데는 평균적으로 Θ(log(n+m)) 무작위 결정이 필요하다. 삭제할 노드의 왼쪽 또는 오른쪽 서브트리가 비어 있으면 결합 작업은 사소하다. 그렇지 않으면 삭제된 노드의 왼쪽 또는 오른쪽 자식이 해당 자손 수에 비례하는 확률로 새 서브트리 루트로 선택되고, 결합은 재귀적으로 진행된다.
확률적 이진 트리의 노드당 저장되는 정보는 트립보다 간단하지만(고정밀 난수 대신 작은 정수), 난수 생성기에 더 많은 호출을 한다(삽입당 한 번의 호출 대신 삽입 또는 삭제당 O(log n) 호출). 또한 삽입 프로시저는 노드당 자손 수를 업데이트해야 하므로 약간 더 복잡하다. 사소한 기술적 차이점은 트립에서 충돌(두 키가 동일한 우선순위를 얻는 것)의 작은 확률이 있고, 두 경우 모두 실제 난수 생성기와 디지털 컴퓨터에서 일반적으로 사용되는 유사 난수 생성기 사이에 통계적 차이가 있을 것이다. 그러나 어떤 경우에도 알고리즘 설계에 사용된 완벽한 무작위 선택의 이론적 모델과 실제 난수 생성기의 기능 사이의 차이는 미미하다.
트립과 무작위 이진 탐색 트리는 각 업데이트 후 트리의 형태가 동일한 무작위 분포를 가지지만, 일련의 삽입 및 삭제 작업에 의해 이 두 자료 구조가 수행한 트리의 수정 이력은 다를 수 있다. 예를 들어, 트립에서 숫자 1, 2, 3이 순서대로 1, 3, 2로 삽입된 다음 숫자 2가 삭제되면 남아 있는 두 노드는 중간 숫자가 삽입되기 전과 동일한 부모-자식 관계를 가질 것이다. 무작위 이진 탐색 트리에서는 삭제 후 트리는 두 노드에 대한 두 가지 가능한 트리 중 어느 하나가 될 가능성이 동일하며, 중간 숫자가 삽입되기 전 트리가 어떻게 생겼는지와는 독립적이다.
암시적 트립.
암시적 트립은 일반 트립의 간단한 변형으로, formula_2 시간 내에 다음 연산을 지원하는 동적 배열로 볼 수 있다:
암시적 트립의 아이디어는 배열 인덱스를 키로 사용하지만 명시적으로 저장하지 않는 것이다. 그렇지 않으면 업데이트(삽입/삭제)로 인해 트리의 formula_5 노드에서 키가 변경될 수 있다.
노드 T의 키 값(암시적 키)은 해당 노드보다 작은 노드의 수에 1을 더한 값이다. 이러한 노드는 왼쪽 서브트리뿐만 아니라, T가 P의 오른쪽 서브트리에 있는 경우 P의 왼쪽 서브트리에도 존재할 수 있음을 유의하라.
따라서 트리를 내려가면서 모든 노드의 합을 누적하여 연산을 수행할 때 현재 노드의 암시적 키를 빠르게 계산할 수 있다. 이 합은 왼쪽 서브트리를 방문할 때는 변하지 않지만, 오른쪽 서브트리를 방문할 때는 formula_6만큼 증가할 것임을 유의하라.
암시적 트립의 join 알고리즘은 다음과 같다:
void join (pitem &amp; t, pitem l, pitem r) {
if (!l || !r)
t = l ? l : r;
else if (l-&gt;prior &gt; r-&gt;prior)
join (l-&gt;r, l-&gt;r, r), t = l;
join (r-&gt;l, l, r-&gt;l), t = r;
upd_cnt (t);
암시적 트립의 split 알고리즘은 다음과 같다:
void split (pitem t, pitem &amp; l, pitem &amp; r, int key, int add = 0) {
if (!t)
return void( l = r = 0 );
int cur_key = add + cnt(t-&gt;l); //implicit key
if (key &lt;= cur_key)
split (t-&gt;l, l, t-&gt;l, key, add), r = t;
split (t-&gt;r, t-&gt;r, r, key, add + 1 + cnt(t-&gt;l)), l = t;
요소 삽입.
요소를 pos 위치에 삽입하려면 split 함수를 호출하여 배열을 [0...pos-1]과 [pos..sz] 두 개의 하위 섹션으로 나누고 두 개의 트리 formula_7과 formula_8를 얻는다. 그런 다음 join 함수를 호출하여 formula_7을 새 노드와 병합한다. 마지막으로 join 함수를 호출하여 formula_7과 formula_8를 병합한다.
요소 삭제.
삭제할 요소를 찾고 해당 자식 L과 R에 대해 조인을 수행한다. 그런 다음 삭제할 요소를 조인 연산의 결과로 생성된 트리로 바꾼다.
주어진 범위에서 합계, 최소 또는 최대 찾기.
이 계산을 수행하려면 다음과 같이 진행한다:
주어진 범위에서 덧셈/색칠.
이 작업을 수행하려면 다음과 같이 진행한다:
주어진 범위에서 뒤집기.
주어진 노드의 서브트리를 뒤집어야 함을 보여주기 위해 각 노드에 추가 부울 필드 R을 생성하고 값을 true로 설정한다. 이 변경 사항을 전파하려면 노드의 자식을 교환하고 모든 자식에 대해 R을 true로 설정한다.
판 엠데 보아스 트리(van Emde Boas tree, ), vEB 트리 또는 판 엠데 보아스 우선순위 큐라고도 알려진 이 자료 구조는 -비트 정수 키를 사용하는 연관 배열을 구현하는 트리 자료 구조이다. 이 자료 구조는 네덜란드 컴퓨터 과학자 피터 판 엠데 보아스가 이끄는 팀에 의해 1975년에 발명되었다. 모든 연산은 시간(m 비트 연산이 상수 시간에 수행될 수 있다고 가정) 또는 동등하게 formula_1 시간 안에 수행되며, 여기서 formula_2은 트리에 저장될 수 있는 가장 큰 원소이다. 매개변수 formula_3은 트리에 저장된 실제 원소의 수와 혼동되어서는 안 된다. 다른 트리 자료 구조의 성능은 종종 이 매개변수로 측정되기 때문이다.
표준 vEB 트리는 formula_4의 비효율적인 공간 효율성을 가진다. 예를 들어, 32비트 정수를 저장할 때(즉, formula_5일 때) formula_6 비트의 저장 공간이 필요하다. 이를 해결하기 위해 vEB 트리를 수정하여 formula_7 공간을 달성하거나, 동등한 점근 시간 효율성과 formula_8 공간 효율성(여기서 formula_9은 저장된 원소의 수)을 가진 유사한 자료 구조를 사용할 수 있다.
지원되는 연산.
vEB는 일반적인 연관 배열 연산과 FindNext 및 FindPrevious라는 두 가지 추가 순서 연산을 포함하는 정렬된 연관 배열의 연산을 지원한다:
vEB 트리는 또한 Minimum 및 Maximum 연산을 지원하며, 이는 각각 트리에 저장된 최소 및 최대 원소를 반환한다. 최소 및 최대 원소는 각 트리에 속성으로 저장되므로 이 둘 모두 formula_10 시간에 실행된다.
어떤 정수 formula_11에 대해 formula_12라고 하자. formula_2으로 정의하자. 유니버스 formula_14에 걸친 vEB 트리 는 길이 formula_15의 배열 을 저장하는 루트 노드를 가진다. 는 값 formula_16을 담당하는 vEB 트리 포인터이다. 또한 T는 두 값 및 와 보조 vEB 트리 를 저장한다.
데이터는 vEB 트리에 다음과 같이 저장된다: 현재 트리에 있는 가장 작은 값은 에 저장되고 가장 큰 값은 에 저장된다. 은 vEB 트리의 다른 곳에 저장되지 않는 반면 는 저장된다는 점에 유의한다. T가 비어 있다면 및 으로 간주한다. 다른 값 formula_17는 formula_18인 서브트리 에 저장된다. 보조 트리 는 어떤 자식이 비어 있지 않은지 추적하므로, 가 비어 있지 않은 경우에만 는 값 formula_19를 포함한다.
FindNext.
vEB 트리에서 원소 x의 후속자를 검색하는 연산 는 다음과 같이 진행된다: 만약 이면 검색이 완료되고, 답은 이다. 만약 이면 다음 원소가 존재하지 않으므로 M을 반환한다. 그렇지 않으면 formula_18라고 하자. 만약 이면, 검색 중인 값은 에 포함되어 있으므로 검색은 에서 재귀적으로 진행된다. 그렇지 않으면, 에서 값 i의 후속자를 검색한다. 이것은 x보다 큰 원소를 포함하는 첫 번째 서브트리의 인덱스 j를 제공한다. 그런 다음 알고리즘은 을 반환한다. 자식 레벨에서 발견된 원소는 전체 다음 원소를 형성하기 위해 상위 비트와 결합되어야 한다.
function FindNext(T, x)
if x &lt; T.min then
return T.min
if x ≥ T.max then // 다음 원소 없음
return M
i = floor(x/formula_15)
lo = x mod formula_15
if lo &lt; T.children[i].max then
return (formula_15 i) + FindNext(T.children[i], lo)
return (formula_15 j) + T.children[j].min
어떤 경우에도 알고리즘은 formula_10 작업을 수행한 다음 크기 formula_26 (m/2 비트 유니버스)의 유니버스에 걸친 서브트리에서 재귀를 수행할 수 있다는 점에 유의한다. 이는 실행 시간에 대해 formula_27의 재귀 관계를 제공하며, 이는 formula_28으로 해결된다.
vEB 트리 에 값 를 삽입하는 호출 는 다음과 같이 작동한다:
코드:
function Insert(T, x)
if T.min == x || T.max == x then // x는 이미 삽입됨
if T.min &gt; T.max then // T가 비어 있음
if x &gt; T.max then
i = floor(x / formula_15)
if T.children[i].min == T.children[i].max then
이 절차의 효율성에 대한 핵심은 빈 vEB 트리에 원소를 삽입하는 데 시간이 걸린다는 것이다. 따라서 알고리즘이 때로는 두 번의 재귀 호출을 하더라도, 이는 첫 번째 재귀 호출이 빈 서브트리에 있었을 때만 발생한다. 이는 이전과 동일한 실행 시간 재귀 관계인 을 제공한다.
vEB 트리에서 삭제는 가장 까다로운 연산 중 하나이다. vEB 트리 T에서 값 x를 삭제하는 호출 는 다음과 같이 작동한다:
function Delete(T, x)
if T.min == T.max == x then
if x == T.min then
hi = T.aux.min * formula_15
if T.children[i] is empty then
if x == T.max then
if T.aux is empty then
hi = T.aux.max * formula_15
다시 한번, 이 절차의 효율성은 단 하나의 원소만 포함하는 vEB 트리에서 삭제하는 데 상수 시간만 걸린다는 사실에 달려 있다. 특히, 두 번째 Delete 호출은 삭제 이전에 x가 에 유일한 원소였을 때만 실행된다.
이 정수라는 가정은 불필요하다. formula_35 및 formula_36 연산은 각각 의 상위 비트와 하위 비트를 취함으로써 대체될 수 있다. 기존의 어떤 기계에서든 이것은 나눗셈 또는 나머지 계산보다 더 효율적이다.
실제 구현에서, 특히 k 시프트 및 첫 번째 0 찾기 명령을 가진 기계에서는 이 워드 크기(또는 그 작은 배수)와 같아질 때 비트 배열로 전환함으로써 성능을 더욱 향상시킬 수 있다. 단일 워드에 대한 모든 연산은 상수 시간이므로 이는 점근적 성능에 영향을 미치지 않지만, 대부분의 포인터 저장 및 여러 포인터 역참조를 피하여 이 트릭으로 시간 및 공간에서 상당한 실질적인 절약을 달성한다.
vEB 트리의 최적화는 빈 서브트리를 폐기하는 것이다. 이는 vEB 트리가 많은 원소를 포함할 때 매우 컴팩트하게 만든다. 왜냐하면 어떤 것이 추가될 필요가 있을 때까지 서브트리가 생성되지 않기 때문이다. 초기에는 추가되는 각 원소가 약 개의 새로운 트리를 생성하며, 이들은 모두 합쳐서 약 개의 포인터를 포함한다. 트리가 성장함에 따라 더 많은 서브트리가 재사용되며, 특히 큰 서브트리가 그렇다.
위에서 설명한 구현은 포인터를 사용하며, 키 유니버스의 크기에 비례하는 총 공간을 차지한다. 이는 다음과 같이 볼 수 있다. 재귀 관계는 formula_37이다.
귀납법으로 임을 보일 수 있다.
유사한 구조.
vEB 트리의 공간 사용량은 키 유니버스의 큰 부분이 저장되지 않는 한 엄청난 오버헤드이다. 이것이 vEB 트리가 실제로 인기가 없는 이유 중 하나이다. 이 제한은 자식을 저장하는 데 사용되는 배열을 다른 자료 구조로 변경함으로써 해결될 수 있다. 한 가지 가능성은 각 레벨당 고정된 수의 비트만 사용하는 것으로, 이는 트라이 (컴퓨팅)로 이어진다. 또는 각 배열을 해시 테이블로 대체하여 공간을 로 줄일 수 있다(여기서 은 자료 구조에 저장된 원소의 수) 이 경우 자료 구조는 무작위화된다.
x-고속 트라이와 더 복잡한 y-고속 트라이는 vEB 트리와 유사한 업데이트 및 쿼리 시간을 가지며, 무작위 해시 테이블을 사용하여 사용되는 공간을 줄인다. x-고속 트라이는 공간을 사용하는 반면, y-고속 트라이는 공간을 사용한다.