728x90
반응형
[자료 구조] 5. 비선형 자료 구조
1. 비선형 자료 구조: 부모 자식의 관계처럼 계층적인 관계를 표현하는 데에 사용된다.
-트리는 노드(Node)로 구성되며, 하나의 노드가 다른 노드들과 연결된 구조를 가진다.
(1) 트리 구조(Tree): 부모 노드와 자식 노드 간의 연결로 이루어진 자료 구조이다.
반대로 뒤집으면 나무 형태와 비슷하다.
(2) 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가질 수 있는 트리이다.
즉, 0부터 2개까지의 자식 노드를 가질 수 있다. 요소가 중복되어도 상관이 없다.
(3) 이진 탐색 트리(Binary Search Tree, BST): 이진 트리의 한 종류로, 각 노드에서 왼쪽 서브트리에는 노드의 값보다 작은 값들을, 오른쪽 서브 트리에는 노드의 값보다 큰 값들을 가지는 구조이다.
*이진 탐색 트리의 목적은 검색이다. 그래서 안에 들어가는 요소들이 중복되어서는 안 된다.
(4) 균형 이진 탐색 트리(Balanced Binary Search Tree): 데이터에 따라 편향되거나, 균형이 맞춰지지 않은 트리가 생길 수도 있다. 편향된 이진 트리를 재정렬하여 균형을 맞추는 트리를 균형 이진 탐색 트리라고 한다.
728x90
반응형
'자료 구조 > 기본 개념' 카테고리의 다른 글
[자료 구조] 6. 연결 리스트 (0) | 2024.05.08 |
---|---|
[자료 구조] 6. 큐 구현하기 (0) | 2024.05.07 |
[자료 구조] 4. 배열을 활용해 Stack 구현하기 (0) | 2024.05.03 |
[자료 구조] 3. Java 배열을 활용한 객체 만들기 (0) | 2024.05.02 |
[자료 구조] 2. 선형 자료 구조 (0) | 2024.05.02 |