ETC/Data Structure 썸네일형 리스트형 KD Tree / KDB Tree K-D Tree(K = 숫자, D = Demension, 차원) k-d tree는 다차원의 점 data를 index할 수 있는 가장 간단하면서도 기본적인 data 구조이다.k-d tree는 일반적으로 disk의 저장을 고려하지 않고 주 기억장치 상에서 동작하는 index 구조이다.따라서 대용량의 data에 대해서는 적당하지 않고 소규모의 다차원 점 data를 index할 때 적당하다. 즉 Binary Search Tree를 다차원 공간으로 확장한것, 기본 구조와 알고리즘은 BST와 유사하지만 Tree의 level차원을 번갈아 가며 비교한다는게 차이점이다. 특징 주 기억장치에서 동작소규모의 다차원 점 data를 인덱싱할때 적합(PAM)balanace tree가 아님 삽입 삽입하려는 data key valu.. B Tree / B* Tree / B+ Tree B Tree(Balanced Tree) 균형트리로서 기존에 자식을 2개만 가질 수 있던 Binary tree를 확장하여 더 많은 자식을 가질 수 있는것기존의 binary tree의 경우 추가, 검색, 삭제등에 O(NlogN)의 시간복잡도를 보여주었고좌우 균형이 맞지않는 최악의 경우 O(N*N)의 시간복잡도를 가지게 된다. B-Tree란 하나의 node에 어러자료가 배치되는 tree 구조이다.한개의 node에 M개의 자료가 배치되면 M차 B-tree라고 한다.5차 B-Tree인경우 자식노드가 최대 5개인 것을 의미한다.B-Tree는 스스로 균형을 맞추는 tree이다. 그래서 최악의 경우에도 O(logN)의 검색성능을 보인다.또한 B-tree는 하나의 node에 많은 수의 data를 저장할 수 있다. 조건 .. 이전 1 다음
