컴공 일기230
게시글 주소: https://dev.orbi.kr/00062187328
균형 이진 트리 중 하나인 AVL 트리를 구현하고 있습니다. 자료구조를 구현할 땐, 먼저 SKETCH를 해놓고 전체적인 구조를 이해하는 것이 중요한 것 같아요. 뇌가 64비트 인텔 CPU와 동기화가 되지 않은 이상이요...
트리(Tree)라는 자료구조의 장점 중 하나는, 탐색에서 굉장히 유용하다는 거에요. 10억개의 데이터가 들어와도, 높이가 30을 넘지 않기 때문에 몇 번의 탐색으로도 해당 데이터를 빠르게 찾아낼 수 있죠. 하지만, 이건 이상적인 얘기입니다. 트리 자체가 왼쪽과 오른쪽이 고르게 분포된 상태라면, 그 장점을 발휘할 수 있지만, 삽입 또는 삭제가 되는 과정에서 트리의 균형이 무너지게 되면, 자칫 잘못하면 10억 개의 데이터를 찾을 때 10억번을 검색해야 할 수도 있기 때문입니다.
조금 이상하죠. 장점이 탐색인데, 단점이 탐색이라니... 따라서, 트리를 구현할 때 "Balancing"이라고 하는 이슈가 중요하게 됩니다. 말하자면, 삽입과 삭제를 할 때, 트리가 왼쪽 혹은 오른쪽으로 쏠리지 않도록 재조정을 해주는 것이지요. 이렇게 된다면, 탐색의 성능을 굉장히 잘 발휘할 수 있으니까요.
AVL트리는 기존의 트리에 "Balancing" 기능을 추가해주어서 트리의 균형을 잘 잡아주는 구조라 할 수 있겠습니다. 따라서, 일반 이진트리나 이진 탐색 트리에 비해서 훨씬 더 안정적이라고 볼 수 있고, 더 고급(?) 자료구조라고 볼 수 있겠네요.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
초 가구야 공주 보셈요 4 0
진짜 꿀잼 고트 애니
-
그냥 술자리 싫음 청년 7 3
그 뒤지게 시끄러운 곳에서 말도 제대로 안들리는데 처음 보는 사람하고 어색하게...
-
근데 더프 수학선택 범위 좁은건 3모대비라하면 이해되는데 4 3
투과목 << 얘넨 3모에도 안나오는데 전범위로 하면 될걸 왜 꾸득꾸득 초반부만 넣는거임
-
알림창 개폭력적이네 9 6
-
개강 3주차...아직 후배 얼굴도 본적없음
-
시발 뭘 할 수가 없네 9 1
친구 없어도 그래도 고대 왔으니 합응까진 갈까 했는데 허리 이 시발롬 좆도 안낫고 더 아파짐 아오
-
음주체스숙취수학 1 0
왜효고ㅓ좋냐
-
옾붕이들은 영어듣기 잘하나요 9 0
듣기 살면서 한번도 안툴린 사람 많으려나영듣칼럼 쓰려 하는데 수요 있으려나...
-
와 시벌 이게 얼마만인지 모르겟다 한달만에 같이 밥먹는거같은데 두달인가?
-
본인은 메인 두 번 가봄 3 1
한 번은 평가원 피셜 확정 등급컷 (영어) 네이버 블로그 감성 글로 가봤고 한 번은...
-
역시 약대생 3 1
난 시간 꽉꽉 채워 풀어서 88점인데
-
3덮 미적 풀어봤다 15 2
이렇다 전 글에서 맞춘사람 5000덕 보내줄게 생각보다 잘나왔네 22 30은 걍...
-
3모 ㅈ된거같으면 개추. 3 3
ㄱㄱ
-
어스름 내린 언덕 너머로 푸른 융단이 조용히 깔리면 4 1
수줍게 눈을 뜨는 작은 별들 사이로 깊고 아득한 밤이 피어납니다.
-
JMS 유튜버 댓글 근황 1 2
빨리 JMS에서 탈출하길 빕니다
-
대학간 오르비언 특 8 3
2월 말 ~ 3월 첫째주까진 재밌다~~ 하면서 안들어오더니 3월 둘째주부턴 외롭다...
-
나 분명 학기중엔 0 0
새르비를 안할줄알았는데ㅔㅔㅔ 옯창이 맞는것인가?
-
체언 수식 부사
-
새르비ing 0 0
손 ㄱㄱ
-
지방대 궁금한점 질문받음 9 0
옯인원들에겐 관심없을수있지만 25수능때 66584로 지방대 빵노리고 붙었음...
-
독서 제대로 이해한 지문이 없었음... 심지어 마킹 안 하고 1분 초과됨 3모 5일...
-
아빠 잔다 2 1
잔디wwwwww
-
재작년에 수능봐서 백분위 97 받고 대학 다니다가 올해 다시 수능 준비 중인데 생명...
-
3연강으로맞고 0 0
8:30~17:30당하니까죽겠다
-
여기다전화해줘 0 1
119 너 때문에 내 심장이 멎었어
-
행복해요 8 0
-
현역이때 생윤 말아먹어서 재수때 정법하서 3나왔어요 다시 생윤으로 돌아갓?...
-
글리젠 진짜 없네 2 0
내가아는 오르비가맞냐
-
ㅇㅇ
-
그것이 문제로다
-
오르비 굿나잇 ~ 7 1
피곤해뒤지겟다 오답은 내일 할게
-
얘네가 진선여고 숙명여고에 있었으면 내신 몇 뜰까요? 7 0
옛동네인 영등포에 사는 초등동창인 여사친들인데 한 아이는 영등포 공학 좆반고에서...
-
N제 먼저?? 0 0
수1 스블 다 들었고 수2,확통 실점개념 반정도 들었는데 수2,확통까지 실전개념 다...
-
08) 오늘의 공부인증!! 10 1
그냥 너무 심란함 모든것에 대해서 ㅠㅠ
-
ㄹㅇㅋㅋ
-
에효 못생긴 옵붕이들 ㅉ 0 1
심지어 공부도 못하는 말이야
-
새르비 최강의 남자 3 1
쌍윤왜어려움
-
3섶 화1 45 4 0
물2는...예...
-
5시긴40분뒤에일어니야더ㅣㅁ 2 2
습박
-
오늘 저녁 ㅁㅌㅊ? 4 1
돼지 되는 중 ...ing
-
새르비의라이징스타 0 0
설국문쟁취
-
한국 kf21 보라메=>뭔가 문제 있어보이고 그렇게 안 쌜거 같음 미국 f22 =>...
-
김기현쌤 아이디어 0 0
작수 4이고 이번에 확통으로 바꿨습니더 확통은 시발점 듣고있는데 수1 수2를 어느...
-
조해공 과잠 봤을 때였음 조선해양공학과 <- 개틀딱같음 Naval...
-
이거 개쩌는 공부법인듯 2 1
1주마다 문제집 제끼고 오르비에 인증하기 앉아있는 시간은 같지만 공부량 ㅈㄴ 늘어난게 체감이 됨
-
윤사 코드원 샀음 1 2
윤사 개박살 났으니까 그래도 김종익 플러스 해서 코드원까지 하려고..
-
전화하고싶다 3 0
누구든좋으니까
-
작년에 2 0
2월부터 수능까지 새르비에 항상 있었던 사람이 있음
-
소아과 의사 누구였지 6 0
오르비언 ㅇㅅㅇ
-
한 달 뒤 새르비 상황 1 3
제목:진짜 다 뒤1졌냐? 2분전 조회수 8 작성자 수능 ㅈ된 설의적표현 내용:
레드블랙은 아는데 avl 은 처음 들어봤네요.. 찾아보니 꽤 비슷하던데 avl 구현해보셨으면 다음엔 레드블랙 트리 한번 해보시죠 ㅎㅎ
https://ko.m.wikipedia.org/wiki/레드-블랙_트리
레드 블랙 트리, 2-3트리, 2-3-4트리.. avl 트리, B-트리 등등 균형 이진 트리 계열은 비슷한 측면들이 많은 것 같습니다 ㅎㅎ 개인적으로 학부 자료구조 수업에서 균형 이진 트리까지 배우지 않는 경우가 있어서 아쉬웠어요. 트리의 균형성을 어떻게 맞출 수 있는가에 대한 고민은 참 중요한 것 같은데 말입니다.
학부에서 이걸 안배우는 경우도 있나요? 저희 학교는 아직 수업을 안들어봐서 모르겠지만 배웠으면 좋겠군요. 트리에서 균형이 굉장히 중요한데 말이죠..
아무래도, 전체 학기가 14-15주차로 구성되어있고 그 안에서 링크드리스트에서 그래프까지 진도를 빼야하다 보니, 자료구조 수업 자체가 pre-알고리즘 수업으로 변질되는 경우가 더러 있는 것 같더라구요.
실제로, 제가 이수했던 수업에서는 트리 쪽 단원에서 균형 이진 트리라는 구조가 있다는 것을 간단하게 소개만 하고, 다른 자료구조나 알고리즘으로 넘어가더라구요. 시험 문제 같은 경우도, 자료구조 구현에 대한 측면보다는 알고리즘 관련 손코딩 문제가 많이 나왔던 것 같고...
교수님마다, 또 서적마다 차이가 있겠습니다만, 자료구조 수업에서 알고리즘 얘기는 가급적 줄이는 것이 맞다고는 생각하고 있습니다. 그럴 거면, 굳이 자료구조와 알고리즘 과목을 분리할 이유가 없으니까요. 또, 모든 알고리즘은 근본적으로 자료구조에 의존적이기 때문에, 자료구조 수업에서는 특정 자료구조에 대한 상세한 배경, 원리, "다양한" 구현 방식, 예시와 같은 것들을 많이 다루는게 맞다고 봅니다.
확실히 대학 수업만으론 컴퓨터 과학의 방대한 분량을 자세히 다 다루긴 어렵겠네요… 이거 제 생각엔 아무래도 초등학교때부터 자료구조를 배우도록 해야 겠군요(?) 초등학교 숙제로 ps 하나씩 풀어오게 하고 ㅎㅎ
아마 그런 날이 오는 시기도 얼마 남지 않았겠죠. 프로그래밍 과목이 국영수 처럼 기본 영역으로 편입될 여지는 얼마든지 있다고 봅니다 ㅎㅎ