이진 탐색 트리
-
트리(Tree)와 이진 탐색 트리(Binary Search Tree)프로그래밍 기초/자료구조 2021. 3. 29. 19:33
트리 각각의 자료가 노드를 이루고 각 노드가 부모-자식 관계를 형성하는 자료구조를 말한다. 트리의 구성 요소 트리는 하나의 루트와 여러 개의 자식 노드로 구성된다. 노드 트리를 이루는 각각의 요소 루트 트리의 최상단 요소 리프 트리의 최말단 요소 차수 각 노드가 가진 자식의 수 트리의 차수 해당 트리에 존재하는 각 노드의 차수 중 가장 큰 값 높이 트리의 노드의 레벨 중 가장 큰 값 이진트리 리프 노드를 제외한 노드의 자식이 1개 혹은 2개로 이루어진 트리로 각 서브 트리는 다음과 같은 구조로 이루어진다. ※ 각 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드로 구분하며 각각의 자식 노드가 자식 노드를 가진 경우 자식 노드를 루트로 하는 노드 집단을 서브 트리라고 한다. 이진 트리의 특징 n개의 노드를 ..