ArrayList
초기 버퍼 크기에 따른 성능
LinkedList
요소 삽입, 추가 성능측정
ArrayList vs LinkedList
Queue
큐는 직접 구현한 LinkedList를 활용하여 구현
Stack
스택은 직접 구현한 ArrayList를 활용하여 구현
Binary Tree
트리 순회에 있어 재귀호출 방식은 성능저하가 있어서 이를 반복문으로 처리
Binary Search Tree
Binary Search Tree는 Binary Tree로부터 상속을 받는 구조
AVL Tree
AVLTree는 Binary Search Tree에게 상속받는 구조
알고리즘 및 성능
처음에는 노드를 추가하고 삭제할 때마다 모든 노드의 밸런스 팩터를 다시계산 함.
하지만 이 방법은 모든 노드를 순회해야하기 때문에 매우비효율적임
그래서 노드를 추가하고 삭제할 때 영향을 받은 최하단 노드로부터 루트노드까지만 밸런스팩터를 다시 계산하도록 개선하였더니 성능이 크게 향상.
Binary Search Tree vs AVL Tree
Heap
힙을 트리로 구현해보니 가장 마지막 단말 노드를 찾는 비용이 매우 컸음.
층별 순회가 가장 손쉬웠지만 실사용에는 절대 적용할 수 없을 정도로 느린 반면에 배열힙은 완전 이진트리라는 힙의 특성상 최적의 구현 방식.
