문법/Python
이진트리(Binary Tree)
jungmin.park
2023. 10. 25. 13:59
Understand Binary Search Tree through Gifs
Binary Search Tree Degredation Gif Insertion of a node into Tree Description --> Binary Search Tree vs Sorted Array Animated Gif Comparing Sorted Array vs Binary Search Tree Description --> Optimal Binary Search Tree from Sorted Array Subtopic --> Descript
www.mathwarehouse.com
트리
- 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터구조
- 트리 중 이진 트리(Binary Tree) 형태의 구조로 탐색(검색) 알고리즘 구현을 위해 많이 사용됨.
- 큐(Queue), 스택(Stack) 와 같이 선형구조가 아닌 비선형 구조
- 선형구조 : 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태 / 자료를 저장하고 꺼내는 것에 초점
- 비선형구조 : 데이터가 계층적 혹은 망으로 구성되어있다. / 표현에 초점
용어
- Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
- Root Node : 트리 맨 위에 있는 노드
- Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
- Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
- Child Node : 어떤 노드의 상위 레벨에 연결된 노드
- Leaf Node(Terminal Node) : Child Node가 하나도 없는 노드
- Sibling (Brother Node): 동일한 Parent Node를 가진 노드
- Depth: 트리에서 Node가 가질 수 있는 최대 Level
이진 트리(Binary Tree) 와 이진 탐색 트리
- 이진 트리 : 노드의 최대 Branch가 2인 트리