컴공 일기230
게시글 주소: https://orbi.kr/00062187328
균형 이진 트리 중 하나인 AVL 트리를 구현하고 있습니다. 자료구조를 구현할 땐, 먼저 SKETCH를 해놓고 전체적인 구조를 이해하는 것이 중요한 것 같아요. 뇌가 64비트 인텔 CPU와 동기화가 되지 않은 이상이요...
트리(Tree)라는 자료구조의 장점 중 하나는, 탐색에서 굉장히 유용하다는 거에요. 10억개의 데이터가 들어와도, 높이가 30을 넘지 않기 때문에 몇 번의 탐색으로도 해당 데이터를 빠르게 찾아낼 수 있죠. 하지만, 이건 이상적인 얘기입니다. 트리 자체가 왼쪽과 오른쪽이 고르게 분포된 상태라면, 그 장점을 발휘할 수 있지만, 삽입 또는 삭제가 되는 과정에서 트리의 균형이 무너지게 되면, 자칫 잘못하면 10억 개의 데이터를 찾을 때 10억번을 검색해야 할 수도 있기 때문입니다.
조금 이상하죠. 장점이 탐색인데, 단점이 탐색이라니... 따라서, 트리를 구현할 때 "Balancing"이라고 하는 이슈가 중요하게 됩니다. 말하자면, 삽입과 삭제를 할 때, 트리가 왼쪽 혹은 오른쪽으로 쏠리지 않도록 재조정을 해주는 것이지요. 이렇게 된다면, 탐색의 성능을 굉장히 잘 발휘할 수 있으니까요.
AVL트리는 기존의 트리에 "Balancing" 기능을 추가해주어서 트리의 균형을 잘 잡아주는 구조라 할 수 있겠습니다. 따라서, 일반 이진트리나 이진 탐색 트리에 비해서 훨씬 더 안정적이라고 볼 수 있고, 더 고급(?) 자료구조라고 볼 수 있겠네요.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
레드블랙은 아는데 avl 은 처음 들어봤네요.. 찾아보니 꽤 비슷하던데 avl 구현해보셨으면 다음엔 레드블랙 트리 한번 해보시죠 ㅎㅎ
https://ko.m.wikipedia.org/wiki/레드-블랙_트리
레드 블랙 트리, 2-3트리, 2-3-4트리.. avl 트리, B-트리 등등 균형 이진 트리 계열은 비슷한 측면들이 많은 것 같습니다 ㅎㅎ 개인적으로 학부 자료구조 수업에서 균형 이진 트리까지 배우지 않는 경우가 있어서 아쉬웠어요. 트리의 균형성을 어떻게 맞출 수 있는가에 대한 고민은 참 중요한 것 같은데 말입니다.
학부에서 이걸 안배우는 경우도 있나요? 저희 학교는 아직 수업을 안들어봐서 모르겠지만 배웠으면 좋겠군요. 트리에서 균형이 굉장히 중요한데 말이죠..
아무래도, 전체 학기가 14-15주차로 구성되어있고 그 안에서 링크드리스트에서 그래프까지 진도를 빼야하다 보니, 자료구조 수업 자체가 pre-알고리즘 수업으로 변질되는 경우가 더러 있는 것 같더라구요.
실제로, 제가 이수했던 수업에서는 트리 쪽 단원에서 균형 이진 트리라는 구조가 있다는 것을 간단하게 소개만 하고, 다른 자료구조나 알고리즘으로 넘어가더라구요. 시험 문제 같은 경우도, 자료구조 구현에 대한 측면보다는 알고리즘 관련 손코딩 문제가 많이 나왔던 것 같고...
교수님마다, 또 서적마다 차이가 있겠습니다만, 자료구조 수업에서 알고리즘 얘기는 가급적 줄이는 것이 맞다고는 생각하고 있습니다. 그럴 거면, 굳이 자료구조와 알고리즘 과목을 분리할 이유가 없으니까요. 또, 모든 알고리즘은 근본적으로 자료구조에 의존적이기 때문에, 자료구조 수업에서는 특정 자료구조에 대한 상세한 배경, 원리, "다양한" 구현 방식, 예시와 같은 것들을 많이 다루는게 맞다고 봅니다.
확실히 대학 수업만으론 컴퓨터 과학의 방대한 분량을 자세히 다 다루긴 어렵겠네요… 이거 제 생각엔 아무래도 초등학교때부터 자료구조를 배우도록 해야 겠군요(?) 초등학교 숙제로 ps 하나씩 풀어오게 하고 ㅎㅎ
아마 그런 날이 오는 시기도 얼마 남지 않았겠죠. 프로그래밍 과목이 국영수 처럼 기본 영역으로 편입될 여지는 얼마든지 있다고 봅니다 ㅎㅎ