Algorithm Design - Tree

---

Tree

우선 트리구조를 가볍게 살펴보자. 이미 자료구조론 수업에서 다뤘던 내용이기 때문에 간단하게만 살펴보려한다.

Tree terminology
1. 루트(Root): 부모가 없는 노드 (A)
2. 자식(Child): 노드 u가 노드 v의 부모라면, v는 u의 자식입니다.
3. Siblings: 같은 부모를 가진 노드들
4. Internal node: 적어도 하나의 자식을 가진 노드 (A, B, C, F)
5. Leaf node: 자식이 없는 노드 (E, I, J, K, G, H, D)
6. 노드의 깊이(Depth of a node): ancestor의 수
7. Height of a tree: 어떤 노드의 최대 깊이
8. 차수(Degree): 노드의 자식 수

 

Traversal 종류
Preorder (전위 순회)
    - 순회 순서: 루트 -> 왼쪽 자식 -> 오른쪽 자식
    - 전위 순회는 루트 노드를 먼저 방문하고, 그 다음에 왼쪽 서브트리, 그리고 오른쪽 서브트리를 순회하다.
    - 예를 들어, 루트 노드 A, 왼쪽 자식 노드 B, 오른쪽 자식 노드 C가 있다면, 순회 순서는 A -> B -> C 이다.
    - 이 순회 방식은 트리의 복사본을 만들거나 트리를 표현하는 표현식을 만드는 데 유용하다.

Preorder(node)
1. if node == null then return
2. 방문(node)출력
3. Preorder(node.left)
4. Preorder(node.right)

Inorder (중위 순회)
    - 순회 순서: 왼쪽 자식 -> 루트 -> 오른쪽 자식
    - 중위 순회는 먼저 왼쪽 서브트리를 방문하고, 그 다음에 루트 노드, 그리고 마지막으로 오른쪽 서브트리를 순회한다.
    - 예를 들어, 루트 노드 A, 왼쪽 자식 노드 B, 오른쪽 자식 노드 C가 있다면, 순회 순서는 B -> A -> C 이다.
    - 이진 탐색 트리에서 중위 순회를 사용하면 오름차순으로 노드를 방문할 수 있다.

Inorder(node)
1. if node == null then return
2. Inorder(node.left)
3. 방문(node)출력
4. Inorder(node.right)

Postorder (후위 순회)
    - 순회 순서: 왼쪽 자식 -> 오른쪽 자식 -> 루트
    - 후위 순회는 왼쪽 서브트리를 방문한 다음, 오른쪽 서브트리를 방문하고, 마지막으로 루트 노드를 방문한다.
    - 예를 들어, 루트 노드 A, 왼쪽 자식 노드 B, 오른쪽 자식 노드 C가 있다면, 순회 순서는 B -> C -> A 이다.
    - 후위 순회는 트리의 노드를 삭제하거나 트리의 후위 표현을 만들 때 유용하다.

Postorder(node)
1. if node == null then return
2. Postorder(node.left)
3. Postorder(node.right)
4. 방문(node)출력

---

BST

BST는 Binary Search Tree(이진 탐색 트리)의 약자로 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 특성을 가진 이진 트리의 일종이다.
BST는 데이터를 정렬된 상태로 저장하여 효율적인 검색, 삽입, 삭제를 가능하게 한다. 트리의 각 노드는 키(key)를 가지고 있으며, 모든 노드는 다음과 같은 특성을 만족해야 한다.(어떤 노드의 왼쪽 서브트리에 있는 모든 노드의 값은 해당 노드의 값보다 작아야 하고, 오른쪽 서브트리에 있는 모든 노드의 값은 해당 노드의 값보다 커야 하고, 각 서브트리도 이진 탐색 트리여야 한다.)

Node

struct Node {
	int data;
	//부모 노드
	Node* parent;
	//왼쪽 자식 노드
	Node* leftChild;
	//오른쪽 자식 노드
	Node* rightChild;
};

BST

class binarySearchTree {
private:
	Node* root;
public:
	binarySearchTree() {
		root = nullptr;
	}
	void insert(int elem);
	Node* find(int elem);
	void swap(Node* a, Node* b);
	void erase(int elem);
    void erase(Node* node);
	void print(Node* node);
	Node* getRoot();

};

 

Search

	Node* curNode = root;
	//트리가 비어있다면 nullptr반환
	if (curNode == nullptr) {
		return nullptr;
	}
	while (1) {
		//현재 찾는값이 curNode가 가리키는 데이터값보다 작으면
		while (curNode->data > elem) {
			//왼쪽 자식노드로 
			curNode = curNode->leftChild;
		}
		//찾는 값이 curNode가 가리키는 데이터값보다 같거나 크면
		while (curNode->data <= elem) {
			//elem값을 찾았다면 해당 노드 반환
			if (curNode->data == elem) {
				return curNode;
			}
			//못찾았다면 오른쪽 노드로
			curNode = curNode->rightChild;
		}
        //만약 curNode가 nullptr이라면 elem값은 존재하지 않으므로
		if (curNode == nullptr) return nullptr;
	}

 

Insertion

void binarySearchTree::insert(int elem) {
	//새로 삽입할 노드
	Node* addNode = new Node;
	//맨처음 삽입이라면 루트에 넣어주기
	if (root == nullptr) {
		addNode->data = elem;
		addNode->parent = nullptr;
		addNode->leftChild = nullptr;
		addNode->rightChild = nullptr;
		root = addNode;
		return;
	}

	//현재 노드를 가리키는 노드(초기값 root노드)
	Node* curNode = root;
	while (1) {
		//인풋값이 현재 curNode가 가리키는 노드의 데이터값보다 작다면
		while (curNode->data > elem) {
			//curNode의 왼쪽자식이없다면 
			if (curNode->leftChild == nullptr) {
				//curNode의 왼쪽자식노드값 설정해주고 부모 자식값 다시설정
				addNode->data = elem;
				addNode->parent = curNode;
				addNode->leftChild = nullptr;
				addNode->rightChild = nullptr;
				curNode->leftChild = addNode;
				return;
			}
			//왼쪽 자식이 존재하면
			else {
				//curNode가 자신의 왼쪽 자식노드를 참조하게함
				curNode = curNode->leftChild;
			}
		}
		//인풋값이 curNode가 가리키는 노드의 데이터값보다 같거나 크면 
		while (curNode->data <= elem) {
			//오른쪽자식값이 없다면 해당 자식노드에 추가
			if (curNode->rightChild == nullptr) {
				addNode->data = elem;
				addNode->parent = curNode;
				addNode->leftChild = nullptr;
				addNode->rightChild = nullptr;
				curNode->rightChild = addNode;
				return;
			}
			//오른쪽 자식 존재하면 오른쪽 자식 노드 참조하게함
			else {
				curNode = curNode->rightChild;
			}
		}
	}

}

 

Deletion

void binarySearchTree::erase(int elem) {
	Node* delNode = find(elem);
	//BST에 해당 원소 없다면 바로 종료
	if (delNode == nullptr) {
		return;
	}
	//해당 원소가 리프 노드라면 
	if (delNode->leftChild == nullptr && delNode->rightChild == nullptr) {
		//해당 원소의 부모노드에서 해당 원소 제거
		if (delNode->parent->leftChild == delNode) delNode->parent->leftChild = nullptr;
		else delNode->parent->rightChild = nullptr;
	}
	//해당원소가 오른쪽 자식만 있을 때
	else if (delNode->leftChild == nullptr) {
		//만약 del노드가 del의 부모노드의 왼쪽자식이라면
		if (delNode->parent->leftChild == delNode) {
			delNode->parent->leftChild = delNode->rightChild;
		}
		//del노드가 부모노드의 오른쪽자식이라면
		else {
			delNode->parent->rightChild = delNode->rightChild;
		}
		//해당원소의 오른쪽자식의 부모노드를 해당원소의 부모노드로 설정
		delNode->rightChild->parent = delNode->parent;
	}
	//해당원소가 왼쪽 자식만 있을 때
	else if (delNode->rightChild == nullptr) {
		//del노드가 부모 노드의 왼쪽자식이라면
		if (delNode->parent->leftChild == delNode) {
			//부모노드의 왼쪽 자식을 해당원소의 왼쪽 자식으로 설정
			delNode->parent->leftChild = delNode->leftChild;
		}
		else {
			delNode->parent->rightChild = delNode->leftChild;
		}
		//해당원소의 왼쪽자식의 부모노드를 해당원소의 부모노드로 설정
		delNode->leftChild->parent = delNode->parent;
	}
	//해당 원소가 두 자식 다 있을 때 오른쪽 서브트리에서 제일 작은값과 교체
	else {
		//오른쪽 서브트리의 루르노드부터 시작해서
		Node* curNode = delNode->rightChild;
		//오른쪽 서브트리의 제일 작은 노드까지 
		while (curNode->leftChild != nullptr) {
			curNode = curNode->leftChild;
		}
		//두 노드를 바꿔주고
		swap(curNode, delNode);
		//해당 원소의 부모노드에서 해당 원소 제거
		if (delNode->parent->leftChild == delNode) delNode->parent->leftChild = nullptr;
		else delNode->parent->rightChild = nullptr;
	}
	delete(delNode);
}

---