🌳 Binary Tree 🌳

(left) binary tree / (right) binary search tree

theory

🌳 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조

: Binary Tree is defined as a tree data structure where each node has at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

 

🌳 트리 관련 용어

① root node: 부모가 없는 최상위 노드

② leaf node: 자식이 없는 노드

③ size: 트리에 포함된 모든 노드의 개수

④ depth: 특정 노드에서 루트 노드부터의 거리(즉 위 1번 노드의 깊이는 0, 2번 노드의 깊이는 1)

⑤ height: 깊이 중 최댓값(위 8번 노드의 깊이가 height)

⑥ degree: 각 노드의 (자식 방향) 간선 개수(즉 자식의 개수) (위 1번 노드의 차수는 2)

 

🌳 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개

binary search tree

🌳 binary tree 중에서 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종

 

🌳 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

🌳 The left and right subtree each must also be a binary search tree. There must be no duplicate nodes.

basis of comparison	binary tree	binary search tree
definition	a nonlinear data structure where each node can have at most two child nodes.	a node based binary tree that further has right and left subtree that too are binary search tree.
types	Full binary tree Complete binary tree Extended Binary tree and more	AVL tree Splay tree T-trees and more
structure	In BINARY TREE there is no ordering in terms of how the nodes are arranged	In BINARY SEARCH TREE the left subtree has elements less than the nodes element and the right subtree has elements greater than the nodes element.
data representation	Data Representation is carried out in a hierarchical format.	Data Representation is carried out in the ordered format.
duplicate values	Binary trees allow duplicate values.	Binary Search Tree does not allow duplicate values.
speed	The speed of deletion, insertion, and searching operations in Binary Tree is slower as compared to Binary Search Tree because it is unordered.	Because the Binary Search Tree has ordered properties, it conducts element deletion, insertion, and searching faster.
complexity	Time complexity is usually O(n).	Time complexity is usually O(logn).
application	It is used for retrieval of fast and quick information and data lookup.	It works well at element deletion, insertion, and searching.
usage	It serves as the foundation for implementing Full Binary Tree, BSTs, Perfect Binary Tree, and others.	It is utilized in the implementation of Balanced Binary Search Trees such as AVL Trees, Red Black Trees, and so on.

 

🌳 binary searching example

🌳 binary search tree가 이미 구성되어 있다고 가정하고 데이터 조회하자. 찾고자 하는 원소가 37이라 가정하면, root node부터 방문해서 탐색 진행. 현재 node 값은 30이므로 찾는 원소가 값이 더 큼. 따라서 현재 root node에서 오른쪽으로 방문. 그 다음 단계에서는 값이 48인 node 방문(즉 root node의 왼쪽 범위는 방문할 필요 없음 - 탐색 범위 절반으로 줄어듦). 37은 48보다 작으므로 왼쪽 방문. 37 확인! 원소를 찾았으므로 탐색 종료

 

🌳 즉 이진 탐색이 가능하게끔 고안된 트리 자료구조. 이상적인 경우 데이터 탐색 O(logn). 하지만 왼쪽과 오른쪽 tree가 균형이 잡혀있을 경우만 가능한 시간 복잡도. 따라서 실제로는 트리 자료구조를 활용한 다양한 자료구조 존재

traversal(트리의 순회)

🌳 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법. 트리의 정보를 시각적으로 확인 가능

 

① 전위 순회(pre-order traverse): 루트를 먼저 방문

② 중위 순회(in-order traverse): 왼쪽 자식을 방문한 뒤에 루트를 방문

③ 후위 순회(post-order traverse): 오른쪽 자식을 방문한 뒤에 루트를 방문

 

ex)

① 전위 순회

: 루트를 먼저 출력(A)후 왼쪽 들어가서 출력(B) 그 다음 왼쪽(D)출력. 이제 자식 노드 없으면 다시 위로 올라가서 오른쪽(E) 출력. 다시 위로 올라가서 오른쪽(C) 출력. 그 다음 왼쪽(F) 출력. 자식 노드 없으므로 다시 위로 올라가서 오른쪽(G) 출력

 

A → B  → D → E → C → F → G

 

② 중위 순회(아래로 쭉 내려가서 왼쪽 자식 노드부터 출력)

: 루트에서 시작해 맨 왼쪽 자식 노드(D)로 이동. 다시 위로 올라가서 노드(B) 출력. 오른쪽(E) 출력. 다시 위로 올라가서 A 출력. 오른쪽 자식 노드 C 출력. 왼쪽부터 F 출력. 마지막 G 출력

 

D → B → E → A → F → C → G

 

③ 후위 순회

: 루트에서 시작해 맨 왼쪽 자식 노드(D)로 이동. 그 다음 위로 올라가서 다른 오른쪽 자식 노드(E) 출력. 이제 상위 노드 B 출력하는 방식

 

D → E → B → F → G → C → A

 

☆ 즉 전위 순회는 루트 먼저 / 중위 순회는 왼쪽 먼저 →  루트 →  오른쪽 / 후위 순회는 왼쪽 →  오른쪽 →  루트☆

traversal 구현 예제

☆ pre-order는 upper - left -right / in-order는 left - upper - right / post-order는 left - right - upper ☆

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

#preorder traversal
def pre_order(node):#upper -> left -> right
    print(node.data, end=' ') #upper print: when visited, just print right away
    if node.left_node != None: #left first(recursive)
        pre_order(tree[node.left_node])
    if node.right_node != None:
        pre_order(tree[node.right_node])

#inorder traversal
def in_order(node):#left -> upper -> right
    if node.left_node != None: #if left_node, search 
        in_order(tree[node.left_node])
    print(node.data, end= ' ') #if left_node doesn't exist, print upper-node
    if node.right_node != None:
        in_order(tree[node.right_node])

#postorder traversal
def post_order(node): #left -> right -> upper
    if node.left_node != None:
        post_order(tree[node.left_node])
    if node.right_node != None:
        post_order(tree[node.right_node])   
    print(node.data, end= ' ')

n=int(input())
tree={}

for i in range(n):
    data, left_node, right_node = input().split()
    if left_node == 'None':
        left_node = None
    if right_node == 'None':
        right_node = None
    
    tree[data] = Node(data, left_node, right_node)

pre_order(tree['A']) #starts from A node
print()
in_order(tree['A'])
print()
post_order(tree['A'])


#input
'''
7
A B C
B D E
C F G
D None None
E None None
F None None
G None None
'''

#output
'''
A B D E C F G
D B E A F C G
D E B F G C A
'''

---

이코테 2021

geeksforgeeks