Algorithm/알고리즘 (18) 썸네일형 리스트형 [알고리즘](C언어) 트리 탐색을 이용한 사전의 트리 구현 - 이진탐색트리(BST) 탐색 트리의 종류로 두 가지를 다룬다. 이진탐색트리와 AVL 트리이다. 1. 이진탐색트리(BST) 내부노드에 (키, 원소) 쌍을 저장하며 다음의 성질을 만족하는 이진트리 이진트리와는 다르다! 탐색이 가능해야하는 이진탐색트리다. u, v, w가 모두 트리노드일 때, u와 w가 각각 v의 왼쪽과 오른쪽 부트리에 존재할 때 다음이 성립해야 한다. key(u) < key(v) 중위순회 후계자 y는 T를 중위순회할 경우 노드 w 바로 다음에 방문하게 되는 내부노드이므로 w의 중위순회 후계자(inorder successor)라 불린다. 따라서 y는 w의 오른쪽 부트리 내 노드 중 가장 왼쪽으로 돌출된 내부노드 2. y의 내용을 w에 복사 3. reduceExternal(z) 작업을 사용하여 노드 y와 z를 삭제 r.. [알고리즘](C언어) 사전 ADT 개념, 선형 탐색과 이진 탐색을 이용한 사전의 리스트 구현 1. 사전 ADT 탐색 가능한 형태의 (키, 원소) 쌍 항목들의 모음을 모델링 주요 작업 탐색(searching) 삽입(inserting) 삭제(deleting) 사전의 종류 무순사전 순서사전 2. 사전 ADT 메쏘드 일반 메쏘드 integer size() 사전의 항목 수를 반환 boolean isEmpty() 사전이 비어 있는지 여부를 반환 접근 메쏘드 element findElement(k) 사전에 키 k를 가진 항목이 존재하면 해당 원소를 반환 그렇지 않으면 특별 원소 NoSuchKey를 반환 갱신 메쏘드 insertItem(k,e) 사전에 (k,e) 항목을 삽입 element removeElement(k) 사전에 키 k를 가진 항목이 존재하면 해당 항목을 삭제하고 원소를 반환 그렇지 않으면 특별 .. 이전 1 2 3 다음
