컴공 일기230
게시글 주소: https://orbi.kr/00062187328
균형 이진 트리 중 하나인 AVL 트리를 구현하고 있습니다. 자료구조를 구현할 땐, 먼저 SKETCH를 해놓고 전체적인 구조를 이해하는 것이 중요한 것 같아요. 뇌가 64비트 인텔 CPU와 동기화가 되지 않은 이상이요...
트리(Tree)라는 자료구조의 장점 중 하나는, 탐색에서 굉장히 유용하다는 거에요. 10억개의 데이터가 들어와도, 높이가 30을 넘지 않기 때문에 몇 번의 탐색으로도 해당 데이터를 빠르게 찾아낼 수 있죠. 하지만, 이건 이상적인 얘기입니다. 트리 자체가 왼쪽과 오른쪽이 고르게 분포된 상태라면, 그 장점을 발휘할 수 있지만, 삽입 또는 삭제가 되는 과정에서 트리의 균형이 무너지게 되면, 자칫 잘못하면 10억 개의 데이터를 찾을 때 10억번을 검색해야 할 수도 있기 때문입니다.
조금 이상하죠. 장점이 탐색인데, 단점이 탐색이라니... 따라서, 트리를 구현할 때 "Balancing"이라고 하는 이슈가 중요하게 됩니다. 말하자면, 삽입과 삭제를 할 때, 트리가 왼쪽 혹은 오른쪽으로 쏠리지 않도록 재조정을 해주는 것이지요. 이렇게 된다면, 탐색의 성능을 굉장히 잘 발휘할 수 있으니까요.
AVL트리는 기존의 트리에 "Balancing" 기능을 추가해주어서 트리의 균형을 잘 잡아주는 구조라 할 수 있겠습니다. 따라서, 일반 이진트리나 이진 탐색 트리에 비해서 훨씬 더 안정적이라고 볼 수 있고, 더 고급(?) 자료구조라고 볼 수 있겠네요.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
안녕하세요 2 0
배고파요
-
261130에서 10 나오는게 1 1
어떤 원리인지 방금 처음앎 ㄷㄷ 근데 ㄹㅇ 접선 - 접선 이렇게 생각했을수도 있긴...
-
7월 반수 어케 생각함 2 0
인하대 높공이고 작수 기준 언 미 영 세지 지1 2 2 3 3 2 3 학점...
-
방금기절할뻥했는데 4 1
알람땜에깸 이제 진짜자야징 흐헤헤
-
연두색! 아니 딱봐도 노란색.. 아니 연두.. 노란.. 초록색 계열이지! 그니까...
-
깨어났다 1 0
알람을 끄고 나는 다시 잠에 들것이다
-
언언언언언언언언언언언언언언 2 0
수온은 적당한가
-
바♡누 2 0
울♡누 왕♡누 쫄♡누 초♡누
-
이거보셈 3 0
워니 귀여움임! ㅋ
-
아무래도 4 0
잠에 자야겠어 내가 사는게 먼저지
-
야채지누 4 0
너 11수 하게?
-
슬슬 자야하는데 1 0
피자 시킨 거는 먹고 자야지
-
모르겠어 6 0
ㅠㅠㅠㅠㅠ
-
하이 하욜럽 하이 하욜럽 1 0
뚜뚜루 뚜뚜뚜뚜뚜 너라는 숲속에서난 갈곳을 잃은럽홀릭
-
ㅇㅂㄱ 2 0
다들 오늘도 화이팅
-
[속보]노무현 전 대통령 서거 2 1
노무현 전 대통령이 23일 오전 8시50분경 서거한 것으로 경찰이 공식 확인했다....
-
ㅇㅂㄱ 3 0
오늘도파이팅
-
좋은아침 4 1
-
ㅎㅇㅎㅇ 4 0
ㅎㅇ
-
거던 15층클 1 0
풀제약하려고 했는데 쫄아서 15층 정신력 제약 2개는 빼버림 봉이까지 먹었는데...
-
한 편만 보려고 했는데 6 1
왜 벌써 4시지
-
4/30 5/1 3 0
늦잠자서 루틴 조짐
-
정신병농도 진하다 1 1
화가 많이 나고 답답허다
-
자기전에 물많이먹으면 2 1
오줌마려워서 일찍깰수있음
-
목금은 아무 일도 안 하는 날이므로.. 아침에 일어나서 쭉 공부 달려줬습니다....
-
아 뭐임 10 0
시간 에반데 ㅜㅜㅜㅜㅜㅜㅜㅜ
-
현재 박종민쌤 공통 시즌1부터 쭉 듣고있고장재원 쌤 시즌2부터 듣고 있어요방학동안...
-
재밌어야 등급도 잘 나오는듯 3 2
국어 비문학 3개 풀면 아 ㅆㅂ 대가리 아파 담배피고와야지 수학 킬러 22번 풀고...
-
이환 이거 얼탱이내 1 0
시민 공격도 제대로 안되고 경찰와도 공격 타겟팅안되고 어떻게 잘 맞춰도...
-
꿈꾸러가겠습니다 0 1
꿈을이루고싶네요
-
수능 = 곧 능지인거같긴하다 1 0
수학은 개념 기출만 해도 높1 아래로 떨어져본적이 없는데 국어는 개념 기출 다 해두...
-
안녕히 주무세요 선생님,, 1 0
안 좋을 만한 일은 반드시 안 좋게 흘러가기 마련이기 때문에 항상 최악에 대비해야...
-
ㄹㅇ
-
어릴때 보면서 0 1
웃던 합성영상들 날짜 10년전 찍혀있는거 보니까 기분이 묘하네 나도이렇게늙어가는건가
-
배고픔 0 0
돈아끼기 1일차라 굽는중 빵 굽는중 ㅇ
-
요즘도 사탐런 많이 하나요? 1 0
궁금 미적은 엄청 줗었더라구여
-
오롤끝 0 0
오늘은 정병와서 롤함
-
28수능 200일의 전사 2 0
주최해보고십음
-
해놓고 까먹고 있었네
-
빡갤을 좀 참고해야...
-
? 4 0
-
기만하는사람 다 차단했더니 3 0
글이 안올라오네 뭐임
-
지금은 어느정도 고쳐지긴 한것같지만 그냥 다같이 조금씩 망하는 사람이 됨
-
학평 결산 9 1
국어1등급 : 9회2등급~ : 0회수학1등급 : 7회2등급 : 2회3등급~ :...
-
학교가면등수를바로물어봐야제 0 0
우리학교이런거존나안알랴줘서 ㅆㅂ 뭐알아야공부를하든휴학을하든하지
-
200일 전사 변수 하나 발생 0 1
토요일에 가족 여행가는중 알고 오늘 컴퓨터로 만들려 그랬는데 일요일...
-
5모 전까지 탈릅함 3 0
그 전에 오면 내가 진짜 여르비다
-
국어 하방을 어케 올리죠 0 0
진짜 뭔일이 있어도 3은 뜨면 안되는데 문언 시간단축 정확성 상승이 중요한가 국어...
-
학평등급 3 0
131113 121111 121111 131231 121311
-
모고간단결산 3 1
2503: 222111 2506: 221111 2509: 211111 2510:...
레드블랙은 아는데 avl 은 처음 들어봤네요.. 찾아보니 꽤 비슷하던데 avl 구현해보셨으면 다음엔 레드블랙 트리 한번 해보시죠 ㅎㅎ
https://ko.m.wikipedia.org/wiki/레드-블랙_트리
레드 블랙 트리, 2-3트리, 2-3-4트리.. avl 트리, B-트리 등등 균형 이진 트리 계열은 비슷한 측면들이 많은 것 같습니다 ㅎㅎ 개인적으로 학부 자료구조 수업에서 균형 이진 트리까지 배우지 않는 경우가 있어서 아쉬웠어요. 트리의 균형성을 어떻게 맞출 수 있는가에 대한 고민은 참 중요한 것 같은데 말입니다.
학부에서 이걸 안배우는 경우도 있나요? 저희 학교는 아직 수업을 안들어봐서 모르겠지만 배웠으면 좋겠군요. 트리에서 균형이 굉장히 중요한데 말이죠..
아무래도, 전체 학기가 14-15주차로 구성되어있고 그 안에서 링크드리스트에서 그래프까지 진도를 빼야하다 보니, 자료구조 수업 자체가 pre-알고리즘 수업으로 변질되는 경우가 더러 있는 것 같더라구요.
실제로, 제가 이수했던 수업에서는 트리 쪽 단원에서 균형 이진 트리라는 구조가 있다는 것을 간단하게 소개만 하고, 다른 자료구조나 알고리즘으로 넘어가더라구요. 시험 문제 같은 경우도, 자료구조 구현에 대한 측면보다는 알고리즘 관련 손코딩 문제가 많이 나왔던 것 같고...
교수님마다, 또 서적마다 차이가 있겠습니다만, 자료구조 수업에서 알고리즘 얘기는 가급적 줄이는 것이 맞다고는 생각하고 있습니다. 그럴 거면, 굳이 자료구조와 알고리즘 과목을 분리할 이유가 없으니까요. 또, 모든 알고리즘은 근본적으로 자료구조에 의존적이기 때문에, 자료구조 수업에서는 특정 자료구조에 대한 상세한 배경, 원리, "다양한" 구현 방식, 예시와 같은 것들을 많이 다루는게 맞다고 봅니다.
확실히 대학 수업만으론 컴퓨터 과학의 방대한 분량을 자세히 다 다루긴 어렵겠네요… 이거 제 생각엔 아무래도 초등학교때부터 자료구조를 배우도록 해야 겠군요(?) 초등학교 숙제로 ps 하나씩 풀어오게 하고 ㅎㅎ
아마 그런 날이 오는 시기도 얼마 남지 않았겠죠. 프로그래밍 과목이 국영수 처럼 기본 영역으로 편입될 여지는 얼마든지 있다고 봅니다 ㅎㅎ