컴공 일기230
게시글 주소: https://orbi.kr/00062187328
균형 이진 트리 중 하나인 AVL 트리를 구현하고 있습니다. 자료구조를 구현할 땐, 먼저 SKETCH를 해놓고 전체적인 구조를 이해하는 것이 중요한 것 같아요. 뇌가 64비트 인텔 CPU와 동기화가 되지 않은 이상이요...
트리(Tree)라는 자료구조의 장점 중 하나는, 탐색에서 굉장히 유용하다는 거에요. 10억개의 데이터가 들어와도, 높이가 30을 넘지 않기 때문에 몇 번의 탐색으로도 해당 데이터를 빠르게 찾아낼 수 있죠. 하지만, 이건 이상적인 얘기입니다. 트리 자체가 왼쪽과 오른쪽이 고르게 분포된 상태라면, 그 장점을 발휘할 수 있지만, 삽입 또는 삭제가 되는 과정에서 트리의 균형이 무너지게 되면, 자칫 잘못하면 10억 개의 데이터를 찾을 때 10억번을 검색해야 할 수도 있기 때문입니다.
조금 이상하죠. 장점이 탐색인데, 단점이 탐색이라니... 따라서, 트리를 구현할 때 "Balancing"이라고 하는 이슈가 중요하게 됩니다. 말하자면, 삽입과 삭제를 할 때, 트리가 왼쪽 혹은 오른쪽으로 쏠리지 않도록 재조정을 해주는 것이지요. 이렇게 된다면, 탐색의 성능을 굉장히 잘 발휘할 수 있으니까요.
AVL트리는 기존의 트리에 "Balancing" 기능을 추가해주어서 트리의 균형을 잘 잡아주는 구조라 할 수 있겠습니다. 따라서, 일반 이진트리나 이진 탐색 트리에 비해서 훨씬 더 안정적이라고 볼 수 있고, 더 고급(?) 자료구조라고 볼 수 있겠네요.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
이기상 단과 0 0
이미 대성 듣고 있어서 세지 하나 들으려고 메가 끊기엔 좀 그런데 단과로 이개다만...
-
ㅇㅂㄱ 0 0
사실 안잠
-
얼버기 2 1
-
기차지나간당 0 0
부지런행
-
오랜만이에요 0 0
수능 공부하고 마크하느라 바빠서 못왔어요
-
05:00~09:00 편의점 16:00~27:00 포차 생각했던 플랜대로 9시...
-
Copj 들어갔습니다 2 0
네
-
우하하
-
아 진짜 좆됐다 2 0
지금 자면 3시간은 자나 그냥 오전강의 재낄까..
-
-
빨리특이점이와서날구해줘 0 0
으..
-
술 마셨는데 잠을 못잤어... 1 0
이대로 해장국 먹어도 되려나
-
의사가되서 0 0
나같은 사람을 도와주는거임 아무래도 ...조은듯ㅋ 근데별로 .......
-
아니근데나고민이이씀 2 0
문제보면 그냥 슥슥 푸는데 시간이 오래 지나이씀...ㅠㅠㅠㅠ 아무래도 그거땜에 점수가낮은거심!!
-
그니까여자가되면 4 0
꼬실애는 이씀 ㅎㅎ
-
여자만날곳이없음 2 0
그래서내가여자가되기로함 으ㅡㅎ흐
-
작년은 아닌데 0 1
재작년에 썻던 알레르기 안약을 잊지못함 으흐흐 그때 효과 완전 조아씀 쓰자마자 바로...
-
여친사귀고시픈데 6 0
어떠캐해야함 ㅜㅜ
-
옆나라에선 난리인가봄
-
치유물의 정석 3 0
내인생
-
왜 내 몸은 이러지 9 0
ㅠㅠㅠㅠㅠㅠㅠ 건강 개처망함 ㅠㅠㅠㅠㅠ 으으.... 삶의질이떨어짐
-
고딩때는 ENTP 였는데 지금은 INTP로 바뀜 5 0
근데 INTP가 통계적으로 MBTI 중 학점 꼴찌더라
-
일어나고 싶지 않다 6 1
밀쇼는 그냥 잠들기로 했어요
-
난 일단 2 1
언매가 제일 문제는 아니고 탐구가 더 문제지만 언매 너무 기분나쁨 ㅡㅡ 얘땜에 내가...
-
가면 갈수록 2 0
앞으로 뭐 공부해야 먹고살 수 있을지 고민되기 시작하네.. ㄹㅇ 어캄
-
오 뭐야 2 0
약국에서도 가능하구나 내일약국가야징
-
물2가 문젠대 2 1
언매도 문젠대
-
내일 병원가서 0 0
약받아와야하나... 으아아ㅏ
-
지2런 진짜할까 7 1
미친짓일까
-
머리가 너무아파서 0 0
못해씀 ㅠㅜ 자야하느데 .... 흐잉ㅇ
-
4시라니 2 0
슈퍼얼버기를 슬슬 준비해야겟군
-
화2 0 1
개념 핥아보긴 했었는데 타임어택에 극도로 약하고 계산실수가 잦아서 가져갈순 없었지
-
?????? 4 0
-
아무래도 2 0
물2화2엔 내가 깔리고 있음 ㅜ.ㅜ
-
근데 열두시만 지나면 다시 정신이 돌아옴 그러고 4시까지 쳐 놈
-
그냥 통합수능 해줘라 0 1
당장 합쳐라 당장 문과도 투과목을 하도록 해라
-
4시에는진짜자야지 1 0
정상적인 생활이 불가능해
-
네
-
서울대가고싶구나 1 2
못가면 삶의 의미를 잃을거야
-
수특 기하 최종후기 0 0
일단 문제퀄 개드러움. 이차곡선, 공간도형 계산 졸라 많고 근데 벡터는 쉬움. 근데...
-
흐에엥 6 0
사랑받지못하는나는살이유가업성 흐이엥ㅠㅜㅜㅠㅠㅠㅠㅠㅠㅠㅠ
-
외모가출중한사람에게 혼나고싶음 2 0
화내는거가막보고싶음
-
키보다중요한건 5 1
얼굴 얼굴보다중요한거 없음
-
계산실수를 두개씩 함 8 1
미쳣어
-
키작은 사람들 여장해보셈 4 1
궁금해
-
미팅나가볼까 2 2
가서 롤 좋아하세요? 저는 아지르 잘해요 ㅎㅎ 하고 애프터신청 받는거임
-
이거완전 닥밍커플
-
교수님께 죄송하네 1 1
나란새끼는 전공공부 안하고 수능쳐서 튈생각만 하는중인데
-
먐뮴이 5 0
먐뮴이 뮴먐이
-
으헤헤 6 1
흐흐ㅡ흫
레드블랙은 아는데 avl 은 처음 들어봤네요.. 찾아보니 꽤 비슷하던데 avl 구현해보셨으면 다음엔 레드블랙 트리 한번 해보시죠 ㅎㅎ
https://ko.m.wikipedia.org/wiki/레드-블랙_트리
레드 블랙 트리, 2-3트리, 2-3-4트리.. avl 트리, B-트리 등등 균형 이진 트리 계열은 비슷한 측면들이 많은 것 같습니다 ㅎㅎ 개인적으로 학부 자료구조 수업에서 균형 이진 트리까지 배우지 않는 경우가 있어서 아쉬웠어요. 트리의 균형성을 어떻게 맞출 수 있는가에 대한 고민은 참 중요한 것 같은데 말입니다.
학부에서 이걸 안배우는 경우도 있나요? 저희 학교는 아직 수업을 안들어봐서 모르겠지만 배웠으면 좋겠군요. 트리에서 균형이 굉장히 중요한데 말이죠..
아무래도, 전체 학기가 14-15주차로 구성되어있고 그 안에서 링크드리스트에서 그래프까지 진도를 빼야하다 보니, 자료구조 수업 자체가 pre-알고리즘 수업으로 변질되는 경우가 더러 있는 것 같더라구요.
실제로, 제가 이수했던 수업에서는 트리 쪽 단원에서 균형 이진 트리라는 구조가 있다는 것을 간단하게 소개만 하고, 다른 자료구조나 알고리즘으로 넘어가더라구요. 시험 문제 같은 경우도, 자료구조 구현에 대한 측면보다는 알고리즘 관련 손코딩 문제가 많이 나왔던 것 같고...
교수님마다, 또 서적마다 차이가 있겠습니다만, 자료구조 수업에서 알고리즘 얘기는 가급적 줄이는 것이 맞다고는 생각하고 있습니다. 그럴 거면, 굳이 자료구조와 알고리즘 과목을 분리할 이유가 없으니까요. 또, 모든 알고리즘은 근본적으로 자료구조에 의존적이기 때문에, 자료구조 수업에서는 특정 자료구조에 대한 상세한 배경, 원리, "다양한" 구현 방식, 예시와 같은 것들을 많이 다루는게 맞다고 봅니다.
확실히 대학 수업만으론 컴퓨터 과학의 방대한 분량을 자세히 다 다루긴 어렵겠네요… 이거 제 생각엔 아무래도 초등학교때부터 자료구조를 배우도록 해야 겠군요(?) 초등학교 숙제로 ps 하나씩 풀어오게 하고 ㅎㅎ
아마 그런 날이 오는 시기도 얼마 남지 않았겠죠. 프로그래밍 과목이 국영수 처럼 기본 영역으로 편입될 여지는 얼마든지 있다고 봅니다 ㅎㅎ