Soongle's Morgorithm

AVL 트리란, George Adelson-Velsky와 Evgenii Landis가 발표한 최초의 균형잡힌 이진트리(balanced binary tree)이다. AVL 트리 클래스를 Node구조체를 사용한 링크 표현법으로 구현하였다. AVL 트리의 가장 핵심적인 기술은 바로 회전(Rotation)이다. RR, LL, RL, LR 네 가지 경우에서의 회전을 통해 트리 전체의 좌우 균형을 맞추기 때문이다. 이렇게 균형이 맞춰진 트리는 값을 탐색할 때 최악의 경우에도 O(log n)의 시간안에 탐색을 끝낼 수 있다. 각각의 회전을 해야하는 경우는 아래와 같다 RR : 오른쪽, 오른쪽으로 치우친 경우 → 현재 노드 기준으로 왼쪽으로 회전시킨다 LL : 왼쪽, 왼쪽으로 치우친 경우 → 현재 노드 기준으로 오른쪽..

이진 탐색 트리란, 다음과 같은 특징을 갖는 이진 트리이다 모든 노드의 값은 유일하다. 왼쪽 노드의 값은 자신의 값보다 작다. 오른쪽 노드의 값은 자신의 값보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 이진 탐색 트리 클래스를 Node 구조체를 사용한 링크 표현법으로 구현하였다. 모든 함수들은 재귀로 구현하였다. #include #include using namespace std; struct Node { int data; Node* left; Node* right; }; class BinaryTree { public: BinaryTree(); ~BinaryTree(); int size(); int height(); bool search(int key); bool insert(int ite..