몇 가지 코멘트를 남깁니다~ 08:24 설명할 때 노드를 방문할 때 마다 노란색으로 동그라미를 그려주면서 설명을 했기 때문에, 이 타이밍에서 20에 노란색 동그라미를 그렸어야 했습니다. 제가 놓친 부분인데 혹시 보시면서 헷갈리실까 싶어서 코멘트 남깁니다. inorder traversal를 한다고 무조건 트리의 노드의 값 순서대로 방문하는 것은 아닙니다. 이진탐색트리에 한해서 inorder traversal를 하게 되면 노드의 값 순서대로 방문하게 되는 것입니다. 모두 잘 이해하셨겠지만 혹시나 오해가 있을까봐 코멘트 남깁니다. 구현의 관점에서 임의의 노드의 successor를 구하는 방법은 만약 그 노드의 오른쪽 서브트리가 있다면 그 오른쪽 서브트리에서 최소값을 가지는 노드를 찾으면 되구요, 오른쪽 서브트리가 없다면 그 노드의 조상들을 거꾸로 찾아올라가면서 처음으로 (좌측 상단이 아니라) 우측 상단으로 거슬러 올라가서 만나게 되는 조상 노드를 찾으면 됩니다. 반대로 구현의 관점에서 임의의 노드의 predecessor를 구하는 방법은 만약 그 노드의 왼쪽 서브트리가 있다면 그 왼쪽 서브트리에서 최대값을 가지는 노드를 찾으면 되구요, 왼쪽 서브트리가 없다면 그 노드의 조상들을 거꾸로 찾아올라가면서 처음으로 (우측 상단이 아니라) 좌측 상단으로 거슬러 올라가서 만나게 되는 조상 노드를 찾으면 됩니다. 이진탐색트리의 시간복잡도 관련 내용을 찾아보면 일부 문서에서는 best case를 O(logN)으로 표기하는 경우를 보실 수 있는데요, 왜 이런 차이가 발생하냐면, 쉬운코드 영상에서는 best case에 해당하는 특정 상황을 찾아서 시간복잡도를 구했다면, 트리의 구조에 따라서 case를 구분하여 시간복잡도를 구할 수도 있어서 그렇습니다. 예를 들어, 중간에 하나도 노드가 비어있지 않은 꽉찬(perfect) 이진 탐색 트리를 best case로 놓고, 적당히 밸런스가 있는(혹은 밸런스가 랜덤성을 띄는) 이진 탐색 트리를 average case로 놓고, 편향된 이진 탐색 트리를 worst case로 놓고 시간복잡도를 분석을 할 수가 있는데요, 이 경우에는 best case의 시간복잡도가 O(logN)이 됩니다.
몇 가지 코멘트를 남깁니다~
08:24 설명할 때 노드를 방문할 때 마다 노란색으로 동그라미를 그려주면서 설명을 했기 때문에, 이 타이밍에서 20에 노란색 동그라미를 그렸어야 했습니다.
제가 놓친 부분인데 혹시 보시면서 헷갈리실까 싶어서 코멘트 남깁니다.
inorder traversal를 한다고 무조건 트리의 노드의 값 순서대로 방문하는 것은 아닙니다.
이진탐색트리에 한해서 inorder traversal를 하게 되면 노드의 값 순서대로 방문하게 되는 것입니다.
모두 잘 이해하셨겠지만 혹시나 오해가 있을까봐 코멘트 남깁니다.
구현의 관점에서 임의의 노드의 successor를 구하는 방법은 만약 그 노드의 오른쪽 서브트리가 있다면 그 오른쪽 서브트리에서 최소값을 가지는 노드를 찾으면 되구요, 오른쪽 서브트리가 없다면 그 노드의 조상들을 거꾸로 찾아올라가면서 처음으로 (좌측 상단이 아니라) 우측 상단으로 거슬러 올라가서 만나게 되는 조상 노드를 찾으면 됩니다.
반대로 구현의 관점에서 임의의 노드의 predecessor를 구하는 방법은 만약 그 노드의 왼쪽 서브트리가 있다면 그 왼쪽 서브트리에서 최대값을 가지는 노드를 찾으면 되구요, 왼쪽 서브트리가 없다면 그 노드의 조상들을 거꾸로 찾아올라가면서 처음으로 (우측 상단이 아니라) 좌측 상단으로 거슬러 올라가서 만나게 되는 조상 노드를 찾으면 됩니다.
이진탐색트리의 시간복잡도 관련 내용을 찾아보면 일부 문서에서는 best case를 O(logN)으로 표기하는 경우를 보실 수 있는데요,
왜 이런 차이가 발생하냐면, 쉬운코드 영상에서는 best case에 해당하는 특정 상황을 찾아서 시간복잡도를 구했다면, 트리의 구조에 따라서 case를 구분하여 시간복잡도를 구할 수도 있어서 그렇습니다.
예를 들어, 중간에 하나도 노드가 비어있지 않은 꽉찬(perfect) 이진 탐색 트리를 best case로 놓고, 적당히 밸런스가 있는(혹은 밸런스가 랜덤성을 띄는) 이진 탐색 트리를 average case로 놓고, 편향된 이진 탐색 트리를 worst case로 놓고 시간복잡도를 분석을 할 수가 있는데요, 이 경우에는 best case의 시간복잡도가 O(logN)이 됩니다.
엄청 상세하게 설명해주시네요. 감사합니다
깔끔하게 설명해주셔서 너무 좋아요 잘 보고 있습니다!
헤헤 좋은 피드백 주셔서 기분이 좋으네요 :) 늘 애청해 주셔서 고맙습니다👍
진짜......너무 좋습니다.......이진 탐색 트리에관한 개념정리 확실히 되었습니다! 감사합니다!
와 너무 최고에요 💯 🥹 설명 쏙쏙 들어옵니다.... ㅎㅎ
오우 그렇다면 정말 다행입니다 :) 👍👍
고고씽~~~ 항상 감사드립니다
저도 항상 감사드려요 ㅠㅠ
레드 블랙 트리 알아보다가 바이너리 서치 트리가 헷갈려서 우연히 들어왔는데 목소리가 시원시원 하시고 정말 명 강의네요,, 이해가 쏙쏙 됩니다.
유익한 강의 감사합니다!!!
헤헤 좋게 봐주셔서 감사합니다 :) 자주 놀러와 주세요~!
감사드려요~~
저도 감사합니다아 :)
영상들 너무 감사합니다😊
헤헤 저도 댓글 항상 감사합니다 :)
감사합니다❤
증말 감사합니다.
재귀 설명해주신거 정말 도움 되었습니다. ㅜㅜ
도움드릴 수 있어서 저도 뿌듯하네용 😊
감사합니다. ㅎ
따봉입니다👍
하..면접 때문에 자료구조 책 사서 보다가 개같이 멸망하고 D-5일전 이 영상을 보았네요.. 어차피 코드 적인 부분은 안물어볼거같아서 개념만 다 보고 정리해야겠어요 쉬운 설명 감사합니다!!
오우 다음주 면접인가 보네요 화이팅입니다!!!
재생목록에 면접팁 영상도 있으니까요, 그것도 참고해주시면 어쩌면 도움이 될지도 모르겠어요
좋은 결과 있을거에요!!!
이해하기 쉬운 설명 감사합니다 여태들은 것중에 가장 좋은듯 자료구조 알고리즘 자료 좋습니다
크~!! 좋게 말씀 해주셔서 감사합니다 :)
자주 놀러와 주세요~ 좋은 컨텐츠로 기다리고 있을게용 👍
감사합니당
저도 댓글 감사합니다 :)
시간 복잡도를 나타낼때, O(log N) 은 알겠는데, 최선과 최악일때 왜 세타로 표현되는 건가요?