justgo_developer

이진검색트리(Binary Search Tree)-Dynamic set을 트리의 형태로 구현 정의-이진트리이면서 각 노드에 하나의 키를 저장- 각 노드 v에 대해서 그 노드의 왼쪽 부트리(subtree)에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.**Binary Search Tree하고 heap은 다르다. 최소값 찾기: 왼쪽 자식이 없어야 하고 어떤 노드의 오른쪽 서브트리이면 안된다. TREE-MINIMUM(x)while left[x]≠NILdo x

검색트리(Search Tree) 트리(Tree)란?-계층적인 구조를 표현(조직도,디렉토리와 서브디렉토리 구조, 가계도) 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨. 부모(parent)-자식(child) 관계 형제관계 :부 모가 동일한 노드들 리프(leaf) 노드 : 자식이 없는 노드들 내부(internal)노드 : 리프노드가 아닌것 조상-자손관계 : 부모-자식 관계를 확장한 것 부트리(subtree)레벨(level)트리의 높이는 : 서로다른 노드의 갯수 트리의 기본적인 성질-노드의 n개일때 링크의 갯수는 n-1이다.-트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두노드간의 경로도 유일하다. 이진트리(binary tree)-이진트리에서 각 노드는 최대 2개의..