트리란? 🌲
트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.
트리의 특징
1. 트리는 하나의 루트 노드를 갖는다.
2. 루트 노드는 0개 이상의 자식 노드를 갖는다.
3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다.
4. 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다.
트리와 관련된 용어 🖍
- 루트 노드(root node) : 부모가 없는 노드로 트리는 단 하나의 루트 노드를 가진다. (ex : A- 루트노드)
- 단말 노드(leaf node) : 자식이 없는 노드로 terminal 노드라고도 부른다. (ex : C, D, E - 단말 노드)
- 내부 노드(internal node) : 단말 노드가 아닌 노드(ex : A, B - 내부 노드)
- 간선(edge) : 노드를 연결하는 선
- 형제(sibling) : 같은 부모 노드를 갖는 노드들 (ex : D-E, B-C : 형제)
- 노드의 깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수(ex : D의 depth : 2)
- 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합 ( ex : level 1- {B, C} )
- 노드의 차수(degree) : 자식 노드의 개수 ( ex : B의 degree - 2, C의 degree - 0)
- 트리의 차수(degree of tree) : 트리의 최대 차수 ( ex : 위 트리의 차수는 2이다)
트리의 순회 🥖
- 전위 순회 (pre-order) Root → Left child → Right child
- 중위 순회 (in-order) Left child → Root → Right child
- 후위 순회 (post-order) Left child → Right child → Root
이진 트리 😃
이진트리는 각 노드가 최대 두 개의 자식을 갖는 트리를 뜻한다. 즉, 각 노드는 자식이 없거나 한 개 이거나 두 개만을 갖는 것이다.
이진 트리는 아래와 같이 분류할 수 있다
- Perfect Binary Tree (포화 이진 트리) 모든 레벨이 꽉 찬 이진 트리
- Complete Binary Tree (완전 이진 트리) 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리
- Full Binary Tree (정 이진 트리) 모든 노드가 0개 또는 2개의 자식 노드를 갖는 이진 트리
이진 탐색 트리 🐱
이진 트리의 일종으로, 데이터를 저장하는 규칙들을 규정하여 데이터를 효율적으로 탐색할 수 있게 해준다
- 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종입니다.
- 이진 탐색 트리의 특징 : 왼쪽 노드 < 부모 노드 < 오른쪽 자식 노드
- 부모 노드보다 왼쪽 자식 노드가 작습니다.
- 부모 노드보다 오른쪽 자식 노드가 큽니다.
출처
https://www.youtube.com/watch?v=i5yHkP1jQmo
https://github.com/alstjgg/cs-study/blob/main/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/Tree.md#%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B8%B0%EB%B3%B8
https://code-lab1.tistory.com/8
FrontEnd Developer