📒 CS/📝 Data Structure

[Data Structure] AVL 트리

2023.08.19

AVL 트리 AVL 트리 (Adelson-Velsky and Landis tree)는 이진 탐색 트리가 데이터 삽입 순서로 인해 선형적인 형태의 트리가 되는 것을 방지하고자 스스로 균형을 잡는 이진 탐색 트리를 말한다. 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다. (균형 이진 트리의 일종) 데이터 삽입, 삭제시 균형이 항상 맞도록 트리 일부를 왼쪽 혹은 오른쪽으로 회전시킨다 (리밸런싱). 🔹가장 처음 나온 자가 균형 이진 트리 🔹red-black tree보다 균형은 훨씬 잘 잡힘 🔹red-black tree보다 삽입, 삭제가 느림 🔹서브 트리 높이 차이가 1보다 커지면 회전(리밸런싱) 통해 차이 줄임 💡탐색, 삽입, 삭제 시간 복잡도: O(logN) Balance Factor..

[Data Structure] 그래프 - 인접행렬과 인접리스트

2023.08.19

그래프 (Graph) 그래프는 정점과 간선으로 이루어진 비선형 자료 구조를 말한다. 🔹정점(V) (vertex) - 그래프 내의 하나의 개별적 요소 🔹간선(E) (edge) - 정점과 정점 사이를 연결하는 선 (흐름, 관계 표현) 🔹가중치(W) (weight) - 간선과 정점 사이에 드는 비용 🔹차수 (degree) - 정 정점에 연결된 간선의 수 ◽out-degree: 다른 정점으로 나가는 간선 (수) ◽in-degree: 특정 정점으로 들어오는 간선 (수) ◽무방향 그래프에선 하나의 간선이 두 정점에 인접하므로 간선 수의 두 배 💡 비선형 자료 구조 비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다. 일반적으로 트리나 그래프를 말한다. 방향 그래프(Diredted Gr..

[Data Structure] AVL 트리

[Data Structure] 그래프 - 인접행렬과 인접리스트

티스토리툴바