데이터 구조 - 왕도 2017 - 제4 장 나무 와 이 진 트 리 - 나무, 숲

1. 나무의 저장 구 조 는 여러 가지 가 있 는데 순서 저장 구 조 를 사용 할 수도 있 고 체인 저장 구 조 를 사용 할 수도 있다. 모두 나무 에서 각 노드 간 의 논리 관 계 를 유일 하 게 나타 내 고 세 가지 자주 사용 하 는 저장 구 조 를 요구한다.
  1) 양친 표현법
  한 조 의 연속 공간 으로 모든 노드 를 저장 하 는 동시에 모든 노드 에 가짜 지침 을 추가 하여 부모 노드 가 배열 에 있 는 위 치 를 표시 하고 뿌리 노드 아래 는 0 이 라 고 표시 하 며 가짜 지침 도 메 인 은 - 1 이다.
    

#define MAX_TREE_SIZE 100   //       
typedef struct{        //      
   ElemType data;    //    
   int parent;           //     
}PTNode;

typedef struct{                                //      
  PTNode nodes[MAX_TREE_SIZE];   //    
  int n;                       //   
}PTree;

  단점 은 결점 을 구 하 는 아이 가 전체 구 조 를 옮 겨 다 녀 야 한 다 는 것 이다.
  2) 아이 표현법
   모든 노드 의 아이들 을 단일 체인 시계 로 연결 시 켜 형 성 된 선형 구조 로 N 개의 노드 에 N 개의 아이 체인 시계 (잎 이 맺 힌 아이 체인 시 계 는 빈 시계) 가 있다. 이런 저장 방식 에 대해 자녀 를 찾 는 작업 은 매우 직접적 이 고 부 모 를 찾 는 작업 은 N 개의 노드 에서 아이 체인 시계 바늘 영역 이 가리 키 는 N 개의 아이 체인 시 계 를 옮 겨 다 녀 야 한다.
  3) 아이 형제 표현법 은 이 진 트 리 표현법, 즉 이 진 트 리 체인 표를 나무의 저장 구조 로 한다.아이 형제 표현법 은 모든 결점 에 세 가지 내용 을 포함 시 키 는 것 이다. 결점 값, 결점 을 가리 키 는 첫 번 째 아이의 결점 을 가리 키 는 지침 과 결점 을 가리 키 는 다음 형제의 결점 을 가리 키 는 지침 (이 역 을 따라 결점 을 찾 을 수 있 는 모든 형제 결점) 이다.
    메모리 구조:

typpedef struct CSNode{
   ElemType data;
   struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

   이런 저장 방식 은 비교적 유연 하 다. 가장 큰 장점 은 나무 가 이 진 트 리 로 전환 하 는 작업 을 편리 하 게 실현 하고 결점 을 찾기 쉬 운 아이 등 이다. 그러나 단점 은 현재 결점 에서 부모 의 결점 을 찾 는 것 이 비교적 번거롭다 는 것 이다.각 노드 에 parent 도 메 인 을 추가 하여 부모 노드 를 가리 키 면 노드 의 부모 노드 를 찾 는 것 도 편리 합 니 다. 
2. 나무, 숲 과 이 진 트 리 의 전환
   이 진 트 리 와 나 무 는 모두 이 진 트 리 를 저장 구조 로 할 수 있 고 이 진 트 리 를 매개 로 나무 와 이 진 트 리 의 대응 관 계 를 도 출 할 수 있다. 즉, 나 무 를 지정 하면 유일한 이 진 트 리 와 대응 하 는 것 을 찾 을 수 있다.물리 적 구조 상 나무의 아이 형제 표현법 은 이 진 트 리 의 이 진 트 리 표현법 과 같다. 즉, 각 노드 에 두 개의 지침 이 있 기 때문에 같은 저장 구조의 다른 해석 으로 한 그루 의 나 무 를 이 진 트 리 로 바 꿀 수 있다.
   나 무 를 이 진 트 리 로 바 꾸 는 규칙: 각 노드 의 왼쪽 지침 은 첫 번 째 아이의 결점 을 가리 키 고 오른쪽 지침 은 나무 에 있 는 인접 한 형제 결점 을 가리 키 며 왼쪽 아이의 오른쪽 형제 라 고 할 수 있다. 뿌리 결점 에 형제 가 없 기 때문에 나무 에서 바 꾸 어 얻 은 이 진 트 리 는 오른쪽 나무 가 없다.숲 을 바 꾸 려 면 먼저 모든 자 나 무 를 바 꾼 다음 에 첫 번 째 뿌리 결산 점 을 나무의 뿌리 결산 점 으로 하고, 나머지 자나무 의 뿌리 결산 점 은 나무 에서 첫 번 째 나무의 뿌리 결산 점 과 형제 로 바 꾸 고, 이 진 나 무 는 나무 나 숲 으로 바 꾸 는 것 이 유일한 것 이다.
3. 나무 와 숲 의 이동
  트 리 의 선 근 옮 겨 다 니 기 접근 순 서 는 이 진 트 리 의 선 순위 와 같 습 니 다.
  나무의 뒷 뿌리 를 옮 겨 다 니 는 접근 순 서 는 이 나무의 중간 순서 와 같 습 니 다.
  숲 의 선착순 과 중 서 는 이 진 트 리 의 역력 과 같다.
4. 나무의 응용 프로그램
  일반적으로 나무의 부 모 는 집합 을 나타 내 는 저장 구 조 를 나타 내 고 각 자 는 한 그루 의 나무 로 집합 을 나타 내 며 모든 자 집합 을 나타 내 는 나 무 는 전체 집합 을 나타 내 는 숲 을 구성 하여 부모 표시 배열 에 보관 된다.보통 배열 요소 의 아래 표 시 는 요소 이름 을 대표 하고 뿌리 결산 점 의 아래 표 시 는 부분 집합 명 을 대표 하 며 뿌리 결산 점 의 부모 결산 점 은 마이너스 이다.초기 화 할 때 대 집합 S 의 모든 노드 는 뿌리 노드 이 고 그들의 부모 도 메 인 은 - 1 이다.
  두 개의 부분 집합 을 얻 기 위해 서 는 그 중 한 개의 집합 근 결점 의 부모 지침 을 다른 집합 근 결점 을 가리 키 면 된다.
  

//          ：
#define SIZE 100
int UFSets[SIZE];   //      ，      

//         （S     ）
void Init(int S[]){
   for(int i = 0;i < SIZE;i++){
      S[i] = -1;
   }
}
//Find  （                x    ）

int Find(int S[], int x){
   while(S[x] >= 0)
       x=S[x];
   return x;
}

//Union  （            ）
void Union(int S[], int Root1, int Root2){
      S[Root2] = Root1;  //  Root2      Root1  
}

 5. 트 리 와 이 진 트 리 의 활용
  1) 이 진 트 리 (BST 로 약칭) 는 이 진 트 리 라 고도 부 르 며 비어 있 거나 다음 과 같은 특성 을 가지 고 있 습 니 다.
     a) 왼쪽 트 리 가 비어 있 지 않 으 면 왼쪽 트 리 의 모든 노드 키워드 값 은 루트 노드 의 키워드 값 보다 작 습 니 다.
     b) 오른쪽 하위 트 리 가 비어 있 지 않 으 면 오른쪽 하위 트 리 의 모든 노드 키워드 값 이 루트 노드 의 키워드 값 보다 큽 니 다.
     c) 좌우 나무 자체 도 각각 이 진 트 리
  두 갈래 정렬 트 리 를 중간 순서 로 옮 겨 다 니 면 증가 하 는 질서 있 는 서열 을 얻 을 수 있 습 니 다.
  2) 두 갈래 정렬 트 리 찾기
     뿌리 결점 부터 어떤 지점 을 따라 층 층 이 아래로 찾 는 과정
  3) 삽입: 이 진 트 리 는 동적 집합 입 니 다. 트 리 의 구 조 는 한꺼번에 생 성 되 는 것 이 아니 라 찾 는 과정 에서 키워드 가 주어진 값 과 같은 노드 가 존재 하지 않 을 때 삽입 합 니 다.
     삽 입 된 새로운 결점 은 틀림없이 잎 결점 일 것 이다
  4) 이 진 트 리 정렬 트 리 삭제
  5) 이 진 트 리 의 검색 효율 분석
      높이 가 H 인 이 진 트 리 의 경우 삽입 과 삭 제 된 운행 시간 은 모두 O (H) 입 니 다. 최 악의 경우 구조 이 진 트 리 의 입력 순서 가 질서 가 있 으 면 경사 진 단일 트 리 가 형 성 됩 니 다. 이때 이 진 트 리 의 성능 이 현저히 나 빠 지고 나무의 높이 도 요소 개수 N 으로 증가 합 니 다.
    등 확률 적 인 상황 에서 높이 가 10 인 단일 트 리 를 찾 는 데 성공 한 평균 검색 길 이 는?
     ASL = （1+2+3+4+5+6+7+8+9+10）/10 = 5.5
   이 진 트 리 의 좌우 하위 트 리 의 높이 차이 가 절대 1 을 넘 지 않 는 다 면 이 나 무 를 균형 이 진 트 리 라 고 부른다.평균 검색 길이 가 O (log2n) 에 달 합 니 다.
검색 과정 을 보면 두 갈래 정렬 트 리 와 두 갈래 찾기 는 비슷 하지만 두 갈래 찾기 판정 트 리 는 유일 하고 두 갈래 정렬 트 리 는 유일 하지 않 으 며 같은 키 워드 는 삽입 순서 에 따라 다른 두 갈래 정렬 트 리 를 생 성 할 수 있다.
질서 표 가 정적 검색 표 라면 순서 표를 저장 구조 로 하고 2 분 검색 으로 검색 작업 을 수행 해 야 합 니 다. 동적 검색 표 (삽입 과 삭제 포함) 라면 이 진 정렬 트 리 를 논리 구조 로 선택해 야 합 니 다.
 6. 밸 런 스 이 진 트 리 (AVL 트 리)
   균형 인자: 왼쪽 트 리 와 오른쪽 트 리 의 높이 차 이 를 이 노드 의 균형 인자 로 정의 하면 균형 이 진 트 리 의 균형 인자 의 값 은 - 1, 0, 1 에 불과 합 니 다.
  균형 확보: 이 진 정렬 트 리 에 하나의 노드 를 삽입 (삭제) 할 때마다 먼저 삽입 경로 의 노드 가 이번 조작 으로 인해 불 균형 을 초래 했 는 지 확인 해 야 합 니 다. 불 균형 을 초래 하면 삽입 경로 에서 삽입 노드 에서 가장 가 까 운 균형 인자 의 절대 치가 1 보다 큰 결점 A 를 찾 은 다음 에 A 를 뿌리 로 하 는 하위 트 리 에 대해 이 진 정렬 트 리 특성 을 유지 하 는 전제 에서 각 결점 의 위치 관 계 를 조정 하여 다시 균형 을 이 루 도록 한다.
   메모: 매번 조정 대상 은 최소 불 균형 서브 트 리 입 니 다. 즉, 삽입 경로 에서 노드 를 삽입 하 는 가장 가 까 운 균형 인자 의 절대 값 이 1 이상 인 노드 를 뿌리 로 하 는 서브 트 리 입 니 다.
 
7. 하프 만 트 리 와 하프 만 인 코딩
   많은 실제 응용 에서 나무 에서 결점 은 종종 특정한 의 미 를 나타 내 는 수 치 를 부여 하여 이 결점 의 권리 가 된다.나무 뿌리 결점 에서 임의의 결점 까지 의 경로 길이 (지나 간 변수) 와 이 결점 의 권한 값 의 곱셈 을 이 결점 의 권한 경로 길이 라 고 한다.트 리 의 모든 잎 노드 의 대역 권 경로 길이 와 이 트 리 의 대역 권 경로 길이 WPL
  N 개의 권한 이 있 는 잎 사 귀 결점 이 있 는 이 진 트 리 중 권한 이 있 는 경로 길이 (WPL) 가 가장 작은 이 진 트 리 를 하프 만 트 리 라 고도 부 르 고 가장 좋 은 이 진 트 리 라 고도 부른다.
   하 브 만 을 구성 하 는 과정 에서 모두 N - 1 개의 결점 을 신 설 했 기 때문에 하 브 만 나무의 결점 총 수 는 2N - 1 이 고 존재 도가 1 인 결점 은 존재 하지 않 는 다.
  하프 만 인 코딩: 주파수 가 높 은 문 자 는 짧 은 인 코딩 을 부여 하고 주파수 가 낮은 문 자 는 긴 인 코딩 을 부여 하여 데 이 터 를 압축 하 는 효 과 를 낸다.
  인 코딩 이 다른 인 코딩 의 접두사 가 없다 면 이 인 코딩 을 접두사 인 코딩 이 라 고 합 니 다.예 를 들 어 0, 101 과 100,
  
   
 
다음으로 전송:https://www.cnblogs.com/--CYH--/p/6785928.html