엔지니어 대한민국 님의 영상을 참조하였습니다.

https://www.youtube.com/watch?v=LnxEBW29DOw&ab_channel=%EC%97%94%EC%A7%80%EB%8B%88%EC%96%B4%EB%8C%80%ED%95%9C%EB%AF%BC%EA%B5%AD

📌 개념

각 노드들이 층위를 갖고 있다. 노드들이 하나 이상의 자식을 갖고 있으면 tree라고 부른다.

마지막 노드를 leaf이라고 부른다.

📌 이진트리 ( Binary Tree )

각 노드들에 자식이 2개씩만 붙는 형태

📌 이진 검색 트리

왼쪽 노드와 그 이하의 child node들은 부모 노드보다 작아야 한다.

그래서 큰 값을 찾고 싶으면 무조건 오른쪽, 작은 값을 찾고 싶으면 무조건 왼쪽으로만 가면 되는 형태.

🔥 Balance

밸런스가 어느정도 맞으면 밸런스가 맞다고 한다.

• red-black tree, AVL 트리 등이 balanced 트리이다.

🔥 완전 이진 트리

왼쪽부터 채워져 있으면 완전 이진 트리

🔥 Full-binary tree

노드들의 트리가 꽉 차있거나 하나도 없거나 일때

🔥 Perfect-binary tree

모든 노드들이 full인 상태

📌 Binary Tree 순회

PreOrder, InOrder, PostOrder