컴공생의 개인공부일지

B - 트리란? 이진트리와는 반대로 자식 노드가 2개 이상인 트리 B - 트리의 조건 모든 단말노드는 동일한 높이 각 내부노드의 자식노드는 M/2 이상, M 이하 루트의 자식 수는 2개 이상 노드의 키가 x개라면 자식의 수는 x+1개 자료는 정렬된 상태로 저장 B-Tree의 장점 포인터의 접근 방식이 적어서 속도 이슈가 적음 B-Tree는 Balanced Tree로 트리내에 모든 데이터가 정렬된 상태를 유지하기 때문에 등호(=)연산 뿐 아니라 부등호()연산도 가능하다. 데이터의 삽입과 삭제, 탐색의 시간복잡도가 O(logN)으로 동일 B-Tree는 삽입과 삭제 후에도 균형 트리 유지로 균등한 응답 속도를 보장 B-Tree의 단점 삽입과 삭제 시 트리의 균형을 유지하기 위해 복잡한 연산을 수행 순차탐색시 ..

트리를 이용한 DB 설계의 장 / 단점 및 트리의 한계 해결 DB를 설계할 때 주로 사용되는 자료구조는 B-Tree이다. [ ] 다른 자료구조를 DB로 사용 할 수 없는 이유 1. 해시 테이블의 경우 해시 테이블은 단 하나의 데이터를 탐색하는데 O(1) (최악의 경우 O(N)이지만 평균적으로 O(1))의 시간복잡도를 가지만, DB에서는 등호(=) 뿐만 아니라 부등호()도 사용 → O(1)의 시간복잡도를 보장 할 수 없고, 비효율적 2. 레드-블랙트리의 경우 레드-블랙트리는 하나의 노드에 하나의 요소를 저장하지만, B - 트리의 경우 하나의 노드에 배열처럼 여러개의 데이터 요소를 저장 → 같은 공간의 노드를 참조 포인터로 접근 할 필요가 없음 → 동일 메모리에서 작동 → 두 트리 모두 O(logN)의 시간..

레드-블랙 트리란? 각각의 노드가 레드나 블랙인 색상 속성을 가지고 있는 이진 탐색 트리 이진 탐색 트리가 가지는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한 레드-블랙 트리이다. 노드는 레드 또는 블랙 루트 노드는 블랙 모든 리프 노드는 블랙 레드 노드의 자식은 모두 블랙 → 루트부터 리프 노드까지의 경로에 레드가 연이어 올 수 없다 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 존재 위 조건으로부터, 루트로부터 가장 긴 경로가 가장 짧은 경로의 길이의 두 배를 넘지 않는다. 이를 개략적으로 균형이 잡혀 있다(roughly balanced)고 한다. → 최악의 시간복잡도가 트리의 높이(깊이)에 따라 결정되므로 보통의 이진트리보다 효율적 💡 4와 5번째 규칙에 의해 ..

AVL 트리란? 스스로 균형을 잡는 이진 탐색 트리 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 사용 → 스스로 균형을 잡아 편향을 방지 → 트리의 높이가 h일때 시간 복잡도는 O(h) AVL트리의 특징 이진 트리의 속성을 가진다 왼쪽, 오른쪽 서브 트리의 높이 차가 최대 1이다 높이 차이가 1보다 커지면 회전을 통해 균형을 잡는다 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다 Balance Factor(BF) 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값 💡 Balance Factor BF(K) = left(K) - right(K) BF = 1 → 왼쪽 서브트리가 높음 BF = 0 → 양쪽의 높이가 같음 BF ..

트리란? 트리라는 용어는 아서 케일리의 논문에서 처음으로 사용 “A theorem on trees”. 《The Quarterly Journal of Pure and Applied Mathematics》 스택과 큐, 데크 등의 선형 자료구조로는 표현할 수 없는 자료를 표현하기 위해 만들어진 것 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조 즉, 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조를 말한다. 💡 부모노드 : 루트 노드 방향으로 직접 연결된 노드 자식노드 : 루트 노드 반대방향으로 직접 연결된 노드 루트노드 : 트리에서 부모가 없는 최상위 노드, 트리의 시작점 트리의 종류 이진트리 이진트리 이진탐색트리 완전이진트리 ..