붉은 검은 나무로 변환 할 때 한 형태를 다른 양식으로 선택할 이유가 있습니까?

Question

표준 컨테이너가 맞지 않을 때 사용하기위한 링크 된 목록/이진 트리 방법의 라이브러리가 있습니다. 예를 들어 다른 유형의 노드가있을 때 또는 이진 트리에서 목록 및 다시 다시 변환해야 할 때. 붉은 블랙 트리 처리가 포함되어 있습니다.

방법 중 하나는 이중 연결 목록에서 완벽하게 균형 잡힌 간단한 바이너리 트리로 변환됩니다. O(n) 시간 (품목 수가 미리 알려진 경우). 알고리즘은 "접는"것으로 알려져 있습니다. 한 번 Dobbs 박사에 게시 된 이진 트리 재조정 알고리즘의 후반입니다. 단계는 기본적으로 ...

• 나무의 크기가 주어지면 왼쪽 및 오른쪽 하위 트리의 크기를 결정하십시오.

• 왼쪽 하위 트리에 대해 되풀이하십시오

• 루트로 사용하려면 목록에서 노드를 팝

• 오른쪽 하위 트리에 대해 되풀이하십시오

• 하위 트리를 루트에 연결하십시오

또한 붉은 검은 나무를 만드는 비슷한 방법이 있습니다. 원리는 동일하지만 재귀는 노드 높이를 추적합니다. 높이 제로 노드는 빨간색으로 생성되고 다른 모든 것은 검은 색입니다. 시작 높이 계산은 트리 크기에서 가장 높은 세트 비트를 기준으로하며 완벽하게 균형을 잡을 수 있도록 피해를 입습니다. (2^n)-1 크기의 트리에는 검은 색 노드 만 있습니다 (재귀는 높이가 높아집니다).

여기서 요점은 리프 레벨에 빨간 노드 만 있고 최대 절반의 노드는 빨간색이라는 것입니다.

문제는 이것이 유효한 빨간색 나무를 생성하는 간단한 방법이지만 유일한 옵션은 아닙니다. 완벽하게 균형 잡힌 나무에서 모든 잎이 빨간색을 피하는 것을 피하는 것은 임의의 선택이었습니다. 빨간색과 검은 색 노드의 번갈아 가면서 번갈아 가을 수 있습니다. 또는 완벽하게 균형을 잡는 하위 트리를 발견하고 (적색 노드가 필요한 경우) 모든 잎 대신 하위 트리를 빨간색으로 만드는 경우에도 적색 노드의 수를 크게 줄일 수 있습니다.

문제는 - 하나의 유효한 붉은 블랙 트리 형태를 다른 유효한 빨간 검은 나무 형태를 선택할 실용적인 이유가 있습니까?

이것은 순수한 호기심입니다. 나는 실용적인 이유가 없다는 것을 알고 있습니다. 그러나이 선택이 중요한 전문가 응용 프로그램을 아는 사람이 있습니까?

Answer 1

Pysicist의 방법을 사용하여 적색 블랙 트리를 수정하는 상각 비용의 표준 분석에서, 붉은 어린이가 0 또는 두 명의 붉은 어린이를 가진 검은 노드에는 하나의 긍정적 인 잠재력이 할당됩니다. 즉, 추가 작업이 필요할 수있는 나무에서 문제가있는 장소를 나타냅니다. 수행 할. 정확히 하나의 빨간 어린이가있는 빨간색 노드와 검은 색 노드에는 0의 잠재력이 할당됩니다.

따라서 수정 비용을 줄이려면 모든 검은 노드에게 빨간 아이에게 하나의 빨간 아이를 제공하십시오.

---

그만큼 이유 한 명의 빨간 아이가있는 검은 노드가 축복받는 이유는 중복 된 이진 숫자와 유사하게 가장 잘 설명됩니다. 먼저 붉은 블랙 트리를 이진 번호와 관련시키는 방법을 설명하고 하나의 빨간색 자식 노드가 왜 유용한 지 설명하겠습니다.

아시다시피, 붉은 검은 나무는 2-4 그루를 나타내는 방법이며, 뿌리에서 잎까지의 모든 간단한 경로는 길이가 같지만 노드의 2, 3 또는 4 명의 어린이가 있습니다. 2-4 트리에서 노드를 추가하거나 제거하기위한 가장 간단한 알고리즘은 중복 이진 번호.

중복 된 이진수는 ITH 숫자가 2를 나타내는 숫자입니다.^나, 표준 바이너리 숫자와 마찬가지로 ITH 숫자는 0, 1 일 수 있습니다. 또는 2. 주어진 숫자를 작성하는 여러 가지 방법이 있기 때문에 중복이라고합니다. 4_{12 월} 100 또는 20 또는 12를 쓸 수 있습니다.

중복 된 이진수에 하나를 추가하려면 가장 중요한 숫자를 증가시킵니다. 3 인 경우 1로 설정하고 다음으로 가장 유의 한 숫자를 증가시킵니다. 알고리즘은 0 또는 1에 직면 할 때 중단됩니다.

2-4 나무에 잎을 추가하려면 의도 한 부모에게 아이를 추가하십시오. 부모가 다섯 자녀가있는 경우, 두 개의 노드로 나누고 부모의 자녀를 낳습니다. 분할이 필요하지 않은 노드에 도달 할 때까지 계속하십시오. 따라서 뿌리를 향한 경로는 2 ~ 3 명의 자녀와 노드를 만날 때 정지합니다.

중복 된 이진수를 증가시키는 상각 비용을 결합하려면 물리학 자 방법을 사용하고 각 2 자리에 1의 잠재력을 할당하십시오. k 숫자에 닿는 xall은 K-1 전위를 방출하여 상각 된 비용을 제공합니다 (1).

이 분석은 표준 바이너리 수를 증가시키는 상각 비용과 유사하지만 표준 바이너리 수는 O (1) 상각 시간의 증분 및 감소를 모두 지원할 수 없습니다.^케이 -1. K 1 자리입니다. 증분 비용 θ (k). 그 뒤에 감소하면 쌍은 θ (k) 비용을 지불하고 그 숫자를 이전 상태로 다시 가져옵니다.

중복 바이너리는 1 자리 숫자가 증분 및 감소의 계단식 작업을 중단한다는 점에서 특별합니다. 2-4 트리는 삽입 및 삭제 모두의 계단식 작업을 중단하는 데 특별합니다.

붉은 검은 나무에서는 빨간 아이 한 노드는 2-4 트리의 3 노드를 나타냅니다. 이 노드는 하위 트리의 인서트 또는 삭제에 대해 특별하고 강력하므로 많은 업데이트를 볼 수있는 빨간색 검은 나무를 만들 때 선호해야합니다.

당신이 알면 삽입물 만 볼 수 있다는 것을 알고 있다면 두 명의 흑인 어린이가있는 노드를 선호합니다. 당신이 알고 있다면 당신이 삭제 만 볼 수 있다는 것을 알고 있다면, 두 명의 붉은 어린이가있는 노드를 선호합니다.

Answer 2

짧은 대답은 다음과 같습니다. 때에 따라 다르지.

기본적으로 모든 유효한 나무로는 충분합니다. 그러나 측면에서 상각 된 분석 - 장기적으로 가장 최적화 된 동작을 줄 가장 올바른 트리를 선택하고 싶을 수도 있습니다.

예를 들어 항상 유효한 트리를 선택하지만 균형 잡힌 작업이 많이 발생하기 쉬운 트리를 선택하면 상각 성능이 나빠질 수 있습니다. 명백한 예는 완전 검은 트리이며, 완벽하게 유효하지만 수정할 때 나쁜 성능을 제공합니다.

이것은 일반적으로 응용 프로그램 별이기 때문에 달라집니다.