양이온 큐의 재배치 순위

Question

양이온 큐 작업 here에 대해 읽고 있습니다.

이 링크의 하단에 그것이 이항 큐

1. deletemin 작업의

   구현으로 언급 루트의 모든 하위 트리를 찾을 수있는 능력이 필요합니다. 따라서 각 노드의 하위 노드를 사용할 수 있어야합니다 (예 : 연결된 목록)

2. deletemin을 사용하려면 하위 트리의 크기로 정렬해야합니다.
3. 우리는 머릿단을 쉽게 병합 할 수 있어야합니다. 두 개의 이항 트리가 같은 크기를 가진 경우에만 병합 될 수 있으므로 트리의 크기는 루트에 저장되어야합니다. 병합하는 동안 나무 중 하나가 다른 하나의 마지막 자식이되므로 각 노드의 마지막 자식을 추적해야합니다. ?

 
data | first |left | right |rank No. of | 
-------------------------------------------- 
     child |sibling |sibling| children 

이상으로하는 것은 저자가 하나 PLS 예와 함께 설명 할 수의 순위 번호 "무엇을 의미 하는가 : 사용하는 좋은 데이터 구조는 각각의 노드는 다음과 같은 형식의 어떤 원형 이중 연결리스트입니다

Answer 1

내가 이해하는 한, 우리는 rank을 저장하려고합니다. 이는 no. of childen과 동일합니다 (이러한 나무의 등급이 일반적으로 정의되는 방식입니다). 따라서 각 노드에 다음 :

,
• data 트리
• first의 요소를 나타내는 어린이의 연결리스트에 대한 포인터를 나타냅니다 (즉, 첫 번째 자식에 대한 포인터)
• left는 왼쪽 이웃
• right에 대한 포인터가 이항 트리

Answer 2

주 요구 사항 단순히 순위 올바른 이웃

rank에 대한 포인터입니다입니다 "두 이항 트리는 같은 크기를 가진 경우에만 병합 될 수 있으므로 트리의 크기는 루트에 저장되어야합니다."

"하위 트리 크기"필드 대신 "자식 수"필드를 넣은 것 같습니다. 이것은 혼란 스럽지만, 구현을 위해서는 서브 트리의 크기가 2^{children of #}이기 때문에 괜찮습니다. 따라서 하위 트리의 크기를 비교하는 대신 자식 수를 비교할 수 있습니다.