1. 자료구조 확장 Data structures augmentation 코딩

Rank 구현

Rank(t) = how many scheduled <= t
t보다 작거나 같을 때 얼마나 스케쥴이 있는지 개수를 세는데 사용한다

Rank(t)를 구하는 과정으로는
1. walk down(본인 key값보다 작을 때) + 1
2. 1번 + 왼쪽 서브트리의 개수
이후 오른쪽 서브트리로 이동한다 만약 key보다 작은 값을 찾았다면 왼쪽 서브트리로 이동한다
3. key와 같은 값을 찾았다면 +1을 하고 왼쪽 서브트리로 이동한다
4. NULL에 도달할 때까지 2의 과정을 반복한다
5. NULL에 도달했다면 지금까지 센 개수를 반환한다

key값보다 큰 노드의 개수를 찾아볼 수도 있는데 이는 위 과정에서 왼쪽 오른쪽을 바꿔서 진행하면 된다
위 과정을 진행하다보면 중복되는 값이 저장될 수도 있다

예시로 Rank(50)을 구하는 방법을 그림으로 표현해 보았다

이제 이 그림을 구현해보자면
로 나타낼수 있다

https://dapin1490.github.io/satinbower/posts/it-bst-rank/
에서 도움을 받았다

AVL tree 구현

https://www.geeksforgeeks.org/avl-tree-set-1-insertion/
https://www.geeksforgeeks.org/avl-tree-set-2-deletion/
https://srdeveloper.tistory.com/29
의 도움을 받아서 작성하였다
여기서 구현되는 RR, LL, LR, RL은 아래 AVL tree정리에서 그림을 통해 표현해 볼 것이다삽입 연산 관련 코드
삭제 연산 관련 코드

위 Rank에서 사용한 {3,20,24,29,42,50,67}을 사용해서 main문을 사용하면

이 나온다

2. AVL tree 정리

AVL tree란?

왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1이하인 이진 탐색 트리

이 트리는 트리가 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 바꾼다
항상 균형 트리를 보장하기 때문에 탐색 시간이 O(log n)이다

비균형 상태일때 4가지 방법을 통해 재균형을 맞추면 된다
1. LL 회전: A부터 N까지의 경로상 노드의 오른쪽 회전
2. LR 회전: A부터 N까지의 경로상 노드의 왼쪽-오른쪽 회전
3. RR 회전: A부터 N까지의 경로상 노드의 왼쪽 회전
4. RL 회전: A부터 N까지의 경로상 노드의 오른쪽-왼쪽 회전

LL회전과 RR회전은 단순 회전 알고리즘이고 LR회전, RL회전은 이중 회전 알고리즘이다

그림으로 표현하자면
로 표현할 수 있다

탐색 연산: 이진 탐색 트리와 동일하게 진행

삽입 연산: 불균형 상태가 발생하면 발생한 위치에서 가장 가까운 서브 트리들에 대하여 다시 재균형을 맞춘다
다음은 AVL 트리에 1을 삽입했을 때 재균형을 맞추는 예이다

삭제 연산: 삭제 연산시 불균형 상태가 발생하면 삽입연산과 같이 다시 재균형을 맞춘다

문제풀이

leetcode 110 : 주어진 이진트리가 균형이 맞는지 확인

https://leetcode.com/problems/balanced-binary-tree/solutions/577388/leetcode-110-c-booksun/
https://myeongcs.tistory.com/145
의 도움을 받아 작성하였다

dfs를 이용하여 코드를 짰고 -1일 때 false, 0일 때 true가 출력되는 bool을 사용한다
leftHeight와 rightHeight의 높이를 탐색하여 둘의 차가 1보다 크면 -1이 반환되고 false가 출력되게 한다