Tree
Tree
단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 트리구조라고 부른다.
트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조
하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조
트리는 사이클이 없는 하나의 연결 그래프
Tree의 구조 & 특징
트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge) 으로 연결한다.
- 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
- 루트(Root) : 트리 구조의 시작점이 되는 노드
- 부모 노드(Parent node) : 두 노드가 상하관계로 연결될 때 루트에서 가까운 노드
- 자식 노드(Child node) : 두 노드가 상하관계로 연결될 때 루트에서 먼 노드
- 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
- 깊이(depth) : 루트로부터 하위 계층의 특정 노트까지의 깊이
- 레벨(Level) : 같은 깊이를 가지고 있는 노드를 묶어 레벨로 표현, 같은 레벨에 나란히 있는 노드를 형제노드(Sibling Node)라고 함
- 높이(Height) : 리프 노드를 기준으로 루트까지의 높이를 표현
- 서브 트리(Sub tree) : 루트에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리
이진 트리(Binary tree)
자식노드가 최대 두개인 노드로 구성된 트리
자료의 삽입, 삭제 방법에 따라 정 이진트리, 완전 이진트리, 포화 이진트리로 나뉨
정 이진트리(Full binary tree)
각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
포화 이진트리(Perfect binary tree)
정 이진트리이면서 완전 이진트리인 경우,
모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리
완전 이진트리(Complete binary tree)
마지막 레벨을 제외한 모든 노드가 가득 차 있어야하고 마지막 레벨의 노드는 전부 차 있지 않아도 왼쪽이 채워져야 한다.
이진 탐색 트리(Binary Search Tree)
정렬된데이터 중에서 특정한 값을 찾기 위한 알고리즘
오름차순으로 정렬된 정수의 배열을 같은 크기의 두 부분 배열로 나누고, 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한해 원하는 값을 찾는 알고리즘
이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.
이진 탐색 트리 특징
기존 이진트리보다 탐색이 빠르다.
이진탐색 트리 탐색 과정
1. 루트 노드의 키와 찾고자 하는 값을 비교, 찾고자 하는 값이면 탐색 종료
2. 찾고자 하는 값이 루트 노드의키보다 작으면 왼쪽 서브 트리로 탐색 진행
3. 찾고자 하는 값이 루트 노드의 키보다 크면 오른쪽 서브 트리로 탐색 진행
위의 과정을 찾고자 하는 값을 찾을 때까지 반복한다.
만약 값을 찾지 못하면 그대로 종료한다.
탐색 과정은 기본으로 최대 트리의 높이 만큼 연산과 탐색이 진행된다.
트리 순회
전위 순회(preorder traverse)
가장 먼저 방문하는 노드가 루트이다.
루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러보고 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.
부모노드가 제일 먼저 방문되는 순회 방식
중위 순회(inorder traverse)
루트를 가운데 두고 순회한다.
제일 왼쪽 끝에 있는 노드부터 시작해 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 노드로 이동해 탐색한다.
부모노드가 서브 트리의 방문 중간에 방문되는 순회방식
후위 순회(postorder traverse)
루트를 가장 마지막에 순회한다.
제일 왼쪽 끝에 있는 노드부터 시작해 루트를 거치지 않고 오른쪽으로 이동해 순회하고 제일 마지막에 루트를 방문한다.
내용 참조, 이진트리 이미지 출처 : 코드스테이츠
트리구조 이미지 출처:https://wikidocs.net/193702 https://ssangq.netlify.app/posts/data-structure-tree
트리순회 이미지 출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=shootingstar_romance&logNo=220681857243
