[자료구조] 이진 트리(Binary Tree), 이진 탐색 트리(BST, Binary Search Tree)

 

이진트리(Binary Tree)

---

각 노드가 최대 2개의 자식노드를 가지는 트리 자료 구조이다. 

최대 2개이기 때문에 자식이 없을 수도 있고, 한개만 있을 수도 있다.

 

 

이진트리와 이진탐색트리는 다른 개념이기 때문에 헷갈리지 말자!
이진 트리는 많은 응용 트리의 기초가 된다.
B-Tree, 힙(heap) 또는 이진탐색트리(BST)도 이진트리의 응용이다.

이진 트리 DFS기반 탐색 알고리즘

전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)

이진트리 전체 노드를 탐색할 수 있다.

 

 

이진 탐색 트리(Binary Search Tree)

---

왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진 트리이다.

이진 탐색에 트리의 개념이 더해진 것으로 특정 값을 탐색하는 것에 빠른 성능을 보여준다.

때문에 중위순회(inorder traversal)를 하면, 오름차순으로 정렬된 순서로 key값을 얻을 수 있다.

-> 이진 탐색 트리도 일종의 이진 트리이기에 순회 가능

 

이진탐색트리 특징

• 부모 노드의 왼쪽 노드는 부모 노드보다 작아야 한다.
• 부모 노드의 오른쪽 노드는 부모 노드보다 커야 한다.
• 왼쪽, 오른쪽 하위 트리도 각각 이진 검색 트리여야 한다.
• 중복된 키를 허용하지 않는다.

이진 탐색 트리

 

 

 

 

참고 

https://velog.io/@dlgosla/CS-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-Binary-Tree-vzdhb2sp

[CS - 자료구조] 이진 트리 (Binary Tree) 개념과 종류

https://yoongrammer.tistory.com/71

[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)

https://kangworld.tistory.com/51