비선형자료구조3 [비선형 자료구조] - 균형 이진탐색트리 앞서 이진 탐색 트리는 O(logN) 이라는 시간 복잡도를 가져, 탐색 측면에서 이점이 있는데, 삽입 순서에 따라 한쪽으로 치우친 사향트리가 될 경우, O(N)의 시간 복잡도를 갖게 되어, 이점이 사라진다. 따라서 이러한 케이스에 대한 이진 탐색 트리의 단점을 보완하기 위해, 균형을 잡는 여러 방법들 중 AVL 트리에 대해 학습해보고자 한다. 이진 탐색 트리의 기본적인 특징은 여기서 참고! 🌳 균형 이진 탐색 트리란? ▪ 노드의 삽입과 삭제을 진행하면서, 균형을 자동으로 맟춰주도록 동작한다. ▪ 모든 노드의 좌우 서브 트리 높이가 2이상 차이 나지 않는 트리 ▪ 트리의 양쪽 높이 차이가 2이상 날 경우 : 삽입, 삭제, 탐색 등의 시간 복잡도 증가 ex. 사향트리 - 시간복잡도 : O(N) ▪ 종류에는 .. 2023. 12. 26. [비선형 자료구조] - 이진 탐색 트리의 특징, 삽입, 삭제, 검색 과정 앞서 트리에 대한 기본 특징은 여기서 참고 이진 트리는 트리 중에서도 최대 2개의 노드까지 가질 수 있는 트리이다. 🔎 이진 탐색 트리란? ▪ 크기 순으로 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드로 작성된 트리 ▪ 모든 트리의 구성은 위와 같은 규칙을 지키고 있으며, 중복된 키는 허용하지 않는다. - 검색 목적의 자료구조이기 떄문 ▪ 이진 탐색 트리를 순회할 경우, 중위순회 방법 사용 시, 정렬된 데이터를 얻을 수 있다. ▪ 정렬되어 있다는 특징 때문에 균형이 유지되어 있을 경우, 이진 트리에 비해 탐색이 빠르다. ▪ 균형 상태 : O(logN) ▪ 불균형 상태 : O(N) * 이진 트리 : 규칙이 없이, 정렬되지 않은채 저장된 트리 🤔 이진 탐색 트리는 왜 쓰는 걸까. ❓ ☑ 탐색 속도 향상.. 2023. 12. 26. [비선형 자료구조] - 트리 (Tree) 📗트리란? ✔ 노드와 링크로 구성된 자료구조로 주로 계층적 구조(Hierarchical Data Structure)를 나타내는데 사용된다 . 📗트리의 구조 ✔ Node (노드) : 트리 구조의 자료 값을 담고 있는 단위 ✔ Edge (간선) : 노드 간의 연결선 (link, branch) ✔ Height(높이) : 루트부터 현재 노드까지 거치는 간선의 수 ✔ Sibling Node(형제 노드) : 같은 부모의 자식 노드들 ✔ Leaf Node(리프 노드) : 자식 노드가 더 이상 존재하지 않는 트리의 맨 끝 단에 있는 노드 ✔ Depth(깊이): 자신을 제외한 부모 노드의 개수 ✔ Size(크기) : 자신을 포함한 자식 노드의 개수 ✔ Degree (차수) : 각 노드별로 가진 가지의 개수 ✔ 트리의 차.. 2023. 12. 14. 이전 1 다음
