[2021/08/22][짤막한 이야기 - 이진 트리]

[2021/08/22][짤막한 이야기 - 이진 트리]
“이진 트리(Binary Tree)”는 자료구조의 한 형태로 트리의 특수한 형태이다.
사각형, 직사각형, 정사각형이 포함관계인 것처럼, 이진 트리도 트리와 포함관계이다.
정확히는 그래프, 트리, 이진 트리로 생각할 수 있다.
트리는 그래프 중에서도 순환이 없고 내향 간선(Inner-Direction Edge)이 1개인 특수한 형태의 그래프이다.
또한 이진 트리는 트리 중에서도 자식 노드가 최대 2개만 존재하는 특수한 형태의 트리이다.
이진 트리는 자료구조 중에서도 특히 중요하게 여겨지는데, 앞선 포스트의 “이진 탐색(Binary Search)”처럼 해당 자료구조를 사용하면 분석에 소요되는 시간이 매우 짧기 때문이다.
정확히는 순회에 소요되는 시간이 일차식(O(N))이 아닌 로그(O(LogN))가 되는 것이다.
순회에 소요되는 시간이 짧아진다는 점에서 더 많은 문제를 풀어낼 수 있다.
그 중 하나가 다음 포스트에서 이야기하고자 하는 “구간합”을 “인덱스 트리”로 해결하는 방법이다.
[관련된 짤막한 이야기 - 구간합[2021/08/11]]
[관련된 짤막한 이야기 - 이진 탐색[2021/07/26]]
#이야기 #루니프 #알고리즘 #이진트리 #이진탐색 #구간합 #인덱스트리

[2021/08/22][Short Story - Binary Tree]
"Binary Tree" is a special form of a tree as a form of data structure.
Just as quadrangles, rectangles, and squares are inclusive, binary trees are inclusive of trees.
It can be thought of as a graph, tree, or binary tree to be exact.
A tree is a special form of a graph with no loop and no inner-direction edge.
A binary tree is also a special form of a tree with up to two child nodes among the trees.
Binary trees are considered particularly important among data structures, as in the previous post's "Binary Search", because the time spent on analysis is very short when using such data structures are used.
To be precise, the time spent on the tour is a log (O(LogN)) rather than a linear equation (O(N)).
Further problems can be solved in that the time spent on the tour is shortened.
One of them is how to solve the "Prefix Sum" that I want to talk about in the next post with an "Index Tree."
[Related Short Story - Prefix Sum[2021/08/11]]
[Related Short Story - Binary Search[2021/07/26]]
#Story #LootNiP #Algorithm #BinaryTree #BinarySearch #PrefixSum #IndexTree