📚 Reference

📜 ****Chapter

AVL (Adelson-Velsky and Landis)

Backtracking

Binary Tree

B-Tree

Bellman-Ford

BFS (Breadth First Search)

BST (Binary Search Tree)

DFS (Depth First Search)

Dijkstra algorithm

Flood fill

Floyd Warshall

Heap

LCA (Lowest Common Ancestor)

LCS (Longest Common Subsequence)

LIS (Longest Increasing Subsequence)

MST (Minimum Spanning Tree)

Red-black tree

Segment tree

‣

Tree

• Tree
• 트리
• 특수한 구조를 가진 그래프
• 상, 하 관계가 분명한 그래프이다.
• 그래프이기에 똑같이 노드(Node)와 간선(Edge)으로 구성한다.
• 상위/하위 관계를 나눌 수 있다.
• cycle이 없다. → 트리는 사이클이 없어야 한다.
• 모든 노드가 연결되어야 한다.
• 노드의 개수: n
• 간선의 수 = n - 1
• 활용: 가계도, 조직도 등 많이 사용한다.

• root는 1개만 있다.