(데이터 구조 노트) 두 갈래 찾기 트 리 의 실현

이 진 트 리 는 비교적 기본 적 인 데이터 구조 로 최적화 되면 AVL 트 리, 빨 간 검 은 나무, treap 트 리 등 비교적 효율 적 인 나무 가 될 수 있다.이 진 트 리 를 이 진 트 리 로 만 드 는 방법 은 트 리 의 모든 노드 에 대해 왼쪽 트 리 의 모든 항목 이 이 노드 보다 작 고 오른쪽 트 리 의 모든 항목 이 이 노드 보다 크다 는 것 이다.
이 진 트 리 는 재 귀 를 이용 하여 비교적 간단하게 실현 할 수 있 고 구체 적 인 정의 와 알고리즘 은 쉽게 조회 할 수 있 기 때문에 더 이상 군말 하지 않 습 니 다.
이 진 트 리 가 가 져 야 할 공유 구성원 함수 찾기:
1. contains (x): 트 리 에 x 의 노드 가 있 으 면 true 로 돌아 갑 니 다.
2. empty (): 나무 가 비어 있 으 면 true 로 돌아 갑 니 다.
3. insert (x): 트 리 의 적당 한 위치 에 x 노드 를 삽입 하고 x 가 존재 하면 아무것도 하지 않 습 니 다.
4. remove (x): 트 리 의 x 노드 를 삭제 하고 x 가 존재 하지 않 으 면 아무것도 하지 않 습 니 다.
5. findmin (): 트 리 의 최소 값 을 되 돌려 줍 니 다.
6. findmax (): 트 리 의 최대 값 을 되 돌려 줍 니 다.
7.make_empty (): 트 리 비우 기.
8.print_tree (): 트 리 의 노드 를 점차적으로 인쇄 합 니 다.
이 진 트 리 구현 프레임 워 크 찾기:

template
class BinarySearchTree{
public:
	BinarySearchTree() = default;
	BinarySearchTree(const BinarySearchTree&);
	~BinarySearchTree();
	const BinarySearchTree& operator=(const BinarySearchTree &);

	bool contains(const T&);
	bool empty();
	const T& findmin();
	const T& findmax();
	void insert(const T&);
	void remove(const T&);
	void make_empty();
	void print_tree();
private:
	struct BinaryNode {                         //   
		T element;
		BinaryNode *left;
		BinaryNode *right;
		BinaryNode(const T& elem, BinaryNode * l, BinaryNode * r) :
			element(elem), left(l), right(r) {}
	};
	BinaryNode *root;
	bool contains(const T&,BinaryNode*);
	BinaryNode * findmin(BinaryNode*);
	BinaryNode * findmax(BinaryNode*);
	void insert(const T&, BinaryNode*&);
	void remove(const T&, BinaryNode*&);
	void make_empty(BinaryNode*&);
	void print_tree(BinaryNode*);
	BinaryNode * clone(BinaryNode*);            //      
};

contains, empty 함수 의 실현
이 두 함 수 는 비교적 간단 하 다. contains 는 간단 한 호출 재 귀 검색 이다.

template
bool BinarySearchTree::contains(const T& elem) {
	return contains(elem, root);
}

template
bool BinarySearchTree::contains(const T& elem, BinaryNode * bin) {
	if (bin == nullptr)
		return false;
	if (bin->element < elem)
		return contains(elem, bin->right);
	else if (bin->element >elem)
		return contains(elem, bin->left);
	else
		return true;
}

template
bool BinarySearchTree::empty() {
	if (root == nullptr)
		return true;
	return false;
}

findmin, findmax 함수 및 printtree 함수 의 실현
앞의 두 함 수 는 재 귀 를 간단하게 이용 하여 찾 을 수 있 지만 우 리 는 재 귀 를 최대한 피해 야 하기 때문에 재 귀 호출 대신 while 문 구 를 사용 해 야 합 니 다.
또 빈 나 무 를 잘 처리 해 야 한다.

template
const T & BinarySearchTree::findmin() {
	return findmin(root)->element;
}


template typename
BinarySearchTree::BinaryNode * 
BinarySearchTree::findmin(BinaryNode *bin) {
	if (bin == nullptr)
		return nullptr;
	while (bin->left != nullptr)
		bin = bin->left;
	return bin;
}

template
const T & BinarySearchTree::findmax() {
	return findmax(root)->element;
}
template typename
BinarySearchTree::BinaryNode *
BinarySearchTree::findmax(BinaryNode* bin) {
	if (bin == nullptr)
		return nullptr;
	while (bin->right != nullptr)
		bin = bin->right;
	return bin;
}template
void BinarySearchTree::print_tree() {
	print_tree(root);
}

template
void BinarySearchTree::print_tree(BinaryNode *bin) {
	if (bin != nullptr) {
		print_tree(bin->left);
		std::cout << bin->element<		print_tree(bin->right);
	}
}

insert, remove 및 makeempty 함수 의 실현
insert 와 contains 의 사고방식 은 비교적 비슷 하 다.
reove 는 두 가지 상황 으로 나 뉜 다. 하 나 는 두 개의 키 트 리 를 가 진 노드 를 처리 하 는 것 이다. 두 가지 방식 이 있 는데 오른쪽 서브 트 리 의 최소 노드 (또는 왼쪽 서브 트 리 의 최대 노드) 를 이용 하여 이 노드 를 대체 하고 그 노드 를 재 귀적 으로 삭제 하 는 것 이다.둘째, 단자 트 리 나 무 자 트 리 의 노드 입 니 다. 자 트 리 를 이 노드 를 돌아 서 부모 노드 에 연결 한 다음 에 이 노드 를 삭제 할 수 있 습 니 다.
특히 주의해 야 할 것 은 이 세 함수 가 트 리 를 삽입 하거나 삭제 하 는 작업 을 했 기 때문에 매개 변 수 는 인용 형식 을 사용 해 야 합 니 다. 그렇지 않 으 면 오류 가 발생 할 수 있 습 니 다.

template
void BinarySearchTree::insert(const T& elem) {                 
	insert(elem,root);
}

template
void BinarySearchTree::insert(const T& elem, BinaryNode* &bin) {
	if (bin == nullptr) {
		bin = new BinaryNode(elem, nullptr, nullptr);
	}
	else if (bin->element < elem) {
		insert(elem, bin->right);
	}
	else if (bin->element > elem) {
		insert(elem, bin->left);
	}
	                             //    elem，     
}

template
void BinarySearchTree::remove(const T& elem) {
	remove(elem, root);
}

template
void BinarySearchTree::remove(const T& elem,BinaryNode* &bin) {
	if (bin == nullptr)                                       //   elem，     
		return;
	if (elem > bin->element)
		remove(elem, bin->right);
	else if (elem < bin->element)
		remove(elem, bin->left);
	else if (bin->left != nullptr && bin->right != nullptr) {   //           
		auto t = findmin(bin->right);
		bin->element = t->element;
		remove(t->element, t);
	}
	else {                                                       //          
		auto old = bin;
		bin = (bin->left != nullptr) ? bin->left : bin->right;
		delete old;
	}
}

template
void BinarySearchTree::make_empty() {
	make_empty(root);
}

template
void BinarySearchTree::make_empty(BinaryNode* &bin) {
	if (bin != nullptr) {
		make_empty(bin->left);
		make_empty(bin->right);
		delete bin;
		bin = nullptr;
	}
}

마지막 으로 복사 구조 함수, 분석 함수 와 복사 할당 연산 자 입 니 다.
clone 도구 함 수 를 사용 하여 재 귀 작업 을 실현 합 니 다.

template typename
BinarySearchTree::
BinaryNode * BinarySearchTree::clone(BinaryNode* bin) {
	if (bin == nullptr)
		return nullptr;
	return new BinaryNode(bin->element, clone(bin->left), clone(bin->right));
}

template
BinarySearchTree::
BinarySearchTree(const BinarySearchTree& bin) {
	root=clone(bin.root);                                         //         private  
}


template
inline BinarySearchTree::~BinarySearchTree() {
	make_empty();
}
template typename
const BinarySearchTree& BinarySearchTree::operator=(const BinarySearchTree & bin) {
	if (*this != bin) {
		make_empty();
		root = clone(bin.root);
	}
	return *this;
}

신출내기 하나 이 니 여러분 들 께 서 크게 의견 을 내주 시기 바 랍 니 다!