오늘 한 일

AVL 균형이진트리를 짜봤다. 

이진탐색트리를 다시 보고 웹 크롤링 강좌 듣기를 시작했다. 

레드블랙트리는 익숙해지도록 2번 읽어보기만 했다. 

생각거리

어수선하다..

균형 이진 탐색 트리란?

오른쪽 서브트리의 높이와 왼쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리를 말합니다.

이러한 높이 차이를 균형인수(Balance Factor) 라고 합니다. (BF)

AVL 트리는 삽입 또는 삭제로 트리가 균형을 잃었을 때 스스로 노드를 재배치하여 위의 조건을 다시 맞춥니다. 

( BF가 1 이하:   1, 0, 1 중에서 값을 가집니다. )

[장점]

BF가 1 이하이므로(높이 차이가 거의 비슷하기 때문에) 탐색, 삽입, 삭제 모두 O(log2n) 시간 안에 가능합니다. 

균형 없는 트리라면, 한쪽으로만 자라날 수 있기 때문에, 최악의 경우 시간 복잡도가 O(n)이 됩니다. 

[취약점]

자료가 많아지면 트리의 높이가 커지는 문제가 있습니다.

자료 삽입삭제가 자주 일어나면 균형을 유지하느라 재배치에 쏟는 시간이 많아질 수 있습니다. 

AVL TREE 라는 이름은 만든 사람 2명의 앞글자를 딴 것입니다. 아델슨 벨스키(Abelson-Velskii)와 라딘스(Landis)

균형을 잃은 4가지  경우

(전제)

root 노드를 기준으로 왼쪽, 오른쪽을 구분한다. 

root : 초기 부모

pivot : root의 자리를 대신할 자식 

LL과 RR은 한 번만 회전하는 단순회전이고, LR, RL은 두 번 회전하는 이중회전 입니다.

어떤 방향에 따라 부모와 자식 원소의 위치를 바꾸면 됩니다. 

1. LL (Left-Left) : 오른쪽으로 회전

노드 '3'을 오른쪽으로 회전한다. 노드 '3'이 노드 '2'의 자식이 된다. 

균형이 왼쪽 서브 트리의 왼쪽 서브 트리에 의해 깨진 경우. 오른쪽 방향으로 회전한다.

다시 말하면, 루트 노드의 왼쪽 자식노드의 왼쪽 서브트리에 의해 균형이 깨진 경우를 말한다. 

2. RR (Right-Right) : 왼쪽으로 회전

'1' 노드가 '2'노드의 자식이 된다.

루트노드 1을 기준으로 생각한다.

1의 오른쪽 서브 트리(2)의 오른쪽 서브 트리(3)에 의해 균형이 깨진 경우. 왼쪽 방향으로 회전한다. 

루트 노드의 오른쪽 자식노드의 오른쪽 서브 트리에 의해 균형이 깨진 경우를 말한다. 

3. LR ( Left-Right): LL회전 후에 RR회전

루트 노드 3을 기준으로 보자.  

왼쪽 서브 트리의 오른쪽 노드인 1과 2를 먼저 왼쪽으로 회전한다.

왼쪽 서브트리를 오른쪽으로 회전하여 3이 2의 자식이 되도록 한다. 

루트 노드 3을 기준으로, 루트의 왼쪽 서브트리(1)의 오른쪽 서브 트리(2)가 균형을 잃은 경우.

왼쪽으로 회전 후 오른쪽으로 회전한다. 

( 루트의 왼쪽 서브트리의 오른쪽 서브 트리를 왼쪽으로 회전하고, 루트와 루트의 왼쪽 서브트리를 오른쪽으로 회전한다. )

4. RL (Right-Left) : RR 회전 후에 LL회전

루트 노드 1을 기준으로 보자. 

오른쪽 서브트리가 균형을 잃었다. 

오른쪽 서브트리의 왼쪽 자식을 오른쪽으로 회전한다. 2와 3을 오른쪽으로 회전.

그리고 루트노드의 오른쪽 자식 '2'를 기준으로 왼쪽으로 회전한다. 

 루트 노드의 오른쪽 서브트리의 왼쪽 서브트리가 균형을  잃은 경우.

오른쪽으로 회전 후, 왼쪽으로 회전한다. 

( 왼쪽 서브 트리를 오른쪽으로 회전 후. 루트 노드와 오른쪽 서브 트리를 왼쪽으로 회전한다. )

탐색

이진 탐색 트리의 연산과 같습니다. 

삽입 

회전을 이해해야 한다. 

오른쪽 회전, 왼쪽 회전 두 가지를 기반으로 기본 연산을 한다. 

LeftRotate() : 왼쪽방향으로 회전 

RightRotate() :오른쪽방향으로 회전 

leftRightRotate() : 왼쪽, 오른쪽 방향 회전 

rightLeftRotate() : 오른쪽, 왼쪽 방향 회전 

[ 참고 포스팅 ]

https://edu-coding.tistory.com/43

http://egloos.zum.com/printf/v/913998

오늘 할 일 

레드블랙트리를 공부하기전에, 균형이진탐색트리 (AVL트리)를 공부했다.

생각거리 

소중한 사람들로부터 큰 축하를 받아서 행복한 한 주 였다. 

오늘 한 일 

이진탐색트리를 짜고, 레드블랙트리를 읽어만 봤다. 

레드블랙트리는 내일도 다시 복습해야겠다. 반복 학습할 내용이 많다. 

생각거리 

레드블랙트리는 어려웠지만, 이렇게 문제 해결 방법을 착착 정리해둔 사람이 누구인지 참 똑똑하다는 생각이 든다. 

오늘 한 일 

용역 플젝 DB 1차 설계를 PL에게 설명하고 피드백 받았다.

게시판 관련 설계를 빼먹어서 게시판 관련 테이블을 추가해야 한다.

피드백 받은 것 반영해서 2차 설계를 완성했다. 

생각거리

날씨가 너무 좋아서 싱숭생숭하다.

오늘 한 일 

DB설계 1차를 마쳤다. 

node.js로 mysql을 조작하여 글 편집하는 부분을 연습했다.  

node.js 활용하는 강의를 듣기를 시작했다. 

생각거리 

node.js는 라우팅이 좀 어려운 것 같다. 그래도 직관적인 문법이라 좋다.

날씨가 참 좋다. 기분도 좋다:)

MySQL DB 설계를 할 때 명명 규칙을 참고할 일이 생겼습니다.
잘 정리된 포스팅을 발견해서 기록합니다.
출처 : https://purumae.tistory.com/200

공통

1. 소문자를 사용한다.
2. 단어를 임의로 축약하지 않는다. register_date (O) / reg_date (X)
3. 가능하면 약어의 사용을 피한다. 약어를 사용해야 하는 경우, 약어 역시 소문자를 사용한다.
4. 동사는 능동태를 사용한다. register_date (O) / registered_date (X)

TABLE

1. 단수형을 사용한다.
2. 이름을 구성하는 각각의 단어를 underscore 로 연결하는 snake case 를 사용한다.
3. 교차 테이블 (many-to-many) 의 이름에 사용할 수 있는 직관적인 단어가 있다면 해당 단어를 사용한다.
4. 적절한 단어가 없다면 relationship을 맺고 있는 각 테이블의 이름을 "and" 또는 "has" 로 연결한다.

예시

article, movie : 단수형
VIP_member : 약어는 대문자 & 단어의 연결에 underbar를 사용
article_and_movie : 교차 테이블을 "and" 로 연결

COLUMN

1. auto increment 속성의 PK를 대리키로 사용하는 경우, "테이블 이름"_id 의 규칙으로 명명한다.
2. 이름을 구성하는 각각의 단어를 underscore 로 연결하는 snake case 를 사용한다.
3. foreign key 컬럼은 부모 테이블의 primary key 컬럼 이름을 그대로 사용한다.
4. self 참조인 경우, primary key 컬럼 이름 앞에 적절한 접두어를 사용한다.
5. 같은 primary key 컬럼을 자식 테이블에서 2번 이상 참조하는 경우, primary key 컬럼 이름 앞에 적절한 접두어를 사용한다.
6. boolean 유형의 컬럼이면 "_flag" 접미어를 사용한다.
7. date, datetime 유형의 컬럼이면 "_date" 접미어를 사용한다.

예시

article_id, movie_id : "테이블 이름" + "_id"
complete_flag : boolean 유형의 컬럼
issue_date : 날짜 유형의 컬럼

INDEX

1. 이름을 구성하는 각각의 단어를 hyphen 으로 연결하는 snake case 를 사용한다.

접두어
unique index : uix
spatial index : six

index : nix

"접두어"-"테이블 이름"-"컬럼 이름"-"컬럼 이름"

예시

uix-account-login_email

FOREIGN KEY

1. 이름을 구성하는 각각의 단어를 hyphen 으로 연결하는 snake case 를 사용한다.

"fk"-"부모 테이블 이름"-"자식 테이블 이름"

같은 부모-자식 테이블에 2개 이상의 foreign key가 있는 경우, numbering합니다.

예시

fk-movie-article : article 테이블이 movie 테이블을 참조
fk-admin-notice-1 / fk-admin-notice-2 : notice 테이블이 admin 테이블을 2회 이상 참조하여 numbering

VIEW

1. 접두어 "v"를 사용한다.
2. 기타 규칙은 TABLE과 동일

예시

v_privilege

stored procedure

FUNCTION

1. 접두어 "usf"를 사용한다.
2. 이름을 구성하는 각각의 단어를 underscore 로 연결하는 snake case 를 사용한다.

예시

usf_random_key

TRIGGER

1. 이름을 구성하는 각각의 단어를 underscore 로 연결하는 snake case 를 사용한다.
2. 접두어
   tra : AFTER 트리거
   trb : BEFORE 트리거

"접두어""테이블 이름""트리거 이벤트"

예시

tga_movie_ins : AFTER INSERT 트리거
tga_movie_upd : AFTER UPDATE 트리거
tgb_movie_del : BEFORE DELETE 트리거

도움이 되셨다면 하트🤍꾸욱 부탁드립니다.