728x90
이진 검색 트리
-
이진 검색 트리Computer Science/Data Structure 2021. 9. 24. 16:04
이진 검색 트리의 정의 ㆍ 각 노드는 (키, 값)의 쌍을 저장하며, 서로 다른 노드의 키는 다르다. ㆍ 왼쪽 서브 트리에 저장된 노드의 키보다는 크다. ㆍ 오른쪽 서브 트리에 저장된 노드의 키보다는 작다. 이진 검색 트리의 장점 ㆍ 심볼 테이블을 정렬된 순서로 유지할 필요 없다. ㆍ 새로 삽입되는 노드는 항상 리프 노드에 위치한다. 이진 검색 트리의 단점 ㆍ 균형 트리를 보장하지 않는다. ㆍ 감색 시 많은 시간이 소요된다. 구현 방법 노드의 구성 class Node { K key; V value; Node left, right; int N; int aux; Node parent; public Node(K key, V value) { this.key = key; this.value = value; this..