알고리즘 Binary Search Tree 와 AVL트리 비교과제

•개발인원 : 1인

•개발기간 : 2019.08.27 - 2019 12.19

•개발도구 : VisualStudio. C++ 프로그래밍

노드의 수가 많아질수록 높이의 변화가 작아지지만, BST와 AVL트리의 높이차는 증가하는 것을 볼 수 있다.

노드 안에 있는 랜덤 값을 찾는 탐색시간은 높이와 비례할 것이라 예상하였는데 높이가 증가할수록 탐색시간이 늘어나는 것을 확인할 수 있다.

Binary Search Tree와 AVL트리의 높이를 구하기 위해서는 루트 노드의 Height값을 구하면 된다. 트리의 Depth와 Height는 서로 반대이기 때문에 Height값은 루트 노드가 가지고 있다.

Binary Search Tree와 AVL트리의 탐색시간을 구하기 위해서 Search함수에 count변수를 추가하였다. Count변수는 Search함수가 재귀호출 될 때 마다(노드를 거칠 때 마다)1씩 증가하여 값을 찾아냈을 때 리턴된다.

100개~3000개의 노드를 가진 트리를 각각 100개씩 만들어야 하기 때문에, 100개~3000개의 노드를 가진 트리 각각을 만드는 것을 100번 반복하도록 했고, Height와 탐색시간을 따로 저장한 후 트리를 바로 삭제함으로 불필요한 메모리의 유지를 줄였다.

메모리의 삭제는 Postorder를 사용했는데 leaf노드부터 차례차례 삭제해 가기 위함이다.

마지막으로 Height와 탐색시간이 입력된 배열의 원소들에 100을 나눈다.(평균을 구하기 위함)

Binary Search Tree와 AVL트리를 동일한 데이터를 사용하여 만들었을 때, Binary Search Tree의 Height보다, AVL트리의 Height가 더 작다.

Binary Search Tree와 AVL트리를 동일한 데이터를 사용하여 만들고 동일한 노드를 탐색했을 때, Binary Search Tree의 탐색시간 보다, AVL트리의 탐색시간이 더 작다.

트리의 높이가 증가할수록, 데이터를 탐색하는 시간도 증가한다.

트리를 만드는 시간을 배제했을 때, Binary Search Tree와 AVL트리중 탐색에 더 효율적인 트리는 AVL트리이다.

노드의 수가 증가할수록 트리의 높이의 변화는 더 적어진다. (트리의 높이가 lgn 임을 볼 수 있다.)

EnjcatStudio