진짜 명강의 감사합니다. 한가지 궁금한게 있는데 28:15부터 나오는 시간복잡도에서 worst의 경우 빅오메가(logN)(==아무리 실행시간이 빨라도 logN에 비례하는 정도 이하이다)로 표현 불가능해서 빅세타(logN)이 안되는걸까요? 시간복잡도 영상에서 binary search 함수의 시간복잡도 같은 경우 worst의 경우도 빅세타(logN)이였던 것 같은데 무슨 차이일까요...? 다시 한번 감사드립니다.
답변이 늦어서 죄송합니다ㅠㅠ 네 맞습니다! Θ(logN)도 가능합니다! 사실 다들 상한선을 궁금해하기 때문에 Θ(빅-세타) 표현은 잘 안쓰고 O(빅-오)를 많이 쓰다보니 저도 저렇게 쓴 것 같아요. 그리고 저 PPT를 만들 당시에 조금 애매한 부분도 하나가 있었던 것 같은데,, 지금 사실 잘 기억이 안납니다..ㅠㅠ 지금 제 생각은 여하튼 worst case를 Θ(logN)이라고 해도 될 것 같아요!
오~ 가령 50(루트노드)-70-60이 오른쪽-왼쪽 편향일 때 70이 루트 노드가 되어도 될 것 같다는 말씀이신거 맞죠? 70이 만약 루트노드가 된다면 50과 60은 어느 위치에 자리 잡아야 하는지 생각해본다면 조금 더 이해하시는데 도움이 되실 것 같아요. 만약 70이 루트 노드가 된다면 이진탐색트리의 특징을 만족시키기 위해서 50과 60이 모두 70의 왼쪽 서브트리에 위치해야 하는데, 그럼 결국 높이 차가 줄어들지 않게 되죠 ㅠ 그래서 높이 차를 줄여주면서도 동시에 이진탐색트리의 특징(모든 노드에서 왼쪽 서브트리는 자신보다 작은 값을 가지고 오른쪽 서브트리는 자신보다 큰 값을 가지는 특징)을 만족 시켜주려면 가운데 값인 60이 루트 노드가 되어야 합니다 (혹시 제가 질문의 의도를 잘못 이해했다면 알려주세요~)
맞아요~ AVL 트리의 균형 인수가 헷갈릴만 합니다ㅠ bf(50)을 계산할 때 50을 기준으로 50의 왼쪽 서브트리의 높이는 (아무 노드도 없기 때문에) -1이 되고 50의 오른쪽 서브트리의 높이는 1이 되기 때문에 왼쪽과 오른쪽의 높이 차는 -1 - (1)이 여서 -2가 됩니다~
질문에 오타인거죠? 언제 선임자 교체하고 언제 후임자 교체하는지인거죠?? 선임자 교체인지 후임자 교체인지는 정해진건 없습니다. 다만, 선임자로 선택하기로 했으면 쭉 선임자를 일관되게 선택해야하고, 후임자로 선택하기로 했으면 쭉 일관되게 후임자로 선택하는게 좋습니다. (트리마다 다를 순 있겠지만 제대로 잘 동작하려면 이렇게 해야할겁니다)
교수님 설명이 매우 아쉬웠는데 덕분에 이해가 잘 됐습니다! 감사합니다
답변이 늦었습니다 ㅠㅠ 영상을 좋게 봐주셔서 넘넘 감사합니다 :)
드디어 다음 편에 나오는군요!! Red and black tree !! 나올때까지 숨참고 기다립니다
드디어!! 마침내 레드블랙트리를 남겨 놓고 있습니다!! 곧 찾아뵐게요~ :)
영상 오매불망 기다렸습니다. 고고씽~~~~ 항상 도움 주셔서 감사드립니다.
와우~! 기다려주셔서 감사합니다 :)
또 감사드립니다.
최고십니다!
진짜 명강의 감사합니다.
한가지 궁금한게 있는데 28:15부터 나오는 시간복잡도에서
worst의 경우 빅오메가(logN)(==아무리 실행시간이 빨라도 logN에 비례하는 정도 이하이다)로 표현 불가능해서 빅세타(logN)이 안되는걸까요?
시간복잡도 영상에서 binary search 함수의 시간복잡도 같은 경우 worst의 경우도 빅세타(logN)이였던 것 같은데 무슨 차이일까요...?
다시 한번 감사드립니다.
답변이 늦어서 죄송합니다ㅠㅠ 네 맞습니다! Θ(logN)도 가능합니다! 사실 다들 상한선을 궁금해하기 때문에 Θ(빅-세타) 표현은 잘 안쓰고 O(빅-오)를 많이 쓰다보니 저도 저렇게 쓴 것 같아요. 그리고 저 PPT를 만들 당시에 조금 애매한 부분도 하나가 있었던 것 같은데,, 지금 사실 잘 기억이 안납니다..ㅠㅠ 지금 제 생각은 여하튼 worst case를 Θ(logN)이라고 해도 될 것 같아요!
다시한번 감사드립니다~
유튜브를 통해 본 강의중 최고입니다! 이렇게 명쾌하고 쉽게 설명하시다니.. 감동입니다ㅠㅠ 바로 구독하고 갑니다:)
와우 이렇게 극찬해주셔서 감사합니다 ㅠㅠㅠ 게다가 구독까지 ㅠㅠ
앞으로도 좋은 콘텐츠로 인사드릴게요!! :) 👍
따끈따끈한 강의 감사합니다 ㅎㅎ
크 오랜만에 영상 올리게 됐어요ㅎ 다시 달려봐야죠~!ㅎㅎ 감사합니다 :)
항상 자세한 설명 감사드립니다!
우와아~~ 댓글은 언제나 큰 힘이 됩니당~ㅎㅎ 저도 감사합니다 :)
감사합니다
면접 준비하면서 하나씩 보고 있는데 정말 쉬운 코드입니다ㅠㅠ 이해하면서 공부하는 재미를 느끼게 해주셔서 감사합니다!
크~ 좋게 봐주셔서 감사합니다 :)
면접 응원합니다!! 원하시는 곳에 가실 수 있을 거예요 👍
쉬운 설명 너무 감사드립니다!!!! 최고!!
답글이 많이 늦었네요 ㅠㅠ 좋게 봐주셔서 정말 감사합니다!!
너무 알차요. 단번에 이해 됐어요, 감사합니다!
이제야 댓글 남겨요 ㅠ 영상 좋게 봐주셔서 넘 감사해요~!
설명 너무 잘하세요!!! 감사합니다 !
답글이 많이 늦었습니다 ㅠㅠ 칭찬의 말씀 너무 감사합니다~!!
레드블랙트리 기대하고 있겠습니다. 감사합니다.
넵~!ㅎㅎ 조만간 레드블랙트리와 함께 인사드릴게요~ 감사합니다 :)
덕분에 avl 트리에 대해서 이해했습니다 감사합니다!
도움된 것 같아서 뿌듯하네요 :)
댓글 감사합니다!
감사합니다! 잘 몰라서 하는 질문인데 오른쪽(왼쪽)- 왼쪽(오른쪽) 편향인 경우 루트 노드로 중간값이 선택이 되는 이유가 있나요? 중앙 노드(ex. 50-70-60에서 70)가 루트 노트가 되어도 상관없지 않나요..?
오~ 가령 50(루트노드)-70-60이 오른쪽-왼쪽 편향일 때 70이 루트 노드가 되어도 될 것 같다는 말씀이신거 맞죠?
70이 만약 루트노드가 된다면 50과 60은 어느 위치에 자리 잡아야 하는지 생각해본다면 조금 더 이해하시는데 도움이 되실 것 같아요.
만약 70이 루트 노드가 된다면 이진탐색트리의 특징을 만족시키기 위해서 50과 60이 모두 70의 왼쪽 서브트리에 위치해야 하는데, 그럼 결국 높이 차가 줄어들지 않게 되죠 ㅠ
그래서 높이 차를 줄여주면서도 동시에 이진탐색트리의 특징(모든 노드에서 왼쪽 서브트리는 자신보다 작은 값을 가지고 오른쪽 서브트리는 자신보다 큰 값을 가지는 특징)을 만족 시켜주려면 가운데 값인 60이 루트 노드가 되어야 합니다
(혹시 제가 질문의 의도를 잘못 이해했다면 알려주세요~)
아.. 이해 됐습니다 감사합니다! 회전만 신경쓰다가 높이를 생각하지 못했네요
@@joosungkwon5939 넵 저도 AVL 트리 헷갈릴 때가 많더라구요~ 응원합니다 :)
궁금한게 있는데 노드 90이 생겼을 때 bf(50)계산할 때는 부호가 안붙고 그냥 노드 길이만 계산하는건가요? 부호가 붙으면 -1-(-1)이여서 0이 되는거 아닌가 해서요ㅜㅜ 균형인수가 너무 헷갈리네요...ㅠㅠ
맞아요~ AVL 트리의 균형 인수가 헷갈릴만 합니다ㅠ
bf(50)을 계산할 때 50을 기준으로 50의 왼쪽 서브트리의 높이는 (아무 노드도 없기 때문에) -1이 되고 50의 오른쪽 서브트리의 높이는 1이 되기 때문에 왼쪽과 오른쪽의 높이 차는 -1 - (1)이 여서 -2가 됩니다~
@@ezcd 감사합니다! 다른 영상은 봐도 이해가 안됐는데 이 영상보고 이해됐어요 유레카 ㅠㅠ
최고네요
답글이 늦었습니다 ㅠㅠ 좋게 봐주셔서 감사합니다!!
알기 쉬운 설명 감사합니다! 질문있습니다! 이진트리에서 루트를 레벨0으로 보는사람도있고 레벨1로 보는 사람도 있던데 상관없나요? 루트가 레벨0이냐 레벨1이냐에 따라서 트리의 높이가 달라지는거 아닌지..
네 맞습니다~! 그래서 기준을 어떻게 잡는지에 따라 높이가 1씩 차이납니다
그래서 문서를 읽을 때 이걸 염두하면서 보시면 좋습니다 :)
설명 덕에 이해했어요 T_T
오 좋네요~!! 도움이 된 것 같아서 저도 뿌듯합니다 :)
항상 화이팅이에요!!
어떨 때는 루트와 선임자를 교체하고 어떨때는 루트와 선임자를 교체하게 되나요?? 정해진게 있을까요?? b tree부터 수업을 듣고 있어 헷갈리는 점이 있어 댓글남깁니다!
질문에 오타인거죠? 언제 선임자 교체하고 언제 후임자 교체하는지인거죠?? 선임자 교체인지 후임자 교체인지는 정해진건 없습니다. 다만, 선임자로 선택하기로 했으면 쭉 선임자를 일관되게 선택해야하고, 후임자로 선택하기로 했으면 쭉 일관되게 후임자로 선택하는게 좋습니다. (트리마다 다를 순 있겠지만 제대로 잘 동작하려면 이렇게 해야할겁니다)
@ 아 오타 맞습니다. 아 둘중하나 선택하면 되군요 감사합니다. 레드블랙 비트리 avl 다 너무 잘 들았습니다!
@@exanderal4294 크~~! 시청해주셔서 넘넘 감사합니다!! ❤😍
Avl 개념에서 bf값이 30은 -1 90은0은 이해가 되는데요 70과 50이 어떻게 -1이 되는지 모르겟습니다 ㅜㅜ
앗, 혹시 몇분 몇초 부분이죠?
@@ezcd 1분 50초 입니다!
이때는 50의 왼쪽서브트리 30 ㅡ 40이(LR경우) 만약
30 -10 (LL인 경우)라고 해도 똑같이 50의 bf는 1-2로 -1로 봐도되는건가요?
네 그렇습니다~!
높이의 개념이 트리의 루트 노드에서 가장 멀리 떨어져있는 leaf 노드 까지의 edge 수이기 때문에 그렇습니다~!
GOAT
이제야 답글을 남기네요 ㅠㅠ 칭찬의 말씀 감사드립니다!!
👍
우앗ㅠㅠ 멤버십 가입 정말 감사합니다!! 최최고 😍👍
알고리즘 과목에서 이거 C로 코딩하라했을때 엄청 힘겨웠던 기억이 있네요...ㅋㅋ
오 저도 이거 대학 때 C로 코딩하는 거 있었는데, 왼쪽으로 돌리고 오른쪽으로 돌리고 뭘 계속 돌려야 해서 짜파게티 먹는 줄 알았네요 ㅋㅋㅋ
ㄱㄱ씽~
키아 달리시는군요~👍
말을 쓸데 없이 왜 이리 빨리하남? 호떡집에 불났삼? 패쓰!!!!!!!!
어허
제가 마음이 급했나봐요 ㅠㅠ