컴공 일기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를 선물하세요.
-
프린트 카페에 경찰이랑 일반인이랑 같이 뭐 하고있던데 0 0
유빈쓰다 걸렸나봄 정확힌 모르겠지만 주변이 대학생 많고 학원 많아서 수능 준비하시는 분 같은데
-
걍 다들 디폴트가 잘살아가지고 그런게 먹힐 환경이 아니라그런가
-
과거의 영광은 과거의 영광으로 묻어두어야할까..
-
지금보면 2411공통 어케 다맞았지 싶음
-
소신발언)내가 '무조건' 맞다라고 하는쪽은 사기임 7 4
적어도 국어는 그럼
-
딱히 누구라곤 안햇삼
-
7덮 등급컷 예측 1 0
화작 90 독서-1,문학-1,화작-2 극문학 뭐냐;; 미적 92 (21,30틀)...
-
국어도 기출 여러번 푸시나요 1 1
-
7덮 기하 손풀이 (공통) 0 0
기하는 여기...
-
제 국어 커하는 100임 2 0
아직 아니지만 수능때 무조건 띄울거라 100(예정)임
-
2306 풀어봣는데 0 0
화작 확통90 84 / 사문생윤 47 48나왔는데 14 22는 걍 날렸고 13...
-
생윤 41 윤사 44 영어 난이도는 어땠나요?
-
어그로 죄송한데 국어 커리나 인강 안들어보고 2등급은 그래도 안정적으로 나왔어서...
-
군의관 공보의 복무기간 단축을 기다리는 사람에게 2 2
감나무 밑에서 입벌리고 계시지 마십시오 ㅋㅋㅋ
-
혼자 안정적으로 살다 적당히 죽는게 목표인데 당장 1년 2년 먼저 돈벌겠다고...
-
-
9모 전에 딱 한번 2년만에 만나는 친구랑 놀기로 했는데 그 친구가 술꾼이라 술을...
-
두영상 다 보고왔는데 영상만으로는 범작가님측 주장이나 증거? 등이 더 합리적이라...
-
뉴런 vs 개때잡 0 0
보통 뭐를 많이 듣나요? 취향차이인가
-
차라리 군의관 공보의 가고말지 육체적인 뭔가를 매우 싫어하기도 하거니와(훈련, 작업...
-
현역 고3이고, 아마 7월초부터 공부에 대한 의욕이 사라지고, 자존감이 낮아진 것...
-
강k 수학 응시반 0 0
대구가 젤 높다는게 진짜임? 실모 약대 최적 교대 등급컷 더프 세지 7모 상케이 덮...
-
커리큘럼 피드백 좀 1 0
현우진+정승제 쌤 섞어서 들을건데 개념의 신- 개때잡-수분감-드릴-킬캠 이렇게 들으려는데 어떰?
-
세지 노베로 3나와서 생윤세지 할까 하는데
-
둘다 인공심장이라는거임
-
서프랑~ 0 0
6모랑 등급차가ㅜ얼마나 날까요… 수학이여!!!!!!!!! 6모 2등급나왓는데….....
-
누구 얘기는 아니긴 한데 9 16
매년 매달 증명해야 하는 것도 아니고 몇년간의 응시 결과 중 최고점만 골라서...
-
이원준 리트300 끝냈는데 2 0
이제 뭐해야할까요 기출을 다시하기엔 기출은 3회독해서 내용만 기억나는게 아니라...
-
방금 보고 온 7월 더프 후기 12 0
잇올 학교프로젝트가 있어서 7덮을 뒤늦게 봤습니다 언매 87 기하 84 영어 87...
-
올해 의대 합격생 예정자들은 들어라 22 5
씨발 합격하자마자 바로 군대가라 진짜 이건 진심이다 중간에 군대가면 동기들이랑 유대...
-
7덮 등급예측 0 0
화작 확통 한지 경제 81 85 29ㅅㅂ 47 각각 몇나옴?
-
초 코 퍼 지
-
지금까지 해온게 0 0
다 거짓인것같은 느낌 기분이 안좋다
-
이거맞나
-
저녁 뭐뭑을건지 남겨봐. 17 1
괜찮은 거 보이면 그거 먹게
-
내 생각 적어봄. (꽤 장문) 5 3
1. 계약기간이 완전히 끝나지 않았는데 이적을 한 것부터 현명하지 못했음 1권은...
-
대충 배포시기는 8월로 보시면 좋고 , 8월 초중반쯤 생각중입니다. 평가원 형식 /...
-
반데르발스 상태방정식 지문 0 0
안녕하세요. 혹시 13수능 반데르발스 지문 보기문제 단순히 실제기체 A,B의 부피...
-
독학서를 공부하기 위해서 독해력이 필요함 뭔가 철을 녹이기 위한 용광로를 위한 철이...
-
09 국어 강사 추천 0 0
고2 모고 기준 1(낮은)이고 현재 수국김 수강 완료했습니다. 이후에 어떤 인강을...
-
지바 2회 푼사람 4 0
풀고올테니 후기를 남겨주도록.
-
[로크의 자연권 양도 범위 관련 내용 정리] [도움 받은 책] 1. 기본: 로크...
-
지금 강민철 합류해도 되나요 0 0
재수생이고 작6 -> 작9 -> 작수 -> 올6 1 2 3 2 입니다 작년엔 언매만...
-
무슈슈 4 0
-
공비가 음수니까 이런걸 물어봤겠지?
-
범작가 영상보고 남은 생각 8 12
그냥 핫 하길래 영상보고 궁금한점 써봄 영상 시점 언급 내용 말고는 제 3자가...
-
저녁뭐뭑지 4 0
마제소바 냉으동 냉모밀
-
영화 호프 4 2
호프호프
-
확통 벽느껴지는데 2 0
미적 29보다 어려움
-
두잇 두잇 츄 9 2
잘 읽고 갑니다
감사합니다 :-)