건빵의 블로그

앞에서 언급했던 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) 노드의 엔..

트리는 이산수학에서도 다뤘기 때문에 간단히 패스하고 지나간다. 기억을 되새길겸 짚어보자면 Tree는 Acyclic connected graph이다. 그리고 몇가지 특성들을 가지는데 그것은 패쓰~ 트리는 트리 자체도 중요하지만 트리의 응용으로 나오는 다른 트리들이 중요하다. Binary Tree는 각 노드가 차일드 2개를 가지며 left랑 right로 구별되는 트리이다. Full binary Tree는 모든 leaf의 depth가 같은 트리를 말한다. Complete Binary Tree는 Full binary tree에서 맨 오른쪽 leaf부터 순서대로 제거된 형태를 띄는 것을 말한다. 그리고 오늘의 주인공 Binary Search Tree는 각 노드 값이 왼쪽 서브트리의 값들보다 크고, 오른쪽 서브트리..