제로 부터학데이터 구조 (4) - 알고리즘 찾기, 색인, 이 진 트 리

찾기 알고리즘
 
기본 개념:
(1) 키워드: 만약 구조 가 있다 면
struct 노드 / / 하나의 노드, 데이터 와 지침 저장
{
DATA data; / 데이터 속성, 데이터 저장 에 사용
int key; / 키 가 int 값 이 라 고 가정 하면 전체 표 에서 유일한 것 입 니 다.
/ / 포인터 필드, 구체 적 으로 약 하 며, 다른 노드 나 배열 의 아래 표 시 를 가리킨다.
};
key 값 은 바로 키워드 입 니 다. 모든 노드 에 있어 서 key 값 은 다 릅 니 다. (꼭 int 값 이 어야 하 는 것 은 아 닙 니 다)따라서 데 이 터 를 찾 을 때 키 값 을 알 고 키 값 이 우리 가 찾 는 키 값 과 같 는 지 비교 하면 우리 가 찾 는 데이터 인지 아 닌 지 를 판단 할 수 있 습 니 다.
장점: ① 데이터 속성 이 변경 되 어 검색 에 영향 을 주지 않 으 며 key 값 은 변경 되 지 않 습 니 다.
단점: ① key 값 을 저장 하 는 데 더 많은 공간 이 필요 합 니 다.
 
(2) 검색 시간 복잡 도:
찾 을 때 (찾 는 것 도 하나의 알고리즘) 실행 코드 에 필요 한 시간 (몇 줄 코드 를 실행 하 는 지 이해 할 수 있 습 니 다) 을 기록 해 야 합 니 다. 이 실행 에 필요 한 시간 은 바로 알고리즘 의 시간 복잡 도 입 니 다.데이터 양 이 n 일 때 T (n) = O (f (n) 로 기록 하고 f (n) 는 데이터 양 이 n 일 때의 특정한 함 수 를 나타 낸다.
 
한편, O (f (n) 는 이 함수 가 데이터 양 이 n 일 때 알고리즘 의 시간 복잡 도 를 말한다.
 
그 는 문제 규모 n 의 증가 에 따라 알고리즘 이 실 행 된 시간의 성 장 률 을 나 타 냈 다.이렇게 알고리즘 의 복잡 도 를 대문자 O () 로 나타 내 는 기법 을 따 오기 법 이 라 고 한다.
 
일반적으로 관심 사 는 대 오기 법의 평균 시간 과 최 악의 결과 의 시간 이다.
 
그 흔히 볼 수 있 는 몇 가지 상황 은:
① 데이터 가 아무리 많 더 라 도 검색 시간 이 상수 라면 O (1) 로 기록 하여 상수 임 을 나타 낸다.
② 대수 적 성장 (데이터 가 배로 늘 어 날 때마다 횟수 가 1 회 증가) 이 라면 O (log) 로 기록 n), 대 수 를 나타 낸다.
③ 선형 성장 이 라면 O (n) 로 기록한다.
④ 만약 에 곱셈 성장 (데이터 양 과 의 관 계 는 곱셈 관계) 이 라면 O (n2) 로 기록 합 니 다.
 
(3) 표 찾기 와 찾기
탐색 표: 같은 유형의 데이터 집합 (예 를 들 어 트 리 의 결산 점 은 같은 유형 이 고 트 리 의 결산 점 의 집합 은 검색 표 입 니 다).
찾기: 특정한 값 (key) 에 따라 찾기 표 에서 항목 을 확인 합 니 다 (예 를 들 어 트 리 의 노드, 예 를 들 어 이 노드 를 가리 키 는 지침 을 얻 을 수 있 습 니 다).
 
(4) 명중
자신 이 찾 고 있 는 항목 을 찾 은 것 으로 이해 할 수 있다.
 
순서 찾기 (선형 찾기):
(1) 적용 상황:
절대 다수의 상황.
 
(2) 원리:
첫 번 째 부터 찾 고 순서대로 일치 하 는 값 을 찾 거나 마지막 항목 을 찾 을 때 까지 시도 합 니 다.
 
(3) 알고리즘 최 적 적용 상황:
① 데이터베이스 가 작다.
② 시간 에 대한 까다 로 운 요 구 는 없다.
 
(4) 알고리즘 시간 복잡 도:
O（n）
 
 
이분법 찾기:
(1) 적용 상황:
전제: key 는 질서 가 있 고 표 의 순 서 는 key 에 의 해 규정 되 며 일반적으로 변 하지 않 습 니 다. (변 하면 표 의 순 서 를 다시 정렬 해 야 합 니 다)
 
(2) 원리:
먼저 표 의 가장 중간 에 있 는 결점 m 를 찾 은 다음 에 m 의 key 값 과 찾 을 key 값 의 관 계 를 비교 하고 m. key 값 보다 크 면 m 오른쪽 (범위 가 이전 보다 반 으로 축소) 을 찾 습 니 다.m. key 보다 작 으 면 m 왼쪽 을 찾 습 니 다.m. key 값 만큼 크 면 명중 합 니 다.
코드:

Node* find(int last, int key,Node *a)	//         ，a            
{
	int f, l, m;
	f = 0;
	l = last;
	while (f <= l)	//                  
	{
		m = (f + l) / 2;
		if (key < a[m].key)	//        key  
			l = m - 1;	//     1（       ）
		else if (key>a[m].key)		//      key  
			f = m + 1;
		else
			return a;	//  
	}
	return NULL;	//     ，     
}

(2) 알고리즘 최 적 적용 상황:
질서 있 는 표, 질서 있 는 이 진 트 리, 데이터 가 많 을 때.
 
(3) 알고리즘 시간 복잡 도:
O（log n）
 
 
플러그 인 찾기:
(1) 알고리즘 원리:
키 값 과 최대, 최소 하 표 간 의 관계 에 따라 최 적 화 된 것 입 니 다.(구체 적 으로 나 도 알 아 보지 못 했다)
 
(2) 적용 상황:
키 값 이 비교적 고 른 시계.예 를 들 어 1, 2, 3, 4, 5, 6... 이렇게.극단 적 인 분포 에 적합 하지 않다 (예 를 들 어 1, 100, 500, 1000...)
 
(3) 알고리즘:

Node* find(int last, int key,Node *a)	//         ，a            
{
	int f, l, m;
	f = 0;
	l = last;
	while (f <= l)	//                  
	{
		m = l + (key - a[f].key) / (a[l].key - a[f].key)*(l - f);	//****       ****
		if (key < a[m].key)	//        key  
			l = m - 1;	//     1（       ）
		else if (key>a[m].key)		//      key  
			f = m + 1;
		else
			return a;	//  
	}
	return NULL;	//     ，     
}

 
(4) 최 적 적용 상황:
key 값 이 고 르 게 분포 되 어 있 습 니 다.
 
 
피 보 나치 찾기:
(1) 원리:
못 알 아 봤 어...좋아, 인내심 이 없어 서 보 는 거 야.
 
(2) 적용 상황:
검색 되 는 값 이 오른쪽 에 가 까 운 경우 2 분 검색 보다 효율 이 높 습 니 다.
그러나 가장 왼쪽 에 가 까 운 것 은 2 점 보다 효율 이 낮다.
 
 
 
 
색인:
색인 이란 키 값 과 키 값 이 있 는 항목 을 가리 키 는 지침 을 저장 하 는 전문 색인 표를 말한다.색인 선형 색인.
 
예 를 들 면:
색인 특징:
① 질서 있 는.데이터 항목 은 무질서 할 수 있 지만 색인 은 질서 가 있 습 니 다.따라서 데이터 항목 이 질서 가 있 든 없 든 key 값 에 맞 는 색인 항목 을 찾 으 면 색인 항목 의 지침 에 따라 가리 키 는 데이터 항목 을 찾 을 수 있 습 니 다.
 
② 질서 가 있 기 때문에 (색인 표 의 모든 질 서 를 가리 키 는 것 이 아니 므 로 2 분 검색 법 이나 다른 검색 법 을 사용 하여 요구 에 부 합 된 key 값 을 찾 을 수 있 습 니 다.
 
③ 점용 공간 이 작다.int 값 과 포인터 만 필요 할 수 있 습 니 다. 데이터 항목 에 비해 공간 이 많이 작 습 니 다.
 
④ 하지만 효율 성 이 높다.무질서 한 데이터 항목 에서 찾 으 면 기본적으로 선형 만 찾 을 수 있 지만 색인 을 이용 하여 선형 색인 (O (n) 을 이분법 검색 (O (log) 으로 바 꿉 니 다. n)), 그래서 향상 효율 이 높다.
 
 
밀도 인덱스:
(1) 정의:
선형 색인 에서 데이터 집합 에 대응 하 는 색인 항목 을 말 합 니 다.
 
(2) 특징:
① 질서 (key 값) 에 따라 배열 해 야 한다.
② 검색 효율 이 높다.
 
(3) 단점:
① 데이터 양 이 빠르게 증가 할 때 질서 있 게 배열 할 수 없다.
② 데이터 양 이 많 을 때 읽 기 가 어렵 습 니 다 (색인 항목 에 대응 하기 때문에 색인 표 도 많 습 니 다).
 
 
블록 인덱스:
(1) 정의:
데이터 세트 를 몇 조각 (몇 부분) 으로 나 눈 다음 각각 색인 항목 에 대응 합 니 다.
 
(2) 특징:
① 블록 내 는 무질서 하 다.
② 블록 간 은 질서 가 있 습 니 다 (따라서 색인 은 질서 가 있 습 니 다).
 
(3) 원리:
① 블록 내 에 순서 가 없 지만 일정한 요구 에 부합 한다. 예 를 들 어 key 값 은 일정한 범위 안에 있다.
② 블록 안에 두 개의 값 이 있 고 블록 안의 최소 key 값 과 최대 key 값 을 기록 하 는 데 사 용 됩 니 다.(따라서 다른 블록의 어떤 항목 의 값 은 반드시 이 블록의 모든 항목 의 키 값 보다 크 거나 작 을 것 이다.)
③ 색인 항목 은 현재 블록 안의 항목 수 를 기록 하 는 값 이 있 습 니 다.
④ 포인 터 는 블록의 머리 를 가리킨다 (블록의 끝 을 알 필요 가 없다. 항수 가 있 기 때문에 항수 의 수 를 찾 은 후에 자 연 스 럽 게 끝난다).
 
(4) 장점:
① 있 는 블록 을 빠르게 정 한 다음 에 하나씩 찾 을 수 있다 (이때 블록 내 항목 이 많 지 않 음). 느 리 지 않 을 것 이다.
 
 
역 인덱스:
(1) 단순 개념:
① 키워드 (이 키 워드 는 우리 가 찾 아야 할 내용, 예 를 들 어 단어) 를 설정 한 다음 에 키워드 표를 만 듭 니 다.
② 각 키워드 항목 은 하나의 배열 이 있 고 이 키워드 가 있 는 항목 의 번 호 를 기록 합 니 다 (예 를 들 어 데이터베이스 에 있 는 몇 번 째 항목 을 기록 합 니 다).
③ 키 워드 를 찾 을 때 키워드 표 에서 해당 키워드 가 있 는 항목 을 먼저 찾 을 수 있다.그리고 이 기록 의 번호 표를 찾 습 니 다.
④ 그래서 표 한 장 을 얻 었 다. 그 안에 있 는 모든 항목 은 우리 가 찾 아야 할 키 워드 를 포함한다.
⑤ 표시 되 며 검색 이 끝 납 니 다.
 
(2) 장점:
① 단 어 를 찾기 에 적합 하고 원리 가 간단 하 며 저장 공간 이 작고 응답 속도 가 빠르다.
② 키 워드 는 이니셜 로 배열 한 다음 에 같은 자모의 모든 단 어 를 같은 블록 에 넣 을 수 있 기 때문에 효율 이 높다.
③ 실제 응용 에 서 는 한 번 에 모든 것 을 표시 할 필요 가 없 기 때문에 한 번 에 여러 항목 을 읽 을 수 있 습 니 다 (예 를 들 어 배열 의 0 \ # ~ 9 \ # 항목, 다음 에 10 \ # ~ 19 \ # 항목).
 
 
 
두 갈래 정렬 트 리:
(1) 특징
이 진 트 리 형식 으로 검색 합 니 다.
2 분 검색 과 달리 2 분 검색 은 주로 배열 (아래 표 시 됨) 을 마주 하고 있 으 며, 2 차 정렬 트 리 는 배열 이 없습니다 (링크 를 사용 합 니 다).따라서 코드 를 디자인 할 때 middle = (first + last) / 2 와 같은 방법 을 사용 할 수 없습니다.
 
(2) 알고리즘: (여기 있 는 이 진 트 리 는 생각 을 바 꾸 어 다시 쓰 고 삭제 노드 를 추가 합 니 다)
볼 때 이 진 트 리 를 그 려 서 코드 사고방식 에 따라 한 번 걸 어가 면 이해 가 깊 어 집 니 다.

  ：
struct Tree
{
	data m;
	int key;
	Tree* Lchild = NULL, *Rchild = NULL;
};
  ：
bool SearchTree(Tree*T, int key, Tree*p, Tree**n)	//         T，key key，     p（   NULL），                     n
{
	if (T == NULL)	//      （    ）
	{
		*n = p;		//           ，     （   p                      ）
		return false;
	}
	else if (T->key == key)	//     key     
	{
		*n = T;		//           ，      
		return true;
	}
	else if (T->key > key)	//    
		SearchTree(T->Lchild, key, T, n);	//              ，key ，            ，  
	else
		SearchTree(T->Rchild, key, T, n);
}
   ，             ，          。

  ：
bool InsertTree(Tree*T, int key)	//   ，key         false，key          true
{
	Tree*temp = NULL, *p;
	if (!SearchTree(T, key, NULL, &temp))	//      （     ），  temp              （        ）
	{
		p = new Tree;
		p->key = key;
		if (T == NULL)	//           （      ，  T    ，    key     key
			T->key = key;
		if (p->key > temp->key)	//         key       
			temp->Rchild = p;
		else					//   （     ）
			temp->Lchild = p;
		return true;	//    ，  true
	}
	else
		return false;	//   ，      false
}
  ：   key        （         ），       key    ，  true，    false

노드 삭제:
네 가지 상황 으로 나 뉜 다.
(1) 이 결점 은 빈 결점 (삭제 하지 않 아 도 됨) 이다.
(2) 이 결점 은 왼쪽 나무 가 비어 있 고 자신의 지침 을 가리 키 며 자신의 오른쪽 나 무 를 가리킨다.
(3) 이 결점 오른쪽 나 무 는 비어 있 고 자신의 지침 을 가리 키 며 자신의 왼쪽 나 무 를 가리킨다.
(4) 이 결산 점 A 좌우 의 서브 트 리 가 모두 존재 하 므 로 왼쪽 서브 트 리 (뿌리 결산 점 B) 에서 가장 오른쪽 (또는 오른쪽 서브 트 리 에서 가장 왼쪽 을 찾 는) 결산 점 C 를 찾 은 다음 자신 을 교체 합 니 다.그리고 A 의 부 결점 은 A 의 지침 을 가리 키 고 C 를 가리 키 며 C 의 왼쪽 자 결점 지침 은 B 를 가리 키 고 B 의 오른쪽 자 결점 은 A 의 왼쪽 자 결점 을 가리킨다.
생각 은 간단 하지만 쓰기 에는 매우 어색 하 다.
나 는 정확 한 지 아 닌 지 를 확인 하지 못 하고 하 나 를 써 보 았 다.나중에 기회 가 된다 면 검증 하 세 요. 검증 이 잘못 되면 댓 글 알림 을 환영 합 니 다.

bool DeleteTree(Tree**T, int key)	//   ，    
{
	Tree*l,*r;
	 if ((*T)->key = key)	//     （    ）
	{
		delete *T;
		return true;
	}
	else
	{
		while ((*T)->key != key&&(*T)!=NULL)	//    key  ，       
		{
			l = (*T)->Lchild;
			r = (*T)->Rchild;
			if ((*T)->key > key)	//  key  
				*T = (*T)->Lchild;	//     
			else *T = (*T)->Rchild;	//  key  ，     
		}
		if(*T==nullptr)	//      ，     
			return false;
		//      key  ，    l r         
		Tree** temp;
		if (l->key == key)		//     key 
			temp = &l;	//temp       
		else temp = &r;	//  temp       
		//  *temp        （          ）
		if ((*T)->Lchild == NULL)	//       
			*temp = (*T)->Rchild;
		else if ((*T)->Rchild == NULL)
			*temp = (*T)->Lchild;
		else		//         
		{
				//          ，     （             ）
			Tree*A, *B, *C;
			C = (*temp)->Lchild;	//C           
			while (C->Rchild != NULL)
				C = C->Rchild;	//    
			//4）   A       ，    （    B）      （           ）  C，      。  A      A   ，  C，C         B，B       A     。
			A = *temp;	//A             
			*temp = C;	//                  
			B = A->Lchild;	//B A   
			if (B != C)		//   B C      
			{
				B->Rchild = C->Lchild;	//B    C   （       ）
				C->Lchild = B;	//  C    B
			}
			C->Rchild = A->Rchild;	//C    A   
			delete A;
		}
	}
}