BST
-
[자료구조] 균형트리 - AVL Tree(Adelson-Velskii-Landis Tree)코딩(Coding)/자료구조 2021. 1. 14. 11:39
AVL Tree(Adelson-Velskii-Landis Tree) 개념 AVL Tree는 기존의 BST에서 편향된 모양을 최대한 억제한 Tree이다. 음... 그림으로 말하자면,,, 위 그림처럼 입력이 10,20,30,40,50 순으로 입력되었다고 하자 내가 50Node를 탐색하려면 총 4번의 탐색이 필요하다 결국, 저렇게 편향된 BST는 그냥 선형 자료구조와 다름이 없다... 한 마디로 효율이 떨어진다는 것이다. 따라서 저러한 편향된 모양을 최대한 억제한 것이 바로 AVL이다. 균형인수(Balancing-Factor) AVL은 그렇다면 규형을 어떤식으로 맞춰야 하는가... 바로 균형인수(Balancing-Factor)라는 새로운 자원을 통해 균형을 맞춘다. 균형인수는 특정 노드의 왼쪽 서브트리와 오른..
-
[자료구조] BST - 이진탐색 트리(Binary Search Tree)코딩(Coding)/자료구조 2021. 1. 7. 11:04
이진 탐색 트리 BST(Binary Search Tree) BST는 각각의 Node가 2개의 하위 노드를 가진 모양의 Tree이다. 단 BST는 정렬된 상태로 Node가 저장된다. 즉 순서가 있다는 것이다. 쉽게 이야기 하자면 특정 노드가 있을때 그 노드의 왼쪽 하위 노드는 해당 노드보다 data값이 작아야하며 반대로 오른쪽 하위 노드는 data값이 해당 노드보다 커야한다. 그림을 통해 확인해 보면 위 그림을 확인해 보자 root노드인 50의 왼쪽 node의 data 값은 30이고 오른쪽 노드의 data값은 90이다. 해당 규칙을 지키며 tree를 구성한 것이 BST이다. 설계 그렇다면 바로 구현을 시작해보자 Node 설계 우선은 Tree의 각각의 노드를 설계할 것이다. 그림에서 처럼 좌우의 하위 Nod..