[C++] 이진탐색트리(binary Search Tree) 구현

jh Seo·2023년 2월 16일

자료구조 구현

목록 보기

6/6

개요

이진탐색트리에 관해 공부하다가 호기심이 생겨
int형에서만 동작하는 기초적인 이진탐색트리를 구현해봤다.

Node 구조체

기본적으로 모든 데이터는 노드 구조체에 저장되어 있다.

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

binarySearchTree 클래스

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();

};

binarySearchTree::insert함수

void 형으로 bst에 새로운 노드를 삽입하는 함수이다.

bst가 비어있을 때는 루트노드에 데이터값을 넣어주고 끝이난다.
비어있지 않을때는 각 서브트리의 루트 노드보다
새로운 노드 data값이 작다면 왼쪽 자식 노드로,
새로운 노드 data값이 크거나 같다면 오른쪽 자식 노드로 진행하며
알맞는 자리에 추가해준다.

/// <summary>
/// BST에 새로운 원소 삽입
/// </summary>
/// <param name="elem(삽입할 원소)"></param>
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;
			}
		}
	}

}

binarySearchTree::find함수

Node* 형으로 매개변수값을 bst에서 찾는 함수이다.
값을 찾았다면 해당 값을 가진 노드의 포인터를 반환하고,
못 찾았다면 nullptr을 반환한다.

/// <summary>
/// 입력값을 찾는 함수
/// </summary>
/// <param name="elem(찾을 원소)"></param>
/// <returns>"원소 찾았다면 해당 원소 가리키는 포인터, 못 찾았다면 nullptr"</returns>
	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;
	}

binarySearchTree::swap함수

void 형으로 매개변수로 들어온 두 개의 노드를
교체해준다.
binarySearchTree::erase함수에서 사용하기 위해 만들었다.

/// <summary>
/// 매개변수로 들어온 노드 두개 바꿔주는 함수
/// </summary>
/// <param name="a(노드 1)"></param>
/// <param name="b(노드 2)"></param>
void binarySearchTree::swap(Node* a, Node* b) {
	//swap용 임시 노드
	Node* tmp = new Node;
	//a의 부모 노드의 왼쪽자식이 a라면
	if (a->parent->leftChild == a) {
		//b로 연결
		a->parent->leftChild = b;
	}
	//a의 부모 노드의 오른쪽 자식이 b라면
	else {
		a->parent->rightChild = b;
	}

	//b의 부모 노드의 왼쪽 자식이 b라면
	if (b->parent->leftChild == b) {
		b->parent->leftChild = a;
	}
	//b의 부모 노드의 오른쪽 자식이 a라면
	else {
		b->parent->rightChild = a;
	}

	tmp->data = b->data;
	b->data = a->data;
	a->data = tmp->data;

	tmp->parent = b->parent;
	b->parent = a->parent;
	a->parent = tmp->parent;

	tmp->leftChild = b->leftChild;
	b->leftChild = a->leftChild;
	a->leftChild = tmp->leftChild;

	tmp->rightChild = b->rightChild;
	b->rightChild = a->rightChild;
	a->rightChild = tmp->rightChild;

	delete(tmp);
}

binarySearchTree::erase함수(매개변수 int형)

void 형의 함수로 매개변수로 들어온 elem값을 찾아서 bst에서 제거한다.
제거할 때 경우의 수가 네 가지가 있는데
1. 노드가 리프노드일 때
-> 이때는 부모노드의 자식 노드값을, nullptr로 변경한다.
2. 노드가 왼쪽자식만 가지고 있을 때,
-> 부모노드의 자식 노드값을, 지우려는 노드에서 노드의 왼쪽 자식노드로 변경해준다.
3. 노드가 오른쪽 자식만 가지고 있을 때,
-> 부모노드의 자식 노드값을, 지우려는 노드에서 노드의 오른쪽 자식노드로 변경해준다.
4. 노드가 두 개의 자식 모두 가지고 있을 때, 방법이 두 가지가 있다.

노드의 왼쪽서브트리에서 제일 큰값과 자신을 교체
노드의 오른쪽 서브트리에서 제일 작은값과 자신을 교체

여기서는 오른쪽 서브트리에서 제일 작은값과 자신을 교체한다.

그 후 위의 모든 조건문이 끝난 후의 지우려는 노드는
모든 노드와의 관계가 끊어졌으므로 그냥 지우면 된다.

/// <summary>
/// BST에서 매개변수값 제거하는 함수
/// </summary>
/// <param name="elem(지울 원소)"></param>
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);
}

binarySearchTree::erase함수(매개변수 노드 포인터형)

erase함수를 하나를 더 만들었는 데 이번엔 숫자값이 들어오는게 아닌
지우려는 노드를 가리키는 포인터가 매개변수로 들어온다.
구현은 위의 함수에서 해당 값 find하는 부분만 제외하곤 똑같이 했다.

/// <summary>
/// 매개변수로 들어온 노드 포인터가 가리키는 노드 제거
/// </summary>
/// <param name="elem"></param>
void binarySearchTree::erase(Node* node) {
	//해당 원소가 리프 노드라면 
	if (node->leftChild == nullptr && node->rightChild == nullptr) {
		//해당 원소의 부모노드에서 해당 원소 제거
		if (node->parent->leftChild == node) node->parent->leftChild = nullptr;
		else node->parent->rightChild = nullptr;
	}
	//해당원소가 오른쪽 자식만 있을 때
	else if (node->leftChild == nullptr) {
		//만약 del노드가 del의 부모노드의 왼쪽자식이라면
		if (node->parent->leftChild == node) {
			node->parent->leftChild = node->rightChild;
		}
		//del노드가 부모노드의 오른쪽자식이라면
		else {
			node->parent->rightChild = node->rightChild;
		}
		//해당원소의 오른쪽자식의 부모노드를 해당원소의 부모노드로 설정
		node->rightChild->parent = node->parent;
	}
	//해당원소가 왼쪽 자식만 있을 때
	else if (node->rightChild == nullptr) {
		//del노드가 부모 노드의 왼쪽자식이라면
		if (node->parent->leftChild == node) {
			//부모노드의 왼쪽 자식을 해당원소의 왼쪽 자식으로 설정
			node->parent->leftChild = node->leftChild;
		}
		else {
			node->parent->rightChild = node->leftChild;
		}
		//해당원소의 왼쪽자식의 부모노드를 해당원소의 부모노드로 설정
		node->leftChild->parent = node->parent;
	}
	//해당 원소가 두 자식 다 있을 때 오른쪽 서브트리에서 제일 작은값과 교체
	else {
		//오른쪽 서브트리의 루르노드부터 시작해서
		Node* curNode = node->rightChild;
		//오른쪽 서브트리의 제일 작은 노드까지 
		while (curNode->leftChild != nullptr) {
			curNode = curNode->leftChild;
		}
		//두 노드를 바꿔주고
		swap(curNode, node);
		//해당 원소의 부모노드에서 해당 원소 제거
		if (node->parent->leftChild == node) node->parent->leftChild = nullptr;
		else node->parent->rightChild = nullptr;
	}
	delete(node);
}

binarySearchTree::print함수

void형의 함수로, 모든 원소를 출력해준다.
루트 노드값보다 작은 값이 왼쪽 서브트리, 큰 값이 오른쪽 서브트리에 저장되므로
중위 순회를 하면 순서대로 출력되서 중위 순회방식을 통해 출력하였다.

/// <summary>
/// inorder 방식으로 순회하며 크기대로 출력
/// </summary>
/// <param name="root값 넣어주면 됨"></param>
void binarySearchTree::print(Node* node) {
	if (node == nullptr) return;

	print(node->leftChild);
	cout << node->data;
	print(node->rightChild);
}

binarySearchTree::getRoot()함수

print에서 루트노드를 넣어줘야 순서대로 출려기 되어서
루트노드를 가리키는 포인터값을 반환하는 함수를 만들었다.

/// <summary>
/// root노드 포인터 반환해주는 함수
/// </summary>
/// <returns>루트 노드</returns>
Node* binarySearchTree::getRoot() {
	return root;
}

시행

int main() {
	binarySearchTree* bst=new binarySearchTree();
	bst->insert(5);
	bst->insert(2);
	bst->insert(3);
	bst->insert(4);
	bst->insert(1);
	bst->insert(6);
	bst->insert(7);
	
    //출력
	bst->print(bst->getRoot());
	cout << '\n';
	//3값 지우기
	bst->erase(3);
	bst->print(bst->getRoot());

	cout << '\n';
    //3값 다시 추가
	bst->insert(3);
	bst->print(bst->getRoot());
	cout << '\n';
    //3값 하나 더 추가
	bst->insert(3);
	bst->print(bst->getRoot());
	cout << '\n';
	//3노드를 매개변수로 줘서 3값 지우기
	bst->erase(bst->find(3));
	bst->print(bst->getRoot());
	cout << '\n';
	//3노드 찾아서 데이터값 출력
	cout<<bst->find(3)->data;


}

전체 코드

#include<iostream>
using namespace std;

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

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* elem);
	void print(Node* node);
	Node* getRoot();

};
/// <summary>
/// BST에 새로운 원소 삽입
/// </summary>
/// <param name="elem(삽입할 원소)"></param>
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;
			}
		}
	}

}

/// <summary>
/// 입력값을 찾는 함수
/// </summary>
/// <param name="elem(찾을 원소)"></param>
/// <returns>"원소 찾았다면 해당 원소 가리키는 포인터, 못 찾았다면 nullptr"</returns>
Node* binarySearchTree::find(int elem) {
	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이라면 존재하지 않으므로
		if (curNode == nullptr) return nullptr;
	}
}

/// <summary>
/// 매개변수로 들어온 노드 두개 바꿔주는 함수
/// </summary>
/// <param name="a(노드 1)"></param>
/// <param name="b(노드 2)"></param>
void binarySearchTree::swap(Node* a, Node* b) {
	//swap용 임시 노드
	Node* tmp = new Node;
	//a의 부모 노드의 왼쪽자식이 a라면
	if (a->parent->leftChild == a) {
		//b로 연결
		a->parent->leftChild = b;
	}
	//a의 부모 노드의 오른쪽 자식이 b라면
	else {
		a->parent->rightChild = b;
	}

	//b의 부모 노드의 왼쪽 자식이 b라면
	if (b->parent->leftChild == b) {
		b->parent->leftChild = a;
	}
	//b의 부모 노드의 오른쪽 자식이 a라면
	else {
		b->parent->rightChild = a;
	}

	tmp->data = b->data;
	b->data = a->data;
	a->data = tmp->data;

	tmp->parent = b->parent;
	b->parent = a->parent;
	a->parent = tmp->parent;

	tmp->leftChild = b->leftChild;
	b->leftChild = a->leftChild;
	a->leftChild = tmp->leftChild;

	tmp->rightChild = b->rightChild;
	b->rightChild = a->rightChild;
	a->rightChild = tmp->rightChild;

	delete(tmp);
}

/// <summary>
/// BST에서 매개변수값 제거하는 함수
/// </summary>
/// <param name="elem(지울 원소)"></param>
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);
}
/// <summary>
/// 매개변수로 들어온 노드 포인터가 가리키는 노드 제거
/// </summary>
/// <param name="elem"></param>
void binarySearchTree::erase(Node* node) {
	//해당 원소가 리프 노드라면 
	if (node->leftChild == nullptr && node->rightChild == nullptr) {
		//해당 원소의 부모노드에서 해당 원소 제거
		if (node->parent->leftChild == node) node->parent->leftChild = nullptr;
		else node->parent->rightChild = nullptr;
	}
	//해당원소가 오른쪽 자식만 있을 때
	else if (node->leftChild == nullptr) {
		//만약 del노드가 del의 부모노드의 왼쪽자식이라면
		if (node->parent->leftChild == node) {
			node->parent->leftChild = node->rightChild;
		}
		//del노드가 부모노드의 오른쪽자식이라면
		else {
			node->parent->rightChild = node->rightChild;
		}
		//해당원소의 오른쪽자식의 부모노드를 해당원소의 부모노드로 설정
		node->rightChild->parent = node->parent;
	}
	//해당원소가 왼쪽 자식만 있을 때
	else if (node->rightChild == nullptr) {
		//del노드가 부모 노드의 왼쪽자식이라면
		if (node->parent->leftChild == node) {
			//부모노드의 왼쪽 자식을 해당원소의 왼쪽 자식으로 설정
			node->parent->leftChild = node->leftChild;
		}
		else {
			node->parent->rightChild = node->leftChild;
		}
		//해당원소의 왼쪽자식의 부모노드를 해당원소의 부모노드로 설정
		node->leftChild->parent = node->parent;
	}
	//해당 원소가 두 자식 다 있을 때 오른쪽 서브트리에서 제일 작은값과 교체
	else {
		//오른쪽 서브트리의 루르노드부터 시작해서
		Node* curNode = node->rightChild;
		//오른쪽 서브트리의 제일 작은 노드까지 
		while (curNode->leftChild != nullptr) {
			curNode = curNode->leftChild;
		}
		//두 노드를 바꿔주고
		swap(curNode, node);
		//해당 원소의 부모노드에서 해당 원소 제거
		if (node->parent->leftChild == node) node->parent->leftChild = nullptr;
		else node->parent->rightChild = nullptr;
	}
	delete(node);
}

/// <summary>
/// inorder 방식으로 순회하며 크기대로 출력
/// </summary>
/// <param name="root값 넣어주면 됨"></param>
void binarySearchTree::print(Node* node) {
	if (node == nullptr) return;

	print(node->leftChild);
	cout << node->data;
	print(node->rightChild);
}

/// <summary>
/// root노드 포인터 반환해주는 함수
/// </summary>
/// <returns>루트 노드</returns>
Node* binarySearchTree::getRoot() {
	return root;
}


int main() {
	binarySearchTree* bst=new binarySearchTree();
	bst->insert(5);
	bst->insert(2);
	bst->insert(3);
	bst->insert(4);
	bst->insert(1);
	bst->insert(6);
	bst->insert(7);
	
	bst->print(bst->getRoot());
	cout << '\n';

	bst->erase(3);
	bst->print(bst->getRoot());

	cout << '\n';
	bst->insert(3);
	bst->print(bst->getRoot());
	cout << '\n';
	bst->insert(3);
	bst->print(bst->getRoot());
	cout << '\n';

	bst->erase(bst->find(3));
	bst->print(bst->getRoot());
	cout << '\n';

	cout<<bst->find(3)->data;


}

생각

한쪽으로 트리가 치우치면 스스로 균형잡는
balanced tree는 아니라서 치우친값들이 나오면
시간복잡도가 O(n)까지 나올 수 있다.
후에 공부해서 balanced로 구현해서 다시 올릴것

jh Seo

코딩 창고!

이전 포스트