두 갈래 검색 트 리 의 기본 동작
이 진 트 리 가 뭐 예요?
먼저 이 진 트 리 (5 가지 형태) 입 니 다. 그 다음 에 이 진 트 리 의 키 워드 는 이 진 트 리 를 검색 하 는 방식 으로 저장 합 니 다. x 는 이 진 트 리 에 있 는 것 입 니 다. 하나의 결점, y 가 x 왼쪽 나무 중의 결점 이 라면 y .key <= x.key;y 가 x 오른쪽 트 리 의 결점 이 라면 y. key >= x.key。
K 대 수 를 찾 는 것 을 제외 하고 다른 복잡 도 는 모두 0 (h) 급 이다.
1. 두 갈래 검색 트 리 옮 겨 다 니 기:
보통 이 진 트 리 는 특수 한 이 진 트 리 이기 때문에 옮 겨 다 니 는 것 이 똑같다.특히 이 진 트 리 의 순 서 를 검색 합 니 다. LVR 결 과 는 원소 에 대한 어 릴 때 부터 큰 순서 다. RVL 은 크 고 작은 순서 다.
[증명]
트 리 가 비어 있 으 면 값 x 를 넣 고 중간 순서에 따라 출력 합 니 다. 질서 가 서다.
비어 있 지 않 고 n 개의 요소 가 있 으 면 질서 성 을 고려 하지 않 으 면 넣 을 수 있 는 위 치 는 n + 1 개 이지 만 이 진 트 리 의 성질 을 검색 하기 때문에 한 위치 에 만 삽입 할 수 있 습 니 다. 만약 이 위치 가 특정한 노드 y 의 오른쪽 아들 이 라면 (가짜)
아들 을 좌우 하지 않 는 다) 그러면 y 는 이 요소 에서 가장 작은 점 보다 크 고 반대로 같은 이치 이다.
<span style="font-size:18px;">void SortPriont(SeachTree *ST)//
{
if(ST == NULL) return ;
SortPriont(ST->Right);
printf("%d ",ST->Data);
SortPriont(ST->Left);
}
void SortPriont(SeachTree *ST)//
{
if(ST == NULL) return ;
SortPriont(ST->Left);
printf("%d ",ST->Data);
SortPriont(ST->Right);
} </span>2. 두 갈래 검색 트 리 의 경 로 를 옮 겨 다 니 기:
어떤 점 에서 시작 하여 매번 왼쪽 아이 와 오른쪽 아이 중 하나 만 옮 겨 다 니 면 하나의 경로 가 된다.
이 진 트 리 의 임의의 경 로 를 검색 할 때 부모 노드 가 왼쪽 아 이 를 방문 하면 이 경로 에서 이 부모 노드 이후 모든 노드 의 키 워드 는 부모 노드 키워드 보다 작 습 니 다. 오른쪽 아 이 를 방문 할 때 반대 입 니 다.그러나 이 경로 이외 의 결점 은 경로 상의 결점 키워드 와 아무런 관계 가 없다. 이것 은 두 갈래 검색 트 리 의 성질 에 의 해 결정 된다.
만약 임의의 점 에서 잎의 결점 까지 간다 면, 전체 경 로 는 NULL 로 끝난다.
(1) 어떤 키워드 가 존재 하 는 지 찾 습 니 다.
<span style="font-size:18px;">// ， ， NULL。
SeachTree *Find(ElementType item,SeachTree *ST)
{
//
/*if(ST==NULL||ST->Data == item) return ST;// NULL
if(ST->Data < item) return Find(item,ST->Right);
else return Find(item,ST->Left);*/
//
if(ST==NULL||ST->Data == item) return ST;
else
{
SeachTree *temp = ST;
while(temp!=NULL)
{
if(temp->Data == item ) return temp;
else
if(temp->Data < item ) temp = temp->Right;
else temp = temp->Left ;
}
return temp;// ， temp null。
}
}</span>(2) 최대 (작은) 키 찾기:
어떤 부모 노드 가 왼쪽 아 이 를 방문 하면 이 경로 에서 이 부모 노드 이후 의 모든 노드 의 키 워드 는 부모 노드 의 키워드 보다 작다 고 생각 하기 때문에 경로 의 모든 노드 가 왼쪽 아 이 를 방문 하면 마지막 하 나 는 가장 작고 이 경 로 는 큰 것 에서 작은 순서 로 생 긴 다.
<span style="font-size:18px;">SeachTree *FindMin(SeachTree *ST)
{
//
/*if(ST->Left==NULL) return ST;
return FindMin(ST->Left);*/
//
SeachTree *temp=ST;
while(temp->Left!=NULL)
{
temp=temp->Left;
}
return temp;
}</span>가장 작은 동 리 를 찾다.
(3) 전구 와 후계: (모든 이 진 트 리 에 적용)
여기 서 의 전구 후 계 는 중 서 를 옮 겨 다 니 는 것 에 비해 서 말 하기 때문에 하나의 결점 x 의 후 계 는 x. key 에서 가장 작은 키워드 의 결점 보다 크 고 앞 구 는 x. key 에서 가장 큰 키워드 의 결점 으로 후 계 를 구 하 는 것 을 예 로 들 수 있다.
경계 점 을 제외 하고 모든 결점 은 두 개의 신분 이 있 는데 하 나 는 특정한 요소 의 후계 이 고 하 나 는 특정한 요소 의 선구자 이다.만약 x 결점 에 오른쪽 아들 이 있다 면 그 다음은 오른쪽 나무 에서 가장 작은 키워드 의 결점 이다.동시에 이 결점 의 앞 구 는 x 이다.만약 에 x 결점 에 오른쪽 아들 이 없다 면 x 의 후계 자 는 반드시 조상 중의 한 요소 이다. 이 요소 의 왼쪽 나무 최대 치 는 x 이다. 즉, x 의 후계 가 바로 이 조상 이 고 이 조상 은 x 이다.
그래서 이 조상 은 반드시 밑바닥 에 나 타 났 을 것 이다. 그러나 왼쪽 나무 도 x 조상의 조상 (x 자체 도 자신의 조상) 이다.특히 경계 점 에 대한 처 리 를 주의해 야 한다. 즉, 왼쪽 경계 점 의 앞 구 는 NULL 이 고 오른쪽 노드 의 뒤 계 는 NULL 이다.
전구 와 후 계 를 구 하 는 것 도 특정한 경 로 를 찾 는 과정 이다. 다만 이 경로 의 단점 은 요소 가 비교적 특수 하고 경 로 를 제한 할 뿐이다.
<span style="font-size:18px;">SeachTree *SuccessOR(SeachTree *ST,ElementType item)//
{
SeachTree *key = Find(item,ST);
if(key == NULL) return NULL;
if(key->Right != NULL)
{
return FindMin(key->Right);
}
else
{
SeachTree *keyparent = key->parent;
if(keyparent != NULL && keyparent->Right == key)
{
key = keyparent;
keyparent = keyparent->parent;
}
return keyparent;
}
}
SeachTree *PredecessOR(SeachTree *ST,ElementType item)//
{
SeachTree *key = Find(item,ST);
if(key == NULL) return NULL;
if(key->Left != NULL)
{
return FindMax(key->Left);
}
else
{
SeachTree *keyparent = key->parent;
if(keyparent!=NULL && keyparent->Left == key)
{
key = keyparent;
keyparent = keyparent->parent;
}
return keyparent;
}
}</span>(4) K 번 째 숫자 찾기:
그냥 FindMin 으로. *ST) 함수 에서 최소 값 을 찾 은 다음 Successor (SeachTree) 를 순서대로 사용 합 니 다. *ST,ElementType 아 이 템) 후 계 를 찾 는 과정 에서 K - 1 후 계 를 찾 습 니 다.시간 복잡 도 는 0 (K + h) 이다.
<span style="font-size:18px;">SeachTree * FindKNumber(SeachTree *ST, int k)// k
{
k--;
SeachTree *N = FindMin(ST);
while(k--)
{
N= SuccessOR(ST,N->Data);
}
return N;
}</span>3. 두 갈래 검색 트 리 의 삽입:
어떤 키 워드 를 찾 으 려 면 그 경로 뒤에 놓 아야 합 니 다.
<span style="font-size:18px;">SeachTree *Insert(SeachTree *ST, ElementType item)
{
SeachTree *pNew = NULL;
pNew = (SeachTree *)malloc(sizeof(SeachTree));
pNew->Data = item;
pNew->Left = pNew->parent = pNew->Right = NULL;
if(ST==NULL)//
{
ST = pNew;
}
else
{
SeachTree **temp = &ST,*parent=NULL;
while(*temp!=NULL)
{
parent = *temp;
if((*temp)->Data <= item) temp = &(*temp)->Right;
else temp = &(*temp)->Left;
}
pNew->parent = parent;
*temp = pNew;
}
return ST;
}</span>4. 두 갈래 검색 트 리 의 삭제 작업:
이 진 트 리 삭제 의 가장 근본 적 인 것 은 노드 를 삭제 한 후에 전구 나 후계 노드 를 재 귀적 으로 대체 하여 '삭제' 작업 이 필요 하지 않 을 때 까지 하 는 것 이다.중간 순 서 를 옮 겨 다 니 는 것 은 삭 제 된 전 (후) 요 소 를 한 단 위 를 앞으로 (뒤로) 이동 하 는 것 입 니 다.
한 노드 를 삭제 하 는 작업 은 여러 가지 선택 에 대응 할 수 있 지만 나무의 형태 에 따라 가장 좋 은 비빔밥 이나 조작 이 편리 한 방법 이 있다.(삭 제 된 노드 를 루트 노드 로 가정 합 니 다)
빈 나무 판단 후 아무런 처리 도 하지 않 고 바로 돌아 갑 니 다.
2. 하나의 노드 만 있 는 트 리: 삭제 후 바로 NULL 34 상황 으로 요약 할 수 있 습 니 다.
3. 한 개의 노드 와 한 명의 왼쪽 아이 만 있 습 니 다. 이론 적 으로 후계 (최저 조상 왼쪽 아 이 는 조상) 를 삭제 위치 에 놓 거나 전구 (왼쪽 나무 최대 치) 를 삭제 노드 에 놓 거나 왼쪽 나 무 를 삭제 열 점 으로 옮 긴 다음 에 조정 할 수 있 습 니 다.상기 세 가지 방법 중 가장 간단 한 것 은 마지막 이다.
4. 단 하나의 노드 와 오른쪽 아들: 동상
5. 뿌리 노드 와 좌우 두 아들 이 있 습 니 다. 네 가지 방식 으로 이 루어 질 수 있 습 니 다. 여 기 는 생략 하지만 가장 간단 한 것 은 오른쪽 나무 에서 가장 작은 요 소 를 찾 은 다음 에 삭 제 된 요 소 를 대체 한 다음 에 조정 합 니 다.
(찾 은 최소 요소 가 오른쪽 하위 트 리 의 뿌리 노드 라면 직접 위로 이동 하여 대체 합 니 다. 그렇지 않 으 면 최소 값 을 삭제 하 는 작업 을 추가 해 야 합 니 다)
<span style="font-size:18px;">void Transplant(SeachTree **ST,SeachTree *u,SeachTree *v)// u = v v NULL u
{
if(u->parent == NULL)
{
*ST = v;
}
else
{
if(u->parent->Left == u)
{
u->parent->Left = v;
}
else
if(u->parent->Right == u)
{
u->parent->Right = v;
}
}
if(v != NULL)
v->parent = u->parent;
}
ElementType Delete(SeachTree **ST,ElementType item)
{
SeachTree *z =Find(item,*ST);
if(z==NULL) return NULL;
if(z->Left == NULL)//
{
Transplant(ST,z,z->Right);
}
else
if(z->Right == NULL)//
{
Transplant(ST,z,z->Left);
}
else//
{
SeachTree * y= FindMin(z->Right);//
if(y->parent != z)
{
Transplant(ST,y,y->Right);
y->Right = z->Right;
y->Right->parent = y;
}
Transplant(ST,z,y);
y->Left = z->Left;
y->Left->parent = y;
}
free(z);
}</span>전체 코드:
<span style="font-size:18px;">/**************************************************************
project ：
author ：wmaoshu
Email ：[email protected]
time ：2015/11/01
***************************************************************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef int ElementType;
struct TreeNode{
ElementType Data;
struct TreeNode *Left;
struct TreeNode *Right;
struct TreeNode *parent;
};
typedef struct TreeNode SeachTree;
//=================================================
SeachTree *Find(ElementType item,SeachTree *ST);
SeachTree *FindMax(SeachTree *ST);
SeachTree *FindMin(SeachTree *ST);
SeachTree *SuccessOR(SeachTree *ST,ElementType item);
SeachTree *PredecessOR(SeachTree *ST,ElementType item);
SeachTree *Insert(SeachTree *ST, ElementType item);
ElementType Delete(SeachTree **ST,ElementType item);
void SortPriont(SeachTree *ST);
//
/***********************************************************
max
min
（ ）
************************************************************/
SeachTree *Find(ElementType item,SeachTree *ST)
{
//
/*if(ST==NULL||ST->Data == item) return ST;
if(ST->Data < item) return Find(item,ST->Right);
else return Find(item,ST->Left);*/
//
if(ST==NULL||ST->Data == item) return ST;
else
{
SeachTree *temp = ST;
while(temp!=NULL)
{
if(temp->Data == item ) return temp;
else
if(temp->Data < item ) temp = temp->Right;
else temp = temp->Left ;
}
return temp;
}
}
SeachTree *FindMax(SeachTree *ST)
{
//
/*if(ST->Right==NULL) return ST;
return FindMax(ST->Right);*/
//
SeachTree * temp = ST;
while(temp->Right!=NULL)
{
temp=temp->Right;
}
return temp;
}
SeachTree *FindMin(SeachTree *ST)
{
//
/*if(ST->Left==NULL) return ST;
return FindMin(ST->Left);*/
//
SeachTree *temp=ST;
while(temp->Left!=NULL)
{
temp=temp->Left;
}
return temp;
}
//
SeachTree *SuccessOR(SeachTree *ST,ElementType item)//
{
SeachTree *key = Find(item,ST);
if(key == NULL) return NULL;
if(key->Right != NULL)
{
return FindMin(key->Right);
}
else
{
SeachTree *keyparent = key->parent;
// NULL ， keyparent NULL
if(keyparent != NULL && keyparent->Right == key)
{
key = keyparent;
keyparent = keyparent->parent;
}
return keyparent;
}
}
SeachTree *PredecessOR(SeachTree *ST,ElementType item)//
{
SeachTree *key = Find(item,ST);
if(key == NULL) return NULL;
if(key->Left != NULL)
{
return FindMax(key->Left);
}
else
{
SeachTree *keyparent = key->parent;
if(keyparent!=NULL && keyparent->Left == key)
{
key = keyparent;
keyparent = keyparent->parent;
}
return keyparent;
}
}
//
SeachTree *Insert(SeachTree *ST, ElementType item)
{
SeachTree *pNew = NULL;
pNew = (SeachTree *)malloc(sizeof(SeachTree));
pNew->Data = item;
pNew->Left = pNew->parent = pNew->Right = NULL;
if(ST==NULL)
{
ST = pNew;
}
else
{
SeachTree **temp = &ST,*parent=NULL;
while(*temp!=NULL)
{
parent = *temp;
if((*temp)->Data <= item) temp = &(*temp)->Right;
else temp = &(*temp)->Left;
}
pNew->parent = parent;
*temp = pNew;
}
return ST;
}
//
void Transplant(SeachTree **ST,SeachTree * key, SeachTree *newkey)
{
if(key->parent==NULL) *ST=newkey;
else
if(key->parent->Left==key) key->parent->Left = newkey;
else key->parent->Right=newkey;
if(newkey!=NULL) newkey->parent = key->parent;
}
ElementType Delete(SeachTree **ST,ElementType item)
{
SeachTree *key = Find(item,*ST);
if(key->Left == NULL)
{
Transplant(ST,key,key->Right);
}
else
if(key->Right == NULL)
{
Transplant(ST,key,key->Left);
}
else
{
SeachTree * newkey = FindMin(key->Right);
if(newkey->parent!=key)
{
Transplant(ST,newkey,newkey->Right);
newkey->Right = key->Right;
newkey->Right->parent = newkey;
}
Transplant(ST,key,newkey);
newkey->Left = key->Left;
newkey->Left->parent = newkey;
}
}
//
/*************************************************************
： ， x， 。
， n ， n+1
， ，
y ， y x ， 。
*************************************************************/
void SortPriont(SeachTree *ST)//
{
if(ST == NULL) return ;
SortPriont(ST->Left);
printf("%d ",ST->Data);
SortPriont(ST->Right);
}
//==================================================
int main(void)
{
return 0;
}
</span>이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
