AVL 트 리 동적 집합 실현 k 소수 찾기

AVL 트 리 동적 집합 실현 k 소수 찾기
정적 배열 에서 k 소 수 를 찾 으 면 빠 른 배열 사상 을 이용 하여 빠 른 배열 코드 를 바탕 으로 변경 하면 완성 할 수 있 고 시간 복잡 도 는 O (n) 이 며 구체 적 으로 보 여주 지 않 습 니 다.
그러나 하나의 동적 집합 에서 잦 은 업데이트 와 삭제 작업 이 있 으 면 정적 배열 로 이 루어 지 는 것 은 적절 하지 않다. 삽입 과 삭제 작업 이 불편 하기 때문에 다음은 AVL 트 리 를 이용 하여 이 루어 진다.
구체 적 인 체 조 는 AVL 트 리 를 바탕 으로 트 리 의 모든 노드 에 도 메 인 을 추가 합 니 다. 이 노드 를 루트 노드 로 하 는 서브 트 리 의 노드 수 는 subTreeSize 이 고 다른 도 메 인 은 AVL 트 리 와 같 습 니 다.삽입 작업 (함수 addNewNode) 에 대해 서 는 새 노드 노드 를 삽입 하 는 과정 에서 한 노드 에 옮 겨 다 니 며 하위 트 리 크기 를 업데이트 합 니 다 (즉, 삽입 후 하위 트 리 크기 에 1 추가).삭제 작업 (함수 deleteOldNode), 예 를 들 어 정 조 된 이 진 트 리 의 삽입 작업 은 재 귀 과정 에서 노드 를 업데이트 하 는 하위 트 리 크기 (즉, 삽입 후 하위 트 리 크기 가 1 감소) 만 삭제 하고 삽입 과 삭제 작업 시간 복잡 도 는 모두 O (log n) (즉, 트 리 높이) 입 니 다.그 다음 에 k 번 작은 동작 (findKth) 을 찾 습 니 다. 만약 에 왼쪽 에 k 를 옮 겨 다 니 는 값 이 변화 가 없 으 면 노드 의 값 의 정렬 크기 는 왼쪽 서브 트 리 의 노드 수 + 1 이 고 오른쪽 에 있 을 때 왼쪽 서브 트 리 와 현재 뿌리 노드 의 값 이 찾 는 k 번 째 작은 값 보다 작 기 때 문 입 니 다. 이때 k - 앞 노드 의 정렬 크기 (즉, 오른쪽 서브 트 리 의 상대 적 크기), 시간 복잡 도 는 O (log n) 입 니 다.구체 적 인 실현 코드 는 다음 과 같다.
데이터 구조의 정의

typedef struct AVLNode* Position;
typedef Position AVLTree; /* AVL    */
struct AVLNode {
	int value;
	AVLTree left;
	AVLTree right;
	int height;       //  
	int subTreeSize;//              
};

사용 함수

Position findMin(AVLTree Tree) {  //        
	if (Tree->left)
		return findMin(Tree->left);
	else
		return Tree;
}
Position findMax(AVLTree Tree) {  //        
	if (Tree->right)
		return findMin(Tree->left);
	else
		return Tree;
}
int getHeight(AVLTree Tree) { //    
	if (!Tree)return 0;
	return max(getHeight(Tree->left), getHeight(Tree->right)) + 1;
}
int getSubTreeSize(AVLTree Tree) {
	int cnt = 0;
	if (Tree->left)
		cnt = Tree->left->subTreeSize + 1;
	else cnt = 1;
	if (Tree->right)
		cnt += Tree->right->subTreeSize;
	return cnt;
}
AVLTree LL_Rotation(AVLTree Tree) { //LL  
	AVLTree tmp = Tree->left;
	Tree->left = tmp->right;
	tmp->right = Tree;
	Tree->height = max(getHeight(Tree->left), getHeight(Tree->right)) + 1;
	tmp->height = max(getHeight(tmp->left), Tree->height) + 1;
	tmp->subTreeSize = Tree->subTreeSize;
	Tree->subTreeSize = getSubTreeSize(Tree);
	return tmp;
}
AVLTree RR_Rotation(AVLTree Tree) {  //RR  
	AVLTree tmp = Tree->right;
	Tree->right = tmp->left;
	tmp->left = Tree;
	Tree->height = max(getHeight(Tree->left), getHeight(Tree->right)) + 1;
	tmp->height = max(getHeight(tmp->right), Tree->height) + 1;
	tmp->subTreeSize = Tree->subTreeSize;
	Tree->subTreeSize = getSubTreeSize(Tree);
	return tmp;
}
AVLTree LR_Rotation(AVLTree Tree){  //LR  
	Tree->left = RR_Rotation(Tree->left);
	return LL_Rotation(Tree);
}
AVLTree RL_Rotation(AVLTree Tree) { //RL  
	Tree->right = LL_Rotation(Tree->right);
	return RR_Rotation(Tree);
}
AVLTree addNewNode(AVLTree Tree, int value){
	if (!Tree) { 
		Tree = (AVLTree)malloc(sizeof(struct AVLNode));
		Tree->value = value;
		Tree->height = 0;
		Tree->left = Tree->right = NULL;
		Tree->subTreeSize = 1;
	} 
	else if (value < Tree->value) { //    
		Tree->left = addNewNode(Tree->left, value);
		Tree->subTreeSize++;
		if (getHeight(Tree->left) - getHeight(Tree->right) == 2)//      
			if (value < Tree->left->value)  //     LL    LR  
				Tree = LL_Rotation(Tree);
			else
				Tree = LR_Rotation(Tree);
	}
	else if (value > Tree->value) {//    
		Tree->right = addNewNode(Tree->right, value);
		Tree->subTreeSize++;
		if (getHeight(Tree->left) - getHeight(Tree->right) == -2)//      
			if (value > Tree->right->value)//     RR    RL  
				Tree = RR_Rotation(Tree);
			else
				Tree = RL_Rotation(Tree);
	}
	//    
	Tree->height = max(getHeight(Tree->left), getHeight(Tree->right)) + 1;
	return Tree;
}
AVLTree deleteOldNode(AVLTree Tree, int value) { //    
	Position tmp;
	if (!Tree)
		printf("not find
");
	else {
		if (value < Tree->value) {//  ,                
			Tree->subTreeSize--;  //               
			Tree->left = deleteOldNode(Tree->left, value);
			if (getHeight(Tree->left) - getHeight(Tree->right) == -2) {//      
				tmp = Tree->right;
				if (getHeight(tmp->left)> getHeight(tmp->right))//     RR    RL  
					Tree = RL_Rotation(Tree);  //             RL  
				else
					Tree = RR_Rotation(Tree);  //   RR  
			}
		}
		else if (value > Tree->value) {//  ，                
			Tree->right = deleteOldNode(Tree->right, value);
			Tree->subTreeSize--;
			if (getHeight(Tree->left) - getHeight(Tree->right) == 2) {//      
				tmp = Tree->left;
				if (getHeight(tmp->left) > getHeight(tmp->right))  //     LL    LR  
					Tree = LL_Rotation(Tree);//    
				else
					Tree = LR_Rotation(Tree);
			}
		}
		else {//       
			if (Tree->left && Tree->right) {  //          
				if (getHeight(Tree->left) > getHeight(Tree->right)) { //        ，                     
					tmp = findMax(Tree->left);	//          
					Tree->value = tmp->value;  //          
					Tree->subTreeSize--;  //      
					Tree->left= deleteOldNode(Tree->left, Tree->value);
				}
				else {
					tmp = findMin(Tree->right);  //          
					Tree->value = tmp->value;  //          
					Tree->subTreeSize--;  //      
					Tree->right = deleteOldNode(Tree->right, Tree->value); //            
				}
			}
			else { //       
				tmp = Tree;
				if (!Tree->left)       //          
					Tree = Tree->right;
				else                   //       
					Tree = Tree->left;
				free(tmp);
			}
		}
	}
	return Tree;
}
AVLTree createTree(int a[], int n) {
	if (!n)return NULL;
	AVLTree Tree = NULL;
	for (int i = 0; i < n; i++)
		Tree = addNewNode(Tree, a[i]);
	return Tree;
}
int findKth(AVLTree Tree, int k) {//   k   
	if (k > Tree->subTreeSize)return -inf;
	if (!Tree->left && !Tree->right)return Tree->value;
	if (Tree->left) {
		int now = Tree->left->subTreeSize + 1;
		if (now == k)return Tree->value;
		else if (now > k)
			return findKth(Tree->left, k);
		if (Tree->right)
			return findKth(Tree->right, k - now);
	}
	else {
		if (k == 1)
			return Tree->value;
		else
			return findKth(Tree->right, k - 1);
	}
}

디 버 깅 코드

void qxbl(AVLTree Tree) { //    
	if (Tree) {
		printf("%d %d
", Tree->value, Tree->subTreeSize);
		qxbl(Tree->left);
		qxbl(Tree->right);
	}
}
int main() {
	int n = 8;
	int a[] = { 1,2,9,4,5,11,7,8 };
	AVLTree Tree = createTree(a, n);
	qxbl(Tree);
	char ty;
	int k;
	while (cin >> ty) {  //       a      b      c    k   
		cin >> k;
		if (ty == 'a') {
			Tree = addNewNode(Tree, k);//     
			printf("Add success!
");
			qxbl(Tree);
		}
		else if (ty == 'b') {
			Tree = deleteOldNode(Tree, k); //    
			printf("Delete successful!
");
			qxbl(Tree);
		}
		else
			printf("The %d-th small number:%d
", k, findKth(Tree, k));
	}
	return 0;
}

실행 결 과 는 다음 과 같다.

5 8
2 3
1 1
4 1
9 4
7 2
8 1
11 1
a 3
Add success!
5 9
2 4
1 1
4 2
3 1
9 4
7 2
8 1
11 1
c 5
The 5-th small number:5
b 5
Delete successful!
7 8
2 4
1 1
4 2
3 1
9 3
8 1
11 1
c 5
The 5-th small number:7