균형 이 진 트 리 구현 (1)
AVL 트 리 는 이 진 트 리 이지 만 자신의 높이 균형 을 유지 할 수 있 기 때문에 트 리 의 검색 과 삽입 이 빠 릅 니 다. 물론 트 리 의 균형 을 유지 하기 위해 트 리 노드 삽입 과 삭제 과정 에서 도 트 리 자체 의 균형 을 유지 하 는 작업 을 해 야 합 니 다.AVL 트 리 는 구 소련 인 G. M. Adelson - Velskii and E. M. Landis 가 1962 년 에 공동으로 발명 한 것 으로 이런 구 조 는 컴퓨터 과학 에서 발 명 된 첫 번 째 균형 적 특성 을 가 진 데이터 구조 로 창의 적 인 의 미 를 가진다. 나중에 발 명 된 2 - 4 나무, 빨간색 과 검은색 나무, AA 나무 등 을 위해 방향 을 지적 했다. 이런 디자인 사상 은 매우 중요 한 의 미 를 가진다.나중에 디자인 된 더욱 복잡 한 데이터 구조, 예 를 들 어 빨간색 과 검은색 나무 가 평균 성능 에서 AVL 나 무 를 초과 하기 때문에 AVL 나무 가 직접 응용 하 는 장소 가 많 지 않 지만 그 중의 우수한 디자인 사상 을 배 우 는 것 은 자신의 수준 을 향상 시 키 는 데 중요 한 의 미 를 가진다.
2. 밸 런 스 이 진 트 리 삽입 작업
2.1 최소 불 균형 나무의 뿌리 노드
최소 불 균형 트 리 의 뿌리 결산 점: 즉, 삽입 작업 을 할 때 결산 점 을 삽입 해 야 할 위 치 를 찾 아 삽입 한 후 이 결산 점 에서 위로 찾 는 것 (역 추적) 입 니 다. 첫 번 째 불 균형 한 결산 점 은 바로 균형 인자 bf 가 - 2 또는 2 로 변 하 는 것 입 니 다.
균형 잡 힌 이 진 트 리 가 결점 으로 인해 균형 을 잃 었 을 때 최소 불 균형 한 서브 트 리 만 균형 적 으로 회전 하면 된다.회전 처 리 를 거 친 서브 트 리 의 깊이 는 삽입 전의 것 과 같 기 때문에 삽입 경로 에 있 는 모든 조상 노드 의 균형 도 에 영향 을 주지 않 습 니 다.
2.2 균형 이 진 트 리 의 삽입 작업
균형 이 잡 힌 이 진 트 리 의 조작 은 재 귀적 인 방식 으로 밑부분 부터 거 슬러 올 라 가 최소 불 균형 나무의 뿌리 노드 를 발견 할 수 있다.
(1) 삽입 작업 은 먼저 뿌리 노드 부터 시작 하여 삽입 값 과 노드 값 을 비교 하고 같 으 면 되 돌아 가 고 작 으 면 뿌리 노드 의 왼쪽 트 리 를 건 네 주 며 그렇지 않 으 면 오른쪽 트 리 로 돌아간다.
(2) 나무 에 결점 을 삽입 할 때 원래 의 나무, 잎 결점 의 좌우 지침 을 바 꾸 어 새로운 결점 을 삽입 합 니 다.그리고 표지 결점 의 높이 가 증가한다.
(3) 재 귀 되 돌아 와 잎 결점 부터 거 슬러 올 라 가 삽입 상황 (왼쪽 나무 삽입, 균형 인자 더하기 1, 오른쪽 나무 삽입 균형 인자 감소 1) 에 따라 부 결점 의 균형 요 소 를 순서대로 바꾼다.
(4) 결점 의 균형 인자 가 2 또는 2 일 경우 2.3 에서 말 한 방법 에 따라 이 노드 를 회전 시 키 는 동시에 높이 가 증가 함 을 나타 낸다.
노드 삽입 작업 의 코드 는 다음 과 같 습 니 다.
/************************************************************************/
/* ， */
/************************************************************************/
int insertnode(pnode * ptree, nodetype key, int * taller)
{
// ，
if (!(*ptree))
{
*ptree = (pnode)malloc(sizeof(pnode));
if (!(*ptree))
{
debug("alloc node failed
");
}
debug("alloc success
");
(* ptree)->key = key;
(* ptree)->bf = EN;
(* ptree)->rchild = (* ptree)->lchild = NULL;
*taller = 1;
}// ， ，
else if ((* ptree)->key == key)
{
debug("find the node
");
* taller = 0;
return 0;
}
else if ((* ptree)->key > key)
{
// ，
if (insertnode(&(* ptree)->lchild, key, taller) ==0)
return 0;
// ， ， 。
if (*taller)
{
switch((*ptree)->bf)
{ // ，
case LH:
printf(" ");
leftblance(ptree);
* taller = 0;
break;
// ， 1.
case EN:
(*ptree)->bf = LH;
* taller = 1;
break;
// ， 0
case RH:
(*ptree)->bf = EN;
*taller = 0;
break;
default:
break;
}
}
}
else
{
// ，
if (insertnode(&(* ptree)->rchild, key, taller) ==0)
return 0;
// ， ，
if(*taller)
{
switch((*ptree)->bf)
{ // ， 0
case LH:
(*ptree)->bf = EN;
*taller = 0;
break;
// ， -1
case EN:
(*ptree)->bf = RH;
*taller = 1;
break;
// ，
case RH:
printf(" ");
rightblance(ptree);
*taller = 0;
break;
default:
break;
}
}
}
return 1;
}2.3 균형 이 진 트 리 결점 의 회전,
회전 은 주로 포인터 의 방향 과 관련 된 노드 의 균형 요 소 를 바 꾸 어 이 루어 진다.
2.3.1 지침 을 바 꾸 어 회전 을 실현 한다.
회전 하 는 상황 에 따라 왼쪽 회전 과 오른쪽 회전 으로 나 뉜 다.
1. 왼쪽 회전: 뿌리 부분 이 오른쪽 아이의 왼쪽 아이 가 된다.오른쪽 아이 가 뿌리 가 되다.
실현 절차: 1. 오른쪽 아 이 를 가리 키 는 지침 을 저장 합 니 다.2。뿌리 노드 의 오른쪽 지침 은 오른쪽 노드 의 왼쪽 아 이 를 가리킨다.3. 뿌리 노드 의 오른쪽 아이의 지침 은 뿌리 노드 를 가리킨다.4. 뿌리 노드 의 지침 은 뿌리 노드 의 오른쪽 아 이 를 가리킨다.
그림 은 다음 과 같다.
코드 는 다음 과 같다.
/************************************************************************/
/* */
/************************************************************************/
void left_rotate(pnode * pn)
{
//
pnode pr= (* pn)->rchild;
//
(*pn)->rchild = pr->lchild;
//
pr->lchild = (*pn);
//
(*pn) = pr;
}2. 우회전
오른쪽 회전 은 왼쪽 회전 과 마찬가지 로 코드 참조
/************************************************************************/
/* */
/************************************************************************/
void right_rotate(pnode * pn)
{
//
pnode pl= (*pn)->lchild;
// ，
(*pn)->lchild = pl->rchild;
//
pl->rchild = *pn;
//
*pn = pl;
}/************************************************************************/3. 결점 의 삽입 상황 에 따라 회전 유형 은 4 가지 로 나 뉘 는데 조작 방법 은 다음 과 같다.
조작 유형
조작 방법
왼쪽: 왼쪽 트 리 왼쪽 노드 삽입
뿌리 노드 오른쪽 회전
좌우: 왼쪽 트 리 오른쪽 노드 삽입
먼저 뿌리 노드 의 왼쪽 아이 가 왼쪽으로 회전 한 다음 에 뿌리 노드 가 오른쪽으로 회전 합 니 다.
오른쪽: 오른쪽 트 리 오른쪽 노드 삽입
뿌리 노드 왼쪽 회전
오른쪽 왼쪽: 오른쪽 하위 트 리 왼쪽 노드 삽입
먼저 뿌리 노드 의 오른쪽 아이 가 오른쪽으로 회전 한 다음 에 뿌리 노드 가 왼쪽으로 회전 합 니 다.
코드 는 다음 과 같다.
/************************************************************************/
/* */
/************************************************************************/
void leftblance(pnode * pn)
{
pnode pr;
pr =(*pn)->lchild;
switch(pr->bf)
{
case LH://
printf(" ");
(*pn)->bf = (*pn)->lchild->bf = EN;
//
right_rotate(pn);
break;
case RH: //
switch((*pn)->lchild->rchild->bf)
{
case LH:
(*pn)->bf = RH;
(*pn)->lchild->bf = EN;
break;
case EN:
(*pn)->bf = (*pn)->lchild->bf = EN;
break;
case RH:
(*pn)->bf = EN;
(*pn)->lchild->bf = LH;
break;
default:
break;
}
(*pn)->lchild->rchild->bf = EN;
//
left_rotate(&((*pn)->rchild));
//
right_rotate(pn);
break;
default:
break;
}
}
/************************************************************************/
/* */
/************************************************************************/
void rightblance(pnode * pn)
{
pnode pr;
pr = (*pn)->rchild;
switch(pr->bf)
{
// ：
case RH:
(*pn)->bf = (*pn)->rchild->bf = EN;
left_rotate(pn);
break;
// ：
case LH:
switch((*pn)->rchild->lchild->bf)
{
case LH:
(*pn)->bf = EN;
(*pn)->rchild->bf = RH;
break;
case EN:
(*pn)->bf = (*pn)->rchild->bf = EN;
break;
case RH:
(*pn)->bf = LH;
(*pn)->rchild->bf = EN;
break;
default:
break;
}
(*pn)->rchild->lchild->bf = EN;
// ，
right_rotate(&((*pn)->rchild));
// ，
left_rotate(pn);
break;
default:
break;
}
}2.3.2 결점 균형 도의 변 화 는 다음 블 로 그 를 보십시오.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
