Tree

데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조입니다

하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조 입니다

트리구조

루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결합니다

각 데이터를 노드(Node) 라고 합니다 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가집니다

자식이 없는 노드를 나무의 잎과 같다하여 리프 노드(leaf Node) 라고 합니다

레벨과 서브트리

• 깊이(depth) 루트로부터 하위 계층의 특정 노드까지의 깊이 를 의미합니다 위 그림에서 루트 A의 depth는 0, B와 C의 깊이는 1입니다
• 레벨(level) 같은 깊이를 가지고 있는 노드를 묶어서 레벨 이라고 합니다 같은 레벨에 나란히 있는 노드를 형제 노드 라고 합니다
• 높이(height) 리프 노드를 기준으로 루트까지의 높이 를 표현할 수 있습니다 부모 노드는 자식 노드의 가장 높은 height값에 +1한 값을 높이로 가집니다 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓습니다 위 그림에서 H, I, E, F, J의 높이는 0입니다, B와 C의 높이는 2이구여 이때 B는 D의 height + 1을 C는 G의 height + 1을 높이로 가집니다
• 서브 트리(sub tree) 트리 구조를 갖춘 작은 트리를 서브트리라고 합니다

Binary Search Tree

트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 합니다

이진트리(binary tree) 는 자식 노드가 최대 두 개인 노드들로 구성된 트리입니다

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있습니다