두 갈래 검색 트 리 의 상세 한 해석 (알고리즘 서론 독서 노트)

이 진 트 리 가 뭐 예요?
이 진 트 리 의 노드 x, y 가 x 왼쪽 트 리 의 한 노드 라면 y. key < x. key. y 가 x 오른쪽 트 리 의 한 노드 라면 y. key > x. key.
이 진 트 리 의 데이터 구조

typedef int data_t;

typedef struct BST
{
	data_t  data;
	struct BST *left;
	struct BST *right;
	struct BST *parent;
}BST;

이 진 트 리 검색 트 리 의 옮 겨 다 니 기 는 간단 한 재 귀 알고리즘 을 통 해 이 진 트 리 의 모든 키 워드 를 순서대로 출력 할 수 있 습 니 다. 이 알고리즘 은 중간 순서 로 옮 겨 다 니 는 것 과 유사 합 니 다. 먼저 출력 된 뿌리 를 옮 겨 다 니 는 키 워드 는 좌우 하위 트 리 의 키워드 사이 에 있 고 나중에 뿌리 를 옮 겨 다 니 는 값 은 좌우 하위 트 리 의 값 뒤에 있 습 니 다.
다음은 이 진 트 리 의 중간 순서 로 옮 겨 다 니 는 재 귀 알고리즘 과 비 재 귀 알고리즘 입 니 다.
주의: x 가 n 개의 결점 나무의 뿌리 라면 이 나 무 를 옮 겨 다 니 는 데 O (n) 시간 이 필요 합 니 다.
이 진 트 리 조회
우 리 는 항상 두 갈래 검색 트 리 에 저 장 된 키 워드 를 찾 아야 한다.search 작업 외 에 도 minnum, maxim, successor (후계 노드 구하 기), predecessor (전구 결점) 와 같은 조회 작업 도 지원 합 니 다.
트 리 찾기
트 리 뿌리 노드 를 가리 키 는 포인터 와 키워드 k 를 입력 하 십시오. 이 점검 이 존재 한다 면 bstsearch 키워드 k 를 가리 키 는 노드 의 지침 을 되 돌려 줍 니 다. 그렇지 않 으 면 NULL 로 돌아 갑 니 다.
다음은 트 리 찾기 의 재 귀적 실현 과 교체 실현 입 니 다.

void bst_nonrecur_inorder(BST *root)//use stack to store tree's node 
{
	stack<BST *> s_bst;	
	while(s_bst.size() || root!=NULL)
	{
		if(root!=NULL)
		{
			s_bst.push(root);
			root = root->left;
		}
		else
		{
			root = s_bst.top();
			s_bst.pop();
			cout << root->data << " ";
			root = root->right;
		}
	}
}

void bst_inorder(BST *root)
{
	if(root==NULL)	
		return ;
	else
	{
		bst_inorder(root->left);
		cout << root->data << " ";
		bst_inorder(root->right);
	}
}

최대 키워드 요소 와 최소 키워드 요소
나무 뿌리 부터 left 아이 지침 을 따라 한 노드 의 left 지침 이 NULL 이 될 때 까지 이 노드 의 값 은 이 두 갈래 로 트 리 를 검색 하 는 가장 작은 키워드 입 니 다.마찬가지 로 나무 뿌리 에서 right 아이 지침 을 따라 한 노드 의 right 지침 이 NULL 일 때 까지 이 노드 의 값 은 이 두 갈래 로 트 리 를 검색 하 는 가장 큰 키워드 입 니 다.
다음은 구현 코드 입 니 다.
4. 567913. 주, 상기 두 알고리즘 의 시간 복잡 도 는 모두 O (logn) (n 은 지 는 노드 의 개수) 이다.
 노드 의 선구자 와 후계
이 진 트 리 를 검색 하 는 노드 를 지정 합 니 다. 중간 순서 로 그 뒤 를 찾 아야 할 때 가 있 습 니 다.모든 키워드 가 서로 다 르 면 한 노드 x 의 후계 가 x. key 보다 큰 최소 키워드 의 노드 입 니 다.
전구 찾기 과정 은 두 부분 으로 나 뉜 다. 1. x 의 오른쪽 트 리 가 비어 있 지 않 으 면 x 의 후계 가 x 오른쪽 트 리 의 가장 왼쪽 노드 이다.2. 만약 에 x 의 오른쪽 나무 가 비어 있 고 후계 노드 y 가 있다 면 y 는 최 하층 조상 이 고 왼쪽 아이 도 조상 이다.y 를 찾기 위해 서 는 x 부터 나 무 를 따라 올 라 가면 부모 가 왼쪽 아이 가 있 는 노드 를 만 났 다 는 것 을 알 수 있다.
노드 의 앞 구 리 를 찾 으 려 면 먼저 x 노드 의 왼쪽 나무 가 비어 있 는 지, 비어 있 지 않 으 면 앞 구 리 는 왼쪽 나무의 가장 오른쪽 노드 이 고, 비어 있 으 면 x 가 나 무 를 따라 올 라 갈 때 까지 부모 가 오른쪽 아이의 노드 를 만 날 때 까지 이 노드 는 x 의 전구 결점 이다.
다음은 구현 코드 입 니 다.

//search a node in the binary-search-tree
BST *bst_search(BST *root, data_t data)
{
	if(root==NULL || root->data== data)
		return root;
	if(data<root->data)
		return bst_search(root->left, data);
	else
		return bst_search(root->right, data);
}

BST *bst_iterative_search(BST *root, data_t data)
{
	if(root==NULL || root->data == data)
		return root;
	while(root!=NULL && data!=root->data)
	{
		if(data<root->data)
			root = root->left;
		else if(data>root->data)
			root = root->right;
	}
	return root;
}

트 리 삽입 및 삭제  트 리 의 삽입 과 삭제 작업 은 이 진 트 리 가 표시 하 는 동적 집합 변 화 를 일 으 킬 수 있 습 니 다. 반드시 데이터 구 조 를 수정 하여 이 변 화 를 반영 해 야 하지만 수정 은 이 진 트 리 검색 트 리 의 성질 을 유지 해 야 합 니 다.
  끼어들다
이 진 트 리 T 에 새 값 을 삽입 하려 면 bst 를 호출 해 야 합 니 다.insert。이 함 수 는 키워드 v 를 입력 하여 함수 구조 노드 node 에서 node - > left = NULL, node - > right = NULL 을 입력 합 니 다.
삽입 과정: 트 리 뿌리 부터 포인터 node 는 아래 의 간단 한 길 금 을 기록 하고 새 노드 insert 를 교체 할 NULL 을 찾 습 니 다. tmo 를 node 로 유지 하 는 부모 입 니 다.
 

//return the minnest node of tree
BST *bst_mininum(BST *root)
{
	if(root == NULL)
		return NULL;
	while(root->left!=NULL)
		root = root->left;
	return root;
}

//return the maxest node of tree
BST *bst_maxinum(BST *root)
{
	if(root == NULL)
		return NULL;
	while(root->right!=NULL)
		root = root->right;
	return root;
}

트 리 삭제
두 갈래 검색 트 리 T 에서 노드 z 를 삭제 합 니 다. 이 과정 은 루트 와 삭제 할 노드 노드 노드 노드 노드 를 가리 키 는 것 에 달 려 있 습 니 다. 다음은 이 과정의 네 가지 상황 입 니 다.
 1. node 에 왼쪽 아이 가 없 으 면 오른쪽 아이 가 node 를 교체 합 니 다. 이 오른쪽 아 이 는 NULL 일 수도 있 고 아 닐 수도 있 습 니 다.
 2. node 가 한 노드 만 있 고 이 노드 가 왼쪽 아이 라면 왼쪽 아이 로 node 를 교체 합 니 다.
 3. 그렇지 않 으 면 node 는 왼쪽 아이 도 있 고 오른쪽 아이 도 있 습 니 다. node 의 후계 y 를 찾 아야 합 니 다. 이 후 계 는 node 의 오른쪽 나무 에 있 고 왼쪽 아이 도 없습니다. 지금 은 y 를 원래 의 위 치 를 제거 하고 연결 하 며 나무의 node 를 교체 해 야 합 니 다.
 3.1. y 가 z 의 node 오른쪽 아이 라면 y 로 node 를 교체 합 니 다.
 3.2 그렇지 않 으 면 y 는 z 의 오른쪽 나무 에 있 지만 z 의 오른쪽 아이 가 아니다. 이런 상황 에서 Y 의 오른쪽 아이 로 y 를 교체 한 다음 에 y 로 node 를 교체 한다 (마지막 절 차 는 3.1 과 같다).
 이 진 트 리 에서 하위 트 리 를 이동 하기 위해 함수 bst 를 정의 합 니 다.transplant, 차 가운 나무 로 글자 수 를 바 꾸 어 부모 의 아이 노드 가 됩 니 다.다음은 v 를 뿌리 로 하 는 나무 로 u 를 뿌리 로 하 는 나 무 를 교체 하 는 것 이다. 노드 u 의 부 모 는 노드 v 의 부모 가 되 고 마지막 에 v 는 u 의 부모 가 되 는 해당 아이 가 된다.

BST *bst_successor(BST *node)
{
	if(node == NULL)
		return NULL;
	if(node->right!=NULL)	//find successor in the leftest of the right subtree
		return bst_mininum(node->right);
	//else find it a node leftSubTree from his parent
	BST *y = node->parent;
	while(y!=NULL && node==y->right)
	{		
		node = y;
		y = y->parent;
	}
	return y;
}

BST *bst_predecessor(BST *node)
{
	if(node == NULL)
		return NULL;
	if(node->left!=NULL)
		return bst_maxinum(node->left);
	BST *y = node->parent;
	while(y!=NULL && node==y->left)
	{
		node = y;
		y = y->parent;
	}
	return y;
}

//insert a node into a binary-search-tree
BST *bst_insert(BST *root, data_t data)
{
	BST *insert = NULL, *node = NULL, *tmp = NULL;
	insert = bst_newnode(data);  //make a node to insert 
 
	node = root;
	while(node)    //find pos to insert
	{
		tmp = node;
		if(data < node->data)
			node = node->left;
		else
			node = node->right;
	}

	insert->parent = tmp;
	if(tmp==NULL)    //tree root is empty
		root = insert;
	else 
	{
		if(data < tmp->data) 
			tmp->left = insert;
		else
			tmp->right = insert;
	}
	
	return root;
}

트 리 삭제 코드 는 다음 과 같 습 니 다.

//replace subtree of u with subtree of v
BST *bst_transplant(BST *root, BST *u, BST *v)
{
	if(u->parent==NULL)   //u is root 
		root = v;
	else if(u->parent->right == u)  // u is his parent's right subtree
			u->parent->right = v;
	else	u->parent->left = v;   //u is his parent's left subtree
	if(v!=NULL)   //set v's parent
		v->parent = u->parent;
	return root;
}