[Data Structure] B-tree

앞에서 언급했던 Binary Search Tree의 단점을 생각해 보자. 트리가 skewed tree 또는 지그재그 트리 형태로 자라난다면 비효율적인 자료구조가 된다. 우리의 목적은 효율적인 자료구조를 만드는 것이기 때문에 뭔가 보완이 필요하다는 것을 알수가 있다. 그래서 나오는 것들이 Balanced Tree 종류이다. 트리의 Leaf들의 Depth들이 균형 잡힌 형태로 되도록 한다. 그 예로는 B-tree, AVL tree, Red-black tree 등등이 있으며 B-tree와 AVL tree에 대해서 공부해 보았다. B-tree의 성질은 다음과 같다. 1) B-tree는 BST와 같은 Search tree를 구성하되 각 노드가 여러 개의 엔트리를 가진다.(하나의 노드에 값 여러개) 2) 노드의 엔..
Computer Science 2011. 7. 4. 23:21
1