이진탐색트리 (1) 썸네일형 리스트형 이진 탐색 트리 Binary Search Tree : BST /* * 이진탐색트리(Binary Search Tree : BST) 는 삽입, 삭제, 탐색에서 월등한 성능을 나타낸다. * * BST는 공백이 가능한 이진트리로서 공백이 아니라면 다음의 성질을 만족한다. * ①모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다. * 즉, 키는 유일한 값을 갖는다. * ②공백이 아닌 좌측 서브트리에 있는 키들은 그 서브트리의 루트의 키보다 작아야 한다. * ③공백이 아닌 우측 서브트리에 있는 키들은 그 서브트리의 루트의 키보다 커야 한다. * ④좌측과 우측 서브트리도 BST이다. * * 높이가 h인 BST에 대해 탐색(search)를 사용하면 O(h)시간내에 탐색을 수행할 수 있다. * 높이가 h인 BST에 대해 key값의 노드를 삽입할 경우 탐색하는데 드.. 이전 1 다음