![]()
이진 탐색 트리 (Binary Search Tree) 의 개념 이진 탐색 트리란 ? Binary Search Tree (이하, BST)는 모든 노드의 왼쪽 서브 트리가 해당 노드 보다 작은 값을 가지고, 오른쪽 서브 트리가 해당 노드 보다 큰 값을 가지는 구조의 Binary Tree 입니다. 위의 그림에서는 노드 20의 왼쪽 서브 트리는 모두 20보다 작은 값을 가지고, 오른쪽 서브 트리의 모든 값은 20보다 큰 값을 가지고 있습니다. 그런데 만약 자식 노드 중 이러한 조건을 하나라도 만족하지 않는 노드가 존재한다면 BST가 아니게 됩니다. 예를 들어 5의 자식 노드 중 오른쪽 자식 노드가 1의 값을 가진다면, 해당 트리는 더이상 BST가 아닙니다. 이러한 특징을 가지는 BST는 항상 작은 값은 왼쪽, ..
![]()
이진 트리란 ? 이진 트리는 트리 형태의 자료 구조 중 가장 많이 사용하는 트리로, 각 노드의 자녀 노드 수가 최대 두개인 트리를 이진 트리(Binary Tree)라고 합니다. 형태에 따른 이진 트리 종류 1. Full Binary Tree (정 이진 트리) Full Binary Tree란 모든 노드가 자녀 노드가 없거나 또는 두 개의 자녀 노드를 가지는 이진 트리입니다. (즉, 자녀 노드를 1개를 가지는 노드가 없어야 합니다) 2. complete binary tree (완전 이진 트리) complete binary tree는 마지막 레벨을 제외한 모든 레벨의 노드가 두 개씩 노드를 가지고, 마지막 레벨은 왼쪽 부터 빠짐없이 노드가 채워지는 이진 트리입니다. 3. perfect binary tree (..
![]()
Tree의 개념 트리(Tree) 란 노드(Node)들의 집합으로, 노드는 값(value)과 다른 노드들을 가리키는 레퍼런스(Reference)들로 구성되어 있습니다. Tree의 주요 용어 간선 간선 (Edge)란 노드와 노드를 연결하는 선을 의미하고, 구현 관점에서는 노드 간의 주소 값 레퍼런스(참조)를 의미합니다. 역할 별 노드 트리의 노드는 역할에 따라 자녀 노드 , 부모 노드, 형제 노드, 조상 노드, 자손 노드, 내부 노드, 외부 노드 가 있습니다. 각 노드들이 무엇이고 어떤 역할을 하는지 그림을 통해 알아보겠습니다. 1. 루트 노드 (Root Node) 모든 노드의 최상위 노드 위 그림에서 P에 해당합니다. 2. 자녀 노드 (Child Node) 특정 노드의 바로 아래에 연결된 노드 부모 노드..
