목록Data structure (1)

algoqna

이진 탐색 트리 구현(연결리스트)

이진트리는 배열의 방식으로도, 연결리스트의 방식으로도 구현이 가능합니다. 연결리스트의 경우, 공간의 낭비 없이 필요할 때만 공간을 만들어서 편향 이진트리가 나온다고 해도 공간의 낭비가 전혀 없다는 장점이 있죠. 이번에는 이진 트리가 아닌 '이진 탐색' 트리를 구현해 보겠습니다. 이진 트리는 자식이 최대 2개 이하만 되면 모든 조건을 만족하니, 어렵지 않습니다. 이진 탐색트리는 여기에 추가적인 조건이 붙습니다. 출처 : [네이버 지식백과] - 이진 탐색 트리 1. 모든 노드는 다른 값을 갖는다. 2. 왼쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 작은 값을 갖는다. 3. 오른쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 큰 값을 갖는다. 4. 왼쪽, 오른쪽 서브트리도 이진 탐색 트리이다..
자료구조 2022. 9. 21. 18:21
이전 Prev 1 Next 다음