[자료구조] 이진 트리 및 이진 검색 트리

이진 트리 (Bianary Tree)

배열, 링크드리스트, 스택, 큐와 같이 일직선 개념의 자료구조가 아니라
비선형 자료구조인 부모-자식 개념을 가지는 자료구조이다.

 

데이터를 트리 구조로 배열 할 때 트리 맨 위에있는 노드를 루트 노드라고합니다. 전체 트리에 대해 하나의 루트 만있을 수 있습니다. 루트 노드를 제외한 모든 노드에는 노드 위쪽에 하나의 가장자리가 있습니다. 이를 부모 노드라고합니다. 부모 코드 아래의 노드를 자식 노드라고합니다. 각 상위 노드에는 최대 2 개의 하위 노드가있을 수 있습니다. 왼쪽 자식 노드와 오른쪽 자식 노드라고합니다. 자식 노드가없는 노드를 리프 노드.

 

이진 검색 트리 (binary search tree)란, 이진 탐색 트리는 기본적인 특징은 이진 트리와 같지만 하나 다른 점은 자기 왼쪽에는 자신보다 값이 작은 노드가, 오른쪽에는 자신보다 값이 큰 노드가 와야한다는 것이다.

이진 트리

 

이진 트리는 왜 쓰는걸까
데이터 탐색 속도 증진을 위해 사용하는 자료구조이다. 

 

FAQ-1. 이진 탐색 트리로 정렬해주는 시간 복잡도는 얼마일까?
Generally N * O(height of Tree) but, for worst case, O(N)

BST 역시 height에 의해 시간 복잡도가 영향을 받는다. 최악의 case로 skewed BST로 만들어졌을때, 탐색/삽입/삭제가 O(N)이 될 수 있다. 

 

skewed BST 탐색/삽입/삭제 시간 복잡도 

https://www.geeksforgeeks.org/complexity-different-operations-binary-tree-binary-search-tree-avl-tree/

AVL Tree

Balance Factor(BF) = height of left-side - height of right-side 를 활용해서 차이가 커지면 Rotation해준다.

이 때문에 항상 낮은 높낮이로 관리해주기에 시간 복잡도는 O(log2N)이다. 

AVL Tree 

https://www.geeksforgeeks.org/complexity-different-operations-binary-tree-binary-search-tree-avl-tree/

이진 트리 구현

class Node: # 바이너리 트리를 구성 할 노드 클래스 생성
    def __init__(self, root):
        self.data = data
        self.left = None
        self.right = None

 

 

이진 트리를 탐색하는 방법 (3가지)

전위 순회 (pre-order)

• 자기 자신을 출력한다. 
• 왼쪽 서브트리를 호출
• 오른쪽 서브트리를 호출

def preorder(node): # 전위 순회
    print(node.data, end='')
    if node.left != '': preorder(node.left)
    if node.right != '': preorder(node.right)

중위 순회(in-order)

• 왼쪽 서브트리를 호출
• 자기 자신 출력
• 오른쪽 서브트리를 호출

def inorder(node):
	if node.left != '': indorder(node.left)
    print(node.data, end='')
    if node.right != '': inorder(node.right)

후위 순회(post-order)

• 왼쪽 서브트리 호출
• 오른쪽 서브트리 호출
• 자기 자신 출력

def postorder(node):
	if node.left != '': postorder(node.left)
    if nod.right != '': postorder(node.right)
    print(node.data, end='')

 

순회라는 개념은 왜 쓰는걸까?

 

자료구조의 전반적인 내용

https://velog.io/@mrnglory/%EC%A0%95%EC%B2%98%EA%B8%B0-%EC%9A%94%EC%95%BD-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%AC-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%A0%95%EB%A0%AC

[정처기 요약] 자료구조, 트리, 정렬, 복잡도

https://pangyo-datascientist.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-binary-Tree

이진 트리-binary Tree