250507 10일차

AVL트리
LL경우 R회전
RR경우 L회전
LR경우 R부분을 L회전후 L부분을 R회전
RL경우 L부분을 R회전후 R부분을 L회전
균형인자 (balance) 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
처음에 책만보고 균형인자가 계속 계승되는줄알았는데 그건아니고
높이를 계승해서 본인의 균형인자를 만드는것이었다.

해시
충돌처리 기법중에 이중해시 확인

그래프
방향 그래프 : 간선의 방향정보가 있는 그래프
무방향 그래프 : 방향이 없는 그래프 (어떻게보면 방향그래프로 양쪽을 서로연결한 것과 같음)
완전 그래프 : 모든 정점이 간선으로 연결되어있는 그래프
가중치 그래프 : 간선에 가중치(시간, 이동거리 등)의 정보가 있는 그래프
그래프의 특성상 최대 N:N이므로
방문 정보를 배열로 할시 공간소모가 크다 (그래프가 적을때 사용)
주로 리스트를 사용한다
그래프의 탐색또한 BFS / DFS 를이용
BFS : Queue  / 방문정보 정점 개수 배열
DFS : Stack / 방문정보 정점 개수 배열

최소신장트리 (MST)
크루스칼 알고리즘
-딱히 뭐가 있는것 같진 않았고 
간선정보 우선순위큐에 집어넣은뒤에
최대기준: 하나씩 빼면서 삭제 (E+1 == V 가 될때까지) + 간선삭제시 정점이 연결되있는가 체크
최소기준: 하나씩 추가 (E+1 == V 가 될때까지) + 간선추가시 정점이 이미 연결되어있는지 체크

프림은 언급만 나왔다.

 

오후 중간 부터는 Unity 로 AVL트리를 구현해보았다.

C#을 오랜만에 해봐서 오래걸렸고
처음에 GameObject안에 스크립트가 각자 개별처리하려다가 너무 추적이 힘들어서
AVLTree스크립트에서 전체 처리하였다.

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL Tree Visualzation

AVL시뮬레이터 참고하여 만들었다.


AVL처리하는데는 그렇게 오래 안걸렸는데
화면구성하고 트리 구성하는데만 시간다 걸렸다.
특히 저 트리 각 요소에 Width값을 예쁘게 하려고했는데 포기했다.
중요한건 학습용+구현하기 손풀기인데
쓸데없이 시간잡아먹는것 같아서  (최소 2시간은 쓴듯) 타협보고 넘어갔다.
시간만 안잡아먹었어도 delete 마우스로 선택해서 지우기 해보려고했는데 벌써 새벽이다
*약간의 이슈라면 책에는 |Balance| >=2 에서 자식노드가 |Balance| >=1일때의 경우만 처리되어있어서
0일때의 처리를 어떻게 하나싶었는데 알고보니 삽입과 동시에 회전조건을 체크 하는거였다 
테스트하느라 자동AVL처리 하지않고 버튼눌러서 했었다보니 일어났던 현상인듯..
+(최하단 노드기준 |value| >=2 가 가장 가까운것) 
내일 오전에 빠르게 처리하고 마무리 하고
다른것좀 해봐야겠다.