[알고리즘]최적 이진 탐색 트리 구현 레포트

소개글

① 노드의 킷값과 확률은 파일로부터 입력 받는다.
② 최적 이진 탐색 트리를 표현현다.

목차

■ Dynamic Programming을 이용한 최적이진 탐색 트리를 작성 하시오
■ 문제 분석 & 해결
■ Source File
■ Data File
■ Result Screen

본문내용

■ Dynamic Programming을 이용한 최적이진 탐색 트리를 작성 하시오.
- 조건
① 노드의 킷값과 확률은 파일로부터 입력 받는다.
② 최적 이진 탐색 트리를 표현현다.

■ 문제 분석 & 해결
- 트리의 각 노드가 탐색될 확률이 주어질 때, 그 트리의 평균 비교횟수가 최소인 탐색 트리를 구축하는 것이 목적
- 이진탐색트리를 구성하는 n개의 노드가 각각 K1, K2,...Kn 의 키 값을 갖는다고 가정
키 값 Ki 가 탐색될 확률 : p
키 값 Ki 를 찾는데 필요한 비교횟수 : Ci
이때 이진탐색트리의 평균 비교횟수 =
이 값을 최소화하는 이진탐색트리를 구성하는 것이 목표
- 다음 그림이 최적해를 보여 준다고 가정

#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define MAX 100 //최대 아이템의 수

typedef struct{ //아이템을 저장할 구조체
char key[10];
float p;
}b_tree;

struct nodetype{ //트리를 만들 때 노드를 구성할 구조체
char key[10];
nodetype *left;
nodetype *right;
};
typedef nodetype* node_pointer; //노드 포인터 구조체

참고 자료

없음