이진 검색 트리
-
이진 검색 트리 출력 함수 구현프로그래밍 기초/알고리즘 2021. 9. 21. 13:55
이진 검색 트리 출력 이진 검색 트리를 화면에 출력하는 함수를 구현한다. 노드 출력 알고리즘 노드를 동일한 간격으로 출력하기 위해 다음의 제약 사항이 존재해야 한다. 모든 노드는 동일한 크기를 갖는다. 최대 깊이의 노드 간의 간격은 노드의 크기와 같다. 최대 깊이에 빈 노드가 없다고 가정하여 최대 크기를 구한다. 구한 최대 크기를 모든 깊이에 사용하여 출력한다. 깊이가 n 일 때, 노드의 개수 및 공백의 개수는 다음과 같다. 노드의 수 2ⁿ - ¹ 개 공백의 수 n + 1 개 따라서 최대 깊이에서 출력에 필요한 크기는 다음의 식을 만족한다. 출력에 필요한 크기 = (공백의 수 + 노드의 수) * 노드의 크기 ※ 깊이에 따라 노드의 수가 달라지므로 공백의 크기는 출력에 필요한 크기 - (노드의 수 * 노드..
-
이진 검색 트리 구현 및 테스트프로그래밍 기초/알고리즘 2021. 8. 10. 12:06
이진 검색 트리 이진 검색 트리의 특성은 다음과 같다. 각 노드는 서로 다른 키 값을 하나씩 갖는다. 최상위 레벨에 루트가 있으며, 각 노드는 최대 두 개의 자식 노드를 가진다. 노드의 왼쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 작다. 노드의 오른쪽 서브 트리의 모든 노드의 값은 항상 노드의 값보다 크다. 이진 검색 트리에서의 검색 특정 키를 가진 노드를 검색하는 방법은 다음과 같다. 이진 검색 트리의 루트 노드에서부터 비교를 시작한다. 주어진 키와 노드의 키를 비교하여 주어진 키가 노드의 키가 같으면 노드를 반환한다. 주어진 키가 노드의 키보다 작으면 왼쪽 서브 트리로 이동하여 다시 비교한다. 주어진 키가 노드의 키보다 크면 오른쪽 서브 트리로 이동하여 다시 비교한다. 위 과정을 노드를 찾..