균형 이 진 트 리 의 C 언어 구현 (삽입, 삭제, 분열, 합병) 소스 코드
16536 단어 데이터 구조
밸 런 스 이 진 트 리 (Balanced Binary Sort Tree, BBST) 는 밸 런 스 이 진 트 리 라 고 부른다.밸 런 스 트 리 는 여러 가지 가 있 는데 그 중에서 가장 유명한 것 은 구 소련 수학자 아 델 벨 리 키 와 랜 디 스 가 1962 년 에 제기 한 고도 의 밸 런 스 트 리 이다.제출 자의 영문 이름 이니셜 에 따라 AVL 트 리 라 고 약칭 한다.
균형 이 잡 힌 이 진 트 리 나 빈 나무 나 다음 과 같은 성질 을 가 진 이 진 트 리 를 찾 습 니 다. 왼쪽 나무 와 오른쪽 나 무 는 모두 균형 이 잡 힌 이 진 트 리 이 고 왼쪽 나무 와 오른쪽 나무의 높이 차 이 는 절대 1 을 초과 하지 않 습 니 다.이 진 트 리 결점 의 균형 인자 (Balance Factor) 를 이 결점 의 왼쪽 나무 높이 에서 오른쪽 나무의 높이 를 빼 면 모든 결점 의 균형 인 자 는 - 1, 0, 1 일 수 있 습 니 다.하나의 결점 의 균형 인자 의 절대 치가 1 보다 크 면 이 나 무 는 균형 을 잃 는 다.
균형 이 진 트 리 의 저장 구조 및 매크로 정의
#define LH +1 //
#define EH 0 // 、
#define RH -1 //
typedef int KeyType; //
typedef struct {
KeyType key; //
} RecordType, RcdType; //
typedef struct BBSTNode {
RcdType data;
int bf; //
struct BBSTNode *lchild, *rchild; //
} * BBSTree; //
균형 이 진 트 리 의 불 균형 및 조정
최소 불 균형 서브 트 리
균형 이 잡 힌 이 진 트 리 에 새로운 결점 을 삽입 한 후 이 결점 부터 위로 첫 번 째 불 균형 한 결점 (균형 인자 bf 가 - 2 또는 2 로 변 함) 을 찾 아 이 나무의 불 균형 여 부 를 확인한다.찾 으 면 이 결점 을 뿌리 로 하 는 자 수 를 최소 불 균형 자 수 라 고 한다.
균형 이 잡 힌 이 진 트 리 는 균형 을 잃 은 후에 조정 이 필요 하 며 균형 을 잃 은 상황 을 분류 하여 다음 과 같은 네 가지 로 나 누 어야 한다.
(1). LL 형
LL 형 은 최소 불 균형 서브 트 리 의 왼쪽 아이의 왼쪽 트 리 에 새로운 노드 를 삽입 한 것 을 말한다.불 균형 조정 은 다음 그림 에서 보 듯 이 최소 불 균형 나무의 뿌리 A 를 찾 아 왼쪽 아이의 결점 B 를 축 으로 하고 불 균형 결점 A 를 시계 방향 으로 회전한다 (오른쪽 회전 이 라 고도 부른다).우회전 은 B 가 A 를 대신 할 위치 에 A 를 B 로 병 치 하 는 오른쪽 아이 이 고, B 가 오른쪽 나무 BR B R 이 존재 하면 BR B R 을 A 로 하 는 왼쪽 나 무 를 둔다.
코드 구현
/**
* p
*
* @param p
*/
void R_Rotate(BBSTree &p) {
BBSTree lc = p->lchild; // lc p
p->lchild = lc->rchild; // lc p
lc->rchild = p; // p lc
p = lc; // p
}(2). RR 형
RR 형 에 대해 서LL 형 과 대칭 적 으로 A 를 뿌리 로 하 는 최소 불 균형 서브 트 리 에 대해 시계 반대 방향 으로 회전 (왼쪽 회전) 을 한다. 아래 그림 과 같다.
구현 코드
/**
* p
*
* @param p
*/
void L_Rotate(BBSTree &p) {
BBSTree rc = p->rchild;
p->rchild = rc->lchild;
rc->lchild = p;
p = rc;
}(3). LR 형
LR 형 은 최소 불 균형 서브 트 리 의 왼쪽 아이의 오른쪽 서브 트 리 에 새로운 결 점 을 삽입 한 것 을 말한다.처리 방법 은 아래 그림 에서 보 듯 이 먼저 A 를 뿌리 로 하 는 작은 불 균형 자 나 무 를 찾 아 이 나무의 왼쪽 아이 결점 B 를 축 으로 하고 오른쪽 나무 결점 C 를 좌회전 조정 하여 LL 형 으로 만든다.다시 C 를 축 으로 하여 불 균형 결점 A 를 우회전 조정 한다.
(4). RL 형
RL 형 과 LR 형 이 대칭 적 이 므 로 오른쪽 회전 처리 와 왼쪽 회전 처 리 를 순서대로 해 야 한다. 아래 그림 과 같다.
균형 트 리 삽입
구조 평 아 2 또 나 무 는 순서대로 사람 을 꽂 아 결산 하 는 방식 을 사용 할 수 있 는데 그 재 귀 절 차 는 다음 과 같다.
4. 567917. 빈 나무 라면 사람의 결점 을 뿌리 결점 으로 하고 나무의 높이 가 1 증가한다
4. 567917. 노드 와 뿌리 노드 가 같 으 면 삽입 할 필요 가 없다
4. 567917. 만약 에 삽입 을 기다 리 는 사람의 결점 이 뿌리 결점 보다 작고 왼쪽 나무 에 똑 같은 결점 이 존재 하지 않 으 면 왼쪽 나무 에 삽입 하고 삽입 후의 왼쪽 나무 높이 가 1 증가 하면 상황 에 따라 처리한다.
4. 567917. 원 근 결점 의 균형 인 자 는 - 1 (오른쪽 나무 가 왼쪽 나무 보다 높 음) 이 고 0 으로 변경 되 며 나무의 높이 는 변 하지 않 습 니 다
4. 567917. 원 근 결점 의 균형 인 자 는 0 (좌우 나무 높이 가 같다) 이 고 1 로 바 뀌 며 나무의 높이 는 1 증가 합 니 다
4. 567917. 원근 결점 의 균형 인 자 는 1 (왼쪽 나무 가 오른쪽 나무 보다 높 음) 이다. 만약 에 왼쪽 나무 뿌리 결점 의 균형 인자 가 1 이면 LL 형 에 속 하기 때문에 우회전 균형 조정 을 하고 조정 한 후에 뿌리 결점 과 오른쪽 아이의 균형 인 자 를 0 으로 바 꾸 면 나무의 높이 가 변 하지 않 는 다.만약 에 왼쪽 나무 뿌리 결점 의 균형 인자 가 - 1 이면 LR 형 에 속 하기 때문에 순서대로 왼쪽 회전 과 오른쪽 회전 처 리 를 하고 조정 한 후에 뿌리 결점 과 왼쪽, 오른쪽 아이의 균형 인 자 를 수정 해 야 한다. 나무의 높이 는 변 하지 않 는 다
4. 567917. 만약 에 삽입 할 노드 가 뿌리 노드 보다 크 고 오른쪽 서브 트 리 에 똑 같은 노드 가 존재 하지 않 으 면 오른쪽 서브 트 리 에 삽입 하고 삽입 한 후의 오른쪽 서브 트 리 높이 에 1 을 추가 할 때 상황 에 따라 처리 합 니 다.
4. 567917. 원 근 결점 의 균형 인 자 는 1 (왼쪽 나무 가 오른쪽 나무 보다 높 음) 이 고 0 으로 바 뀌 며 나무의 높이 는 변 하지 않 습 니 다
4. 567917. 원 근 결점 의 균형 인 자 는 0 (좌우 나무 높이 가 같다) 이 고 - 1 로 변경 되 며 나무의 높이 는 1 을 더 합 니 다
4. 567917. 원근 결점 의 균형 인 자 는 - 1 (오른쪽 나무 가 왼쪽 나무 보다 높 음) 이다. 만약 에 오른쪽 나무 뿌리 결점 의 균형 인자 가 1 이면 RL 형 에 속 하기 때문에 순서대로 오른쪽 회전 과 왼쪽 회전 처 리 를 하고 회전 처 리 를 한 후에 뿌리 결점 과 왼쪽, 오른쪽 나무 뿌리 결점 의 균형 인 자 를 수정 해 야 한다. 나무의 높이 는 변 하지 않 는 다.만약 에 오른쪽 나무 뿌리 결점 의 균형 인자 가 - 1 이면 RR 형 에 속 하기 때문에 좌회전 처 리 를 한 번 해 야 한다. 그리고 좌회전 한 후에 뿌리 결점 과 왼쪽, 오른쪽 나무 뿌리 결점 의 균형 인 자 를 갱신 하고 나무의 높이 는 변 하지 않 는 다
좌 평형 처리 조작
/**
* T
*
* @param T T
*/
void LeftBalance(BBSTree &T) {
BBSTree lc, rd;
lc = T->lchild;
switch (lc->bf) {
case LH: {
T->bf = lc->bf = EH;
R_Rotate(T);
break;
} case RH: {
rd = lc->rchild;
switch (rd->bf) {
case LH: {
T->bf = RH;
lc->bf = EH;
break;
} case EH: {
T->bf = lc->bf = EH;
break;
} case RH: {
T->bf = EH;
lc->bf = LH;
break;
}
}
rd->bf = EH;
L_Rotate(T->lchild);
R_Rotate(T);
break;
}
}
}오른쪽 평형 처리 조작
/**
* T
*
* @param T T
*/
void RightBalance(BBSTree &T) {
BBSTree rc, ld;
rc = T->rchild;
switch (rc->bf) {
case RH:
T->bf = rc->bf = EH;
L_Rotate(T);
break;
case LH:
ld = rc->lchild;
switch (ld->bf) {
case RH: {
T->bf = LH;
rc->bf = EH;
break;
} case EH: {
T->bf = rc->bf = EH;
break;
} case LH: {
T->bf = EH;
rc->bf = RH;
break;
}
}
ld->bf = EH;
R_Rotate(T->rchild);
L_Rotate(T);
break;
}
}코드 삽입 실현
/**
*
*
* @param T T
* @param e
* @param taller
* @return TRUE
*/
Status InsertAVL(BBSTree &T, RcdType e, Status &taller) {
if (NULL == T) {
// T ，
T = (BBSTree)malloc(sizeof(BBSTNode));
T->data = e;
T->bf = EH;
T->lchild = NULL;
T->rchild = NULL;
taller = TRUE;
} else if (e.key == T->data.key) {
//
taller = FALSE;
return FALSE;
} else if (e.key < T->data.key) {
//
if (FALSE == InsertAVL(T->lchild, e, taller)) {
return FALSE;
}
if (TRUE == taller) {
switch (T->bf) {
case LH: {
LeftBalance(T);
taller = FALSE;
break;
} case EH: {
T->bf = LH;
taller = TRUE;
break;
} case RH: {
T->bf = EH;
taller = FALSE;
break;
}
}
}
} else {
if (FALSE == InsertAVL(T->rchild, e, taller)) {
return FALSE;
}
if (TRUE == taller) {
switch (T->bf) {
case LH: {
T->bf = EH;
taller = FALSE;
break;
} case EH: {
T->bf = RH;
taller = TRUE;
break;
} case RH: {
RightBalance(T);
taller = FALSE;
break;
}
}
}
}
return TRUE;
}균형 트 리 삭제
균형 이 잡 힌 이 진 트 리 의 삭 제 는 삽입 의 반 과정 으로 볼 수 있 기 때문에 방향 을 조정 하 는 것 도 반대 이기 때문에 조작 하기 어렵 지 않다.
그 중에서 전구 결점 을 찾 는 근 거 는 균형 이 진 트 리 의 중간 순서 가 질서 있 는 서열 이라는 것 이다.또한 삭 제 된 점 의 직접 앞 구 는 왼쪽 나무의 오른쪽 아래 에 있다.삭 제 된 노드 의 값 을 전구 결점 의 값 으로 대체 하고 전구 결점 을 삭제 하면 간단 한 조작 과 같다.
코드 구현
/**
*
*
* @param T
* @param key
* @param shorter
* @return
*/
Status DeleteAVL(BBSTree &T, KeyType key, Status &shorter) {
if (NULL == T) {
//
return FALSE;
} else if (T->data.key == key) {
//
BBSTree p = NULL;
if (NULL == T->lchild) {
//
p = T;
T = T->rchild;
free(p);
shorter = TRUE; //
} else if (T->rchild == NULL) {
//
p = T;
T = T->lchild;
free(p);
shorter = TRUE; //
} else {
//
p = T->lchild;
while (p->rchild != NULL) {
p = p->rchild;
}
T->data = p->data;
//
DeleteAVL(T->lchild, p->data.key, shorter);
}
} else if (T->data.key > key) {
if (DeleteAVL(T->lchild, key, shorter) == FALSE) {
return FALSE;
}
if (shorter == TRUE) {
switch (T->bf) {
case LH: {
T->bf = EH;
shorter = TRUE;
break;
} case EH: {
T->bf = RH;
shorter = FALSE;
break;
} case RH: {
RightBalance(T);
if (T->rchild->bf == EH) {
shorter = FALSE;
} else {
shorter = TRUE;
}
break;
}
}
}
} else {
if (DeleteAVL(T->rchild, key, shorter) == FALSE) {
return FALSE;
}
if (shorter == TRUE) {
switch (T->bf) {
case LH: {
LeftBalance(T);
if (T->lchild->bf == EH) {
shorter = FALSE;
} else {
shorter = TRUE;
}
break;
} case EH: {
T->bf = LH;
shorter = FALSE;
break;
} case RH: {
T->bf = EH;
shorter = TRUE;
break;
}
}
}
}
return TRUE;
}균형 이 잡 힌 이 진 트 리 의 분열 과 합병
균형 이 진 트 리 의 분열 과 합병 은 삽입 작업 에 따라 이 루어 집 니 다. 구체 적 으로 다음 코드 를 보십시오.
/**
* ， key key
*
* @param T
* @param key
* @param T1 key
* @param T2 key
*/
void SpiltBBST(BBSTree T, KeyType key, BBSTree &T1, BBSTree &T2) {
Status taller = FALSE;
if (T != NULL) {
SpiltBBST(T->lchild, key, T1, T2); //
if(T->data.key > key) {
InsertAVL(T1, T->data, taller);
} else {
InsertAVL(T2, T->data, taller);
}
SpiltBBST(T->rchild, key, T1, T2);
}
}
/**
*
*
* @param T1
* @param T2
*/
void MergeBBST(BBSTree &T1, BBSTree T2) {
Status taller = FALSE;
if (T2 != NULL) {
MergeBBST(T1, T2->lchild);
InsertAVL(T1, T2->data, taller);
MergeBBST(T1, T2->rchild);
}
}완전한 코드 와 테스트 함 수 를 가 져 오 려 면 오 십시오.https://github.com/zhengjunming/ds/tree/master/avl-tree 중 클론.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
