컴공 일기232
게시글 주소: https://orbi.kr/00062255284
저번에 올렸었던 AVL 트리의 기본 이론 입니다.
일반 이진 트리의 경우 1-9를 삽입한다면 오른쪽으로 확 쏠려버리는 구조가 나옵니다. 이런 경우, 이진 탐색이 선형 탐색과 별반 다를 바가 없는 기이한 현상이 일어나고, 이진 탐색 트리의 장점이라 볼 수 있는 '탐색 속도'가 무의미하게 되지요. 따라서, Node가 삽입 혹은 삭제되는 과정에서 트리의 균형을 잡아주는 알고리즘이 필요한데, 그것이 AVL트리의 경우 RR,LL,RL,LR 회전입니다. 말하자면, 전체 구조 속에서 균형이 무너지기 시작할 때, 회전을 해서 다시 균형을 잡아주는 것이지요.
일반 이진 탐색 트리의 경우, 9를 탐색한다면 9번 연산을 진행해야 하지만, 균형이 잡힌 AVL 트리에서는, 4번의 연산만으로 탐색할 수 있지요. Node 수가 적을 땐 9번이든 4번이든 큰 차이가 없다고 할 수 있겠지만, 데이터가 증가하면 증가할수록, 이 차이는 그에 비례해서 커집니다.
선형 탐색의 경우 시간복잡도는 O(N)이고, 균형 이진 트리의 경우 시간복잡도는 O(logN)입니다.


0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
진짜 아직 모른다 2 1
5:4 ㅋㅋㅋㅋ 역대급 꿀잼경기
-
5대4 ㄷㄷ 1 0
1~3분남음
-
사카 헤트트릭 5대3 3 1
pk로 넣었어요 5대3 맞췄으면 300배입니다
-
얼버기 4 3
오늘은 큐어 에클레르 정체가 공개되는날
-
음바페 버닝 미쳤 3 1
4대0이 순식간에 4대3이 되네
-
아 삼사위전 진짜 재밌네 4 2
자꾸 골이터지네 ㅋㅋㅋㅋㅋ 전개 시원..
-
4대3 배당 85배 1 0
4대4무승부는 180배 양팀득점합 7+는 18배
-
음바페골 4대3 0 1
ㄷㄷ
-
국어 실모 작년것도 괜찮나요? 2 0
작년에 사놓고 안풀어서 그런데 연계된게 낫나요?
-
양팀 감독 수비 포기하긴 한듯 0 1
이게 축구지
-
이건 데샹이랑 음바페가 1 0
라커룸에서 빠따친거 말고는 설명이 안돼
-
프랑스 할 수 있으면서 3 2
살살 뛴거였네 ㅋㅋ
-
음바페 골ㄹㄹㄹㄹㄹㄹ 2 1
음바페원툴똥팀수준ㅋㅋㅋ
-
5대0은 350배 4대1, 4대2는 55배 5대1, 5대2는 190배
-
573년전 군자의 복수
-
ㅇㅂㄱ 2 0
오늘은 수탐 기출을 해볼거에요
-
오늘 2027 LEET 시험일이니 최상위권은 참조 0 4
법학적성시험(LEET) 공식 홈페이지:...
-
잉글랜드가 막강한건지 프랑스가 더럽게 못하는건지 3/4위전인 것치고는 경기 밸런스가...
-
축구 개꿀잼이농농 1 1
3,4위전이 역시 클럽전같애서 재밌음
-
프랑스는 3분만에 골먹었냐 6 1
진행중인 34위전 1대0 잉글리드중 잠깨서 스코어본거라 어떤판인진 모르겠움
-
목요일의 내가 4 3
금요일의 내가 토요일의 내가 오늘의 나에게 모든 임무를 떠넘겼다 남은 시간은...
-
근데 러닝하는 사람들 2 0
그 등줄기만 가리는 괴상망측한 옷을 입는 사람들이 있는데 저거 편하나? 오히려 신경쓰일거 같은데
-
얼버기 했습니다. 9 4
월드컵 3,4위 결정전 보고 하루를 시작해보아요
-
국어에서 변호사 탈락 수학에서 메디컬 탈락 문과에서 삼닉 탈락 그럼 남은게 공무원...
-
밤 샜네 4 2
이런
-
일어남 6 1
머여
-
모든 업보가 끝났다고 믿어봐요! 10 2
그렇게 첫 하루를 시작하는 것이에요! 좋은 아침이에요!
-
ㅜㅜ 3 1
ㅜ
-
얼버기 4 1
-
잠이안오네 2 0
아.. 힘들다..
-
범작가 싫었는데 잘됐다 0 20
지금은 내려간 영상인가 제목이 바꼈나 수능도서 팔이면서 자기를 베스트셀러 작가가라고...
-
잘까말까 1 1
쿼티님 대답해줘요
-
거짓말 안하고 수완 뒤에 실모 푸는데 18부터 21까지를 다 실수해서 처틀림;;...
-
너넨 손가락 함부로 놀리지마라 2 1
약점잡히면 인생힘들다
-
언제자지 2 1
고민중
-
저건뭐 60훈 시즌2임? 0 3
BJ 0훈
-
바닥에서 자기로했음 3 2
습박
-
월드컵 3등은? 0 0
난 프랑스
-
250622 250922 251122 230914 지금 얘네가 ㅈㄴ 힘들어보임...
-
BJ츄 - 본능적으로 0 0
-
어쩔수없지뭐 7 2
어쩔수없지뭐
-
Bj츄 - 당신을 위하여 0 0
-
쿠폰있어서 햄버거 두개에 해쉬브라운 하나 음료 두개 만원 언더로 먹을수있는데 더 먹을거 ㅊㅊ점
-
Bj츄 - 예뻤어 0 0
-
현역때 틀린거 다시 풀고 맞추니까 감회가 새롭네 0 2
아직도 집에 시험지 있어서 함봤는데 틀린거보고 참 대단하다 싶더라 ㅋㅋ 현역때...
-
Bj츄 - 처음처럼 0 0
-
아 좃됏다 4 3
침대에 누워서 물마시다가 침대에 쏟음 어디서자지
-
아오 휴대폰 맛 갔나 0 1
발열이 무슨 흑체복사야
-
2011년 그시절 극킬러문항 4 1
이거보면 표본상승 확 체감됨
-
개원은 하고싶은데 땅이 비싸서 오는건가

잘 읽고 갑니다
감사합니다 :-)