[데이터 구조 와 알고리즘] 왼쪽 트 리 (더미) 의 실현

왼쪽 나 무 는 왼쪽 더미 라 고도 할 수 있다.나무 라 고 부 르 는 것 은 저장 구조 가 보통 이 진 트 리 를 사용 하기 때문에 특수 한 이 진 트 리 라 고 볼 수 있다.더미 라 고 부 르 는 것 은 논리 적 구조 상 통합 가능 한 더미 에 속 하기 때문이다.사실 데이터 구조 에서 가장 번영 하 는 두 가지 가 바로 밸 런 스 트 리 이다. 병합 가능 더미.고급 나무 구조의 핵심 은 나 무 를 균형 에 이 르 게 하 는 방법 을 중심 으로 전개 되 는데 고급 나무 구조의 핵심 은 어떻게 효과적으로 합병 하 느 냐 하 는 것 이다.
        여기 서 먼저 병합 가능 한 아주 좋 은 데이터 구 조 를 소개 합 니 다. 왼쪽 더 미 를 소개 합 니 다.사람들 이 익숙 하거나 자주 듣 는 무 더 기 는 주로 (이 진) 더미, 왼쪽 더미, 경사 더미, 두 가지 더미, 피 보 나치 더미 가 있다.그 중에서 이 진 더 미 는 가장 자주 사용 되 는 것 입 니 다. 일반적인 우선 대기 열 은 이 진 더 미 를 사용 하여 이 루어 지 는 것 을 고려 할 수 있 습 니 다. STL 에서 우선 대기 열 은 여러분 의 사용 을 편리 하 게 할 수 있 습 니 다. 만약 에 자신 이 프로 그래 밍 을 하면 주로 sift down 과 sift up 이라는 두 핵심 작업 의 실현 에 주의 할 것 입 니 다.
 
두 갈래 로 된 더미
왼쪽 더미
비스듬히 쌓다
이항적
피 보 나치 더미
Insert
O(log n)
O(log n)
O(log n)
O(log n)
O(1)
Extract-Min
O(log n)
O(log n)
O(log n)
O(log n)
O(log n)
merge
O(m + n)
O(log n)
O(log n)
O(log n)
O(1)
프로 그래 밍 복잡 도
간단 하 다.
비교적 간단 하 다
비교적 간단 하 다
복잡 하 다
복잡 하 다.
        왼쪽 더 미 는 이 진 링크 의 저장 구 조 를 사용 하기 때문에 동적 작업 에 대한 지원 이 좋 고 합병 작업 이 필요 한 상황 에서 좋 은 선택 입 니 다.두 개의 더미 (아이 형제 저장 모드 사용) 와 피 보 나치 더미 (트 리 구조 와 양 방향 순환 링크 모드 사용) 는 프로 그래 밍 의 복잡성 과 비교적 큰 상수 인자 때문에 사용 하 는 것 이 매우 적다.
다음은 테마 leftist 트 리 로 들 어 갑 니 다:
먼저 왼쪽 편 나무의 성질 을 본다.
1. [쌓 아 올 리 는 성질]: 임의의 노드 의 키 워드 는 아이 노드 와 같은 키워드 보다 크다.
2. [왼쪽 편향 성]: 가장 가 까 운 아이의 거 리 를 노드 거리 dist 로 정의 하면 임의의 노드 의 왼쪽 아이의 거 리 는 오른쪽 아이의 거리 보다 크다.
                                A->lchild->dist >= A->rchild->dist
퇴적 성질 은 가장 작은 결점 이 항상 뿌리의 위치 에 있 도록 하기 위 한 것 으로 모든 퇴적 성질 이다.
왼쪽 편향 성 은 나무 모양 에 저 장 된 더미, 나 무 를 만 들 기 위 한 것 이다.
깊이 가 너무 크 면 안 되 고,
합병 에 유리 하 다.
        그렇다면 이 성질 은 어떻게 이 두 가지 기능 을 완성 합 니까?왼쪽 편향 성 으로 인해 나무의 왼쪽 깊이 가 오른쪽 깊이 보다 크다 는 점 은 이름 에서 알 수 있 고 왼쪽 편향 나 무 를 몇 그루 그 려 볼 수도 있다.한편, 왼쪽 나 무 는 삽입 작업 을 실현 할 때 항상 오른쪽 에서 삽입 합 니 다. 즉, 항상 짧 은 쪽 을 자라 게 합 니 다. 만약 에 오른쪽 이 왼쪽 보다 길 면 좌우 측 을 교환 하여 짧 은 쪽 에서 계속 자라 게 합 니 다.사실 구체 적 인 세부 사항 을 고려 하지 않 으 면 이런 직관 적 인 이 해 는 왼쪽 편 나무의 본질 적 인 의 미 를 볼 수 있다. 한 나무 에 두 개의 가지 가 있 는데 매번 에 자 랄 때마다 짧 은 쪽 을 먼저 자라 게 한다. 그러면 이 나 무 는 마지막 에 대칭 을 비교 할 수 있 지 않 을 까?자연 상식 과 엄밀 한 기술 논 리 는 때때로 일치한다.
다음은 왼쪽 트 리 의 구체 적 인 실현 (간단 한 테스트 를 했 지만 버그 가 없다 는 보장 은 없습니다. 버그 를 발견 하면 알려 주세요. 제 가 바로 수정 하 겠 습 니 다. 감사합니다.)

/*       */
struct LTNode
{
	int data;
	int dist;
	struct LTNode *lchild;
	struct LTNode *rchild;
};


/*    ，         */
template<typename T>
inline void swap(T &a,T &b)
{
	T tmp = a;
	a = b;
	b = tmp;
}

/*         ，      */
void InOrder(LTNode *t)
{
	if(t)
	{
		InOrder(t->lchild);
		printf("%d
",t->data);
		InOrder(t->rchild);
	}
}

/*    ，       */
LTNode* merge(LTNode* &A,LTNode* &B)
{
	if(A==NULL || B==NULL)
		return A==NULL?B:A;

	if(A->data > B->data)    /*  B->data >= A->data*/
	{	swap<LTNode*>(A,B);	}

	A->rchild = merge(A->rchild,B); /*             */

	/*          ，           ,      */
	if(A->lchild==NULL ||          /*    ，      */
	   A->rchild->dist > A->lchild->dist)/*       */
		swap<LTNode*>(A->lchild,A->rchild);

	if(A->rchild==NULL){A->dist = 0;}     /*     */
	else               {A->dist = A->rchild->dist + 1;}

	return A;
}

void insert(LTNode *&t,int x)
{
	/*initiate the node*/
	LTNode *p = new LTNode;
	p->data = x;
	p->dist = 0;
	p->lchild = NULL;
	p->rchild = NULL;

	/*merge into a leftist tree*/
	t = merge(t,p);
	printf("insert %d success
",x);
}

LTNode* ExtractMin(LTNode* &t)
{  
	/*            */
	LTNode *p = t;
	/*        */
	t = merge(t->lchild,t->rchild);
	/*           */
	return p;
}

사실 비교적 복잡 하고 이해 해 야 할 것 은 merge 작업 뿐 이지 이 진 트 리 가 실현 하 는 이 진 트 리 보다 얼마나 복잡 하지 않 습 니까?