[자료구조] 이진 검색 트리

 

이진 트리의 형태

왼쪽 자식 노드값 <= 부모 노드 값 <= 오른쪽 자식 노드 값

이진 트리는 어느 노드를 기준으로 왼쪽 서브 트리는 모두 그 노드보다 작은 값을 가지고 있고 오른쪽 서브트리는 모두 그 노드보다 큰 값을 가지고 있는 트리이다.

그러므로 중위 순회하면 정렬된 데이터 값을 얻는다.

 

 

연산

이진 검색 트리의 연산은 트리의 형태에 따라 시간 복잡도가 달라지는데 좌우가 균형갑혀 있다면 연산은 O(logN) 이 되지만, 어느 한 쪽으로 편향되어 있을수록 O(N)에 가까워진다.

 

 

기능

 

명령어	설명	반환값
height()	트리의 높이를 구한다.(큐를 이용함)	int(트리 높이)
height2()	트리의 높이를 구한다.(재귀를 이용함)	int(트리 높이)
empty()	트리가 비었는지 확인한다.	bool (비었으면 true 아니면 false)
size()	트리의 크기값을 확인한다.	int (트리 크기)
clear()	트리를 비운다.	void (없음)
insert(int value)	트리에서 velue에 값을 삽입한다.	bool (삽입에 성공하면 true 아니면 false)
erase(int value)	트리에서 velue에 값을 삭제한다.	size_t (트리 사이즈)
find(int value)	트리에서 value값을 찾는다.	Node* (찾은 노드)
traverseByLevelorder()	트리를 순회한다.(레벨순회)	void (없음)
traverseByPreorder()	트리를 순회한다.(전위순회)	void (없음)
traverseByInorder()	트리를 순회한다.(중위순회)	void (없음)
traverseByPostorder()	트리를 순회한다.(후위순회)	void (없음)