이론/자료구조 및 알고리즘2 트리와 그래프 트리와 그래프의 차이 가장 큰 차이점은 그래프는 순환이 가능하다는 점이다.그래프에서의 노드와 노드는 모두 동등 관계지만 트리에서는 부모노드와 자식노드가 존재하기 때문에 모든 노드가 동등한 입장이 아니다.또한 그래프는 가중치 및 방향성을 가질 수 있다. 2016. 10. 30. AVL 트리 Binary Search Tree에서 트리에 삽입되는 순서에 의해서 한쪽으로 치우친 트리가 형성될 수 있다. 균형잡힌 이진트리의 경우 탐색에 O(logn)의 시간복잡도가 걸리지만 한쪽으로 치우칠 경우 O(n)의 시간복잡도가 걸리게 된다. 따라서 이러한 단점을 해결한 트리구조 중에는 AVL 트리가 있다. AVL트리에는 Balance Factor라는 것이 존재한다.이것은 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이이다. 이 Balace Factor의 크기가 2이상일 경우 치우쳐진 트리라고 판단하고 흐트러진 균형을 맞추기위한 조치가 취해져야한다. 균형을 맞추기 위한 회전은 4가지 유형이 존재한다. 1. LL회전 2. RR회전 3. LR회전 4. RL회전 2015. 10. 5. 이전 1 다음
