그냥 하는 노트와 메모장

이진 탐색 트리(BST)[ Introduction to Algorithm Chap 12 연습문제 풀이 ] Section 1)12.1-1) 이진 검색 트리 조건을 만족하도록 아무거나 만들면 된다. 12.1-2) 이진 탐색 트리는 현재 노드에 대해 왼쪽 서브 트리보단 크거나 같고, 오른쪽 서브 트리보단 작거나 같다는 것으 보장하지만, 최소힙은 모든 자식 중에서 가장 작은 값만을 보장한다(왼쪽 오른쪽 구분이 없다). 따라서 정렬된 데이터를 얻고 싶을 경우, 최소힙은 선형 시간을 가진다고 보장할 수 없다. 12.1-3) [ TODO ] 12.1-4) PREORDER-TREE-WALK(x) if x != NIL print(x) PREORDER-TREE-WALK(x.left) PREORDER-TREE-WALK(x...

* 이진 탐색 트리(BST, Binary search tree) 이진 트리에서 사용할 수 있는 이진 탐색 트리 개념과 단점 그리고 그 개선안에 대해 작성하고자 한다. - 이진 탐색 트리에서 사용하는 구조체에 쓰이는 데이터는 아래와 같다. 1. left - 왼쪽 자식 포인터. left.key = key를 만족한다. 3. key - 비교 대상 데이터. 4. satellite data - 부속 데이터. 5. p - 부모 노드 포인터. - 정렬된 데이터 얻기 1. y가 x의 왼쪽 서브 트리의 한 노드라면 y.key = x.key를 만족한다. 따라서 중위 순회 결과(Inorder)는 정렬된 데이터를 얻을 수 있음을 알 수 있다. * 기능1. 검색 딱 맞는 키가 있거나 그 값이 NIL이면 해당 노드 포인터를 반환한..