[Data Structure] Binary Search Tree(BST)

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