본 게시글은 학부 강의 '자료구조' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 2-3 트리의 구현이 너무 복잡해..2-3 트리를 이진 트리처럼 만들어 보는거야!! BST에 융통성이 생긴 2-3 트리. 성능도 좋았지만 노드가 많아지면서 노드 구조가 복잡해졌다. 그러기에 경우의 수가 너무 많아지는게 문제였다.2-노드와 3-노드를 처리해야 하고삽입, 삭제 시 너무나도 다양한 케이스들이 존재했다.메모리 효율성 측면에서도 항상 3개의 자식 포인터 공간이 필요했다. 그래서 2-노드일 때 하나는 낭비가 된다. 그래서 좀 더 나은 방법은 없을까? 레드 블랙 트리노드에 색을 부여하여 트리의 균형을 유지탐색, 삽입, 삭제 연산의 수행 시간이 각각 O(lo..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 이진 트리가 아니어도 괜찮아! 노드에 키를 2개까지 넣어보자!! 자료구조 등의 여러 컴퓨터 과학 과목을 듣다보면 모든 테크닉에는 장단점이 명확하게 존재했다. 그래서 단점을 보완한 새로운 테크닉이 등장해도 거기에는 또 다른 단점이 생겼고 보완되기 위해 지금도 새로운 방법론들이 계속 제시되고 있다. 2-3 트리도 아이디어와 함께 이전 트리의 단점을 보완하기 위해 탄생했을 것이다. 앞서 작성한 이진 탐색 트리에는 단점이 존재했다. 일반적인 BST에는 최악의 경우..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. AVL 트리(Hight Balanced Binary Trees)AVL 트리는 Adelson-Velskii & Landis Tree 라고도 한다. 만든 사람의 이름을 땄다.AVL 트리는 트리가 한쪽으로 치우치는 것을 방지하여 트리 높이의 균형을 유지균형(Balanced) 이진 트리 : 탐색, 삽입, 삭제 연산의 수행 시간 O(logn) 보장 AVL 트리는 삽입이나 삭제로 인해 균형이 어긋나면 회전 연산을 통해 트리의 균형을 유지한다. AVL 트리는 임의의 노..

본 게시글은 학부 강의 '자료구조', 온라인 강의 'Honglab Data Structure(https://www.honglab.ai/)' 그리고 강의 교재 '자바와 함께하는 자료구조의 이해'의 내용들을 바탕으로 이해한 내용을 정리하였습니다. 트리 배열이나 연결 리스트 - 데이터를 일렬로 저장하므로 탐색을 순차적으로 수행정렬된 배열에서는 이진 탐색을 통해 효율적인 탐색이 가능하지만, 삽입 / 삭제 후 정렬 상태를 유지하기 때문에 O(n) 시간일반적인 트리(General Tree)는 트리를 거꾸로 세워놓은 형태의 자료구조HTML과 XML의 문서 트리, 자바 클래스 계층구조, 운영체제의 파일시스템, 탐색트리, 이항(Binomial) 힙, 피보나치(Fibonacci) 힙과 같은 우선순위 큐공집합도 트리..