Binary Tree란?
Binary tree is a tree for which every node has at most two child nodes.
Binary Tree는 체리처럼 자식 노드가 2개 이하로 구성된 나무 형태의 데이터 구조를 의미합니다
Binary Tree traversals
Binary Tree가 순회할 때 이렇게 3가지 종류로 나뉠 수 있는데요,
이는 재귀적으로 구현할 때 언제 node.value를 print 하느냐가 가장 큰 차이라고 합니다
여기서 신기한 점은 Binary Search Tree를 inorder traversal 시키면 오름차순 형태로 배열이 완성된다는 점인데요
상황에 따라 BST와 inorder 코드를 잘 구현해서 사용할 수 있을 것 같습니다
Level orderd은 다른 구성들과는 달리 BFS 탐색 방식을 사용하는 차이점이 있습니다
Binary Search Tree란?
Binary search tree is a binary tree that satisfies the BST invariant: left subtree has smaller elements and right subtree has larger elements ==> Binary Tree이지만 왼쪽 자식노드가 root보다 작은 값들, 오른쪽 자식 노드는 root보다 큰 값으로 구성된 Tree로 보시면 될 것 같습니다
| Operation | Average | Worst |
| Insert | O(log(n)) | O(n) |
| Delete | O(log(n)) | O(n) |
| Remove | O(log(n)) | O(n) |
| Search | O(log(n)) | O(n) |
Time Complexity는 일반적으로 O(log(n))이 걸리지만, 오른쪽이나 왼쪽으로 편향된 긴 Tree구조라면 요소들을 다 지나가야 하는 선형적인 O(n)이 나타날 수도 있다고 합니다
추후에 좀 더 공부하면서 내용을 추가하도록 하겠습니다 :))
Source:
https://www.youtube.com/watch?v=RBSGKlAvoiM&t=11052s
댓글