[Powered by Google Translate] [제 7 조] [이하 편안한] [네이트 Hardison] [하버드 대학] [이 CS50 수 있습니다.] [CS50.TV] 

제 7에 오신 것을 환영합니다. , 허리케인 샌디 덕분에 대신 이번 주 일반 섹션을 갖는, 우리는 질문의 섹션을 통해, 워크를 통해이 일을하고 있습니다. 나는 6 사양을 설정 문제와 함께 따라갈 거예요 과의 모든 질문 겪고 질문 섹션의 섹션을 참조하십시오. 질문이있는 경우 CS50 토론에서 이러한 사항을 게시하시기 바랍니다. 

좋아. 의 시작하자. 지금은 문제 세트 사양의 3 페이지를 찾고 있어요. 우리가 처음 이진 나무에 대한 이야기​​를 시작 할거야 그 이번 주 문제 세트의 관련성을 많이 갖고 있기 때문에 - 허프만 트리 인코딩입니다. 우리가 CS50에 대해서 얘기 최초의 데이터 구조 중 하나는 배열했다. 배열 요소의 순서입니다 기억 - 같은 종류의 모든 - 메모리에 바로 서로 옆에 저장됩니다. 저는이 상자 - 숫자 - 정수 스타일을 사용하여 그릴 수있는 정수 배열이있는 경우 - 자, 내가 첫 번째 상자에 5를 말하면, 내가 두 번째에 7을 가지고 그럼 내가 마지막 상자에 8, 10, 20가 있습니다. 이 배열에 대한 기억, 둘은 정말 좋은 일 우리가 특정 요소에이 일정한 시간 액세스 권한이 있는지 아르  배열의 우리가 색인을 알고있는 경우. 예를 들면, 배열의 세 번째 요소를 마시고 싶으면 - 색인에 ​​2의 제로 기반의 색인 생성 시스템을 사용하여 - 나는 말 그대로 그냥 간단한 수학 계산을해야 , 배열의 해당 위치로 타 거기에 저장되어있는 8, 당겨 나는 갈 좋아. 

이 배열에 대한 나쁜 일들 중 하나 - 우리가 얘기하는 우리는 연결 목록을 논의 할 때 - 난이 배열에 요소를 삽입하려는 경우 즉, 좀 주위를 이동해야 겠어. 여기에 예를 들어,이 배열 정렬 순서에 - 오름차순으로 정렬 - 5 다음 다음 다음 7, 8, 10, 그리고 20 - 하지만 난이 배열로 9 번을 삽입 할 경우, 나는 공간을 만들기 위해 요소의 일부를 이동해야 겠어. 우리는 여기를 그릴 수 있습니다. 나는 5 7 이동해야 할 후 8 해요; 전 9 넣을 수 있습니다 갭을 만들 다음 10 20 9의 오른쪽으로 이동 할 수 있습니다. 이것은 고통의 종류 때문 최악의 시나리오에서 - 우리는 처음이나 끝 부분에 하나 삽입 할 필요 때 배열의, 방법에 따라 우리가 이동하고있다 - 우리는 모든 요소를​​ 이동 할 필요 끝낼 수 있습니다 우리는 현재 배열에 저장하고 있는지. 

그래서,이 주위에 방법은 무엇입니까? 이 주변의 방법은 어디에서 우리의 링크 목록 방법으로 이동하는 것이 었습니다 - 대신 요소 5, 7, 8, 10 및 메모리에 서로 옆에 20를 모두 저장하는 - 우리는 대신 우리가 그들을 저장하기 위해 원하는대로의 그들에게 친절을 저장 한 행동 이러한 링크 목록 노드에있는 내가 여기 애드혹 종류를 그리는거야. 그리고 우리는이 다음 포인터를 사용하여 함께 연결되어 있습니다. 나는 5 ~ 7 포인터를 가질 수 있습니다 7에서 8로 포인터 8에서 10 포인터 마지막으로, 10에서 20으로 포인터 그리고 20에서 널 포인터가 왼쪽 아무 것도 없다는 것을 나타냅니다. 우리가 여기있는 트레이드 오프 우리는 정렬 목록으로 9 번을 삽입하려는 경우 즉, 지금 우리가해야 할 모든 9로 새 노드를 만드는 , 해당 위치를 가리 키도록 그걸 송금 그리고 다시 와이어 8 9으로 지정합니다. 우리가 9를 삽입 할 위치를 우리가 정확히 아는 가정, 꽤 빠르다. 그러나이 교환의 트레이드 오프는 우리가 일정 시간 액세스 할 수없는 것입니다 우리의 데이터 구조의 특정 요소에. 예를 들어,이 링크 목록에 네 번째 요소를 찾으려면, 나는이 목록의 맨 처음부터 시작해야 겠어 제가 번째 하나를 찾을 때까지 노드의 노드 수를 헤아을 통해 내 방식대로 작동합니다. 

연결리스트보다 더 나은 액세스 성능을 위해 - 뿐만 아니라 우리가했던 혜택의 일부를 유지 연결리스트에서 삽입 시간의 관점에서 - 이진 트리가 좀 더 많은 메모리를 사용할 필요가 것입니다. 특히, 대신 이진 트리 노드에 하나 포인터를 갖는 - 링크 된 목록처럼 노드는 않습니다 - 우리는 이진 트리 노드에 두 번째 포인터를 추가 할거야. 보다는 다음 요소에 하나의 포인터를 갖는 우리는 왼쪽 자녀와 권리가 자녀에게 포인터를 할 겁니다. 

의 실제 모양이 볼 수있는 그림을 그려 보자. 다시,이 박스와 화살표를 사용하여 겠어. 이진 트리 노드는 단순한 상자로 시작합니다. 그것은 값에 대한 공간이거야 다음은 왼쪽 아이가하고 오른쪽 어린이를위한 공간이 겁니다. 내가 여기 라벨을거야. 우리는 왼쪽 아이를 가질 것, 그리고 우리는 바로 아이를 가질거야. 이 작업에는 여러 가지가 있습니다. 때때로 공간과 편의를 위해, 나는 바닥에 여기서 뭘하는 것처럼 사실을 그려 줄께요 제가 맨 위에있는 값을 가지고 어디로, 다음 하단 오른쪽에있는 오른쪽 아이 하단 왼쪽과 왼쪽 아이. 위에서 그림으로 돌아 간다, 우리는 매우 상단에있는 값이 그러면 우리는 왼쪽 아이가 포인터를 가지고 있고, 그런 다음에 우리가 오른쪽 자식 포인터가 있습니다. 

문제 세트 사양에서 우리는 값 7이있는 노드를 그리기에 대해 이야기 그리고 null입니다 왼쪽 자녀 포인터와 오른쪽 자식 포인터 null이입니다. 우리는 하나의 공간에서 자본 NULL를 작성할 수 왼쪽 자녀와 오른쪽 자녀, 또는 우리 모두가 대각선 슬래시를 그릴 수 상자의 각을 통해이 null입니다 나타냅니다. 그런 일이 간단해서 그 일을 할거야. 아주 간단한 이진 트리 노드를 다이어그램의 두 가지 방법은 당신이 여기에서 볼 아르 우리는 가치 7 널 아동 포인터가있는 곳. 

어떻게 연결 목록과 대한 우리의 사양 회담의 두 번째 부분 - 기억, 우리는 목록에 매우 첫 번째 요소에 개최했다 전체 목록을 기억해야 - 와 마찬가지로, 이진 나무, 우리는 나무 한 포인터에 개최해야 전체 데이터 구조에 대한 제어를 유지하기 위해 인치 나무의이 특별한 요소는 트리의 루트 노드라고합니다. 예를 들어,이 하나의 노드 - 값 7을 포함하는이 노드 - 널 왼쪽 및 오른쪽 아이 포인터로 우리 나무의 유일한 값이 있었다 다음이 우리의 루트 노드가 될 것입니다. 우리 나무의 처음입니다. 우리는 나무에 더 많은 노드를 추가되면 더 명확하게이 조금 볼 수 있습니다. 내가 새 페이지를 당겨 보자. 

이제 우리는, 루트에 7이 나무를 그릴거야 그리고 왼쪽 자녀, 오른쪽 아이의 9 내부의 3 안에. 다시 말하지만, 이건 정말 간단합니다. 우리는 7이 있고, 3 노드, 9 노드를, 그리 나는 3가 포함 된 노드를 가리 키도록 7 왼쪽 자녀 포인터를 설정하는거야 9를 포함하는 노드에 7이 포함 된 노드의 오른쪽 자식 포인터. 지금, 3부터 9는 아이가 없습니다 우리는 널 (null)로 자녀 포인터를 모두 설치하도록한다. 여기, 우리의 트리의 루트는 숫자 7을 포함하는 노드에 해당합니다. 우리가 가진 그 루트 노드에 대한 포인터입니다 경우, 그를 볼 수 있습니다 우리는 우리의 나무를 통과하고 자식 노드를 모두 액세스 할 수 있습니다 - 3 구 모두. 아니오 트리에있는 모든 단일 노드 포인터를 유지 할 필요가 없습니다. 좋아. 이제 우리는이 다이어그램에 다른 노드를 추가 할거야. 우리는 6을 포함하는 노드를 추가 할거야 우리는 3가 포함 된 노드의 오른쪽 자식으로 추가 할거야. 그 작업을 수행하려면, 내가 3 노드에서 해당 NULL 포인터를 지울거야 6를 포함하는 노드를 가리 키도록 그걸 송금. 좋아. 

이 시점에서, 그럼 용어가 좀 이상 가자. , 이것은 특히 이진 트리라고 이유를 시작하려면 그 두 아이 포인터를 가지고 있다는 것입니다. 더 많은 어린이 포인터가 나무의 다른 종류가 있습니다. 특히, 당신은 문제가 세트 5 '시도'했어요. 당신이 시도에 것을 볼 수, 당신은 다른 아이들에게 27 개의 포인터를 했어요 - 영어 알파벳의 26 글자 각각에 대해 하나 다음 생략 부호를위한 27 - 그래서, 그 나무의 유형과 비슷합니다. 하지만 여기, 이건 진 이후, 우리는 두 아이 포인터가 있습니다. 

우리가 얘기하는이 루트 노드뿐만 아니라, 우리는이 용어 주위에 던져 했어요 '아이.' 한 노드가 다른 노드의 하위되는 것이 무엇을 뜻합니까? 그것은 말 그대로 자​​식 노드가 다른 노드의 자식을 의미합니다 다른 노드가 해당 노드를 가리 키도록 설정 하위 포인터 중 하나를있는 경우. 이 더 구체적인 용어로해라 3 7 자녀 포인터 중 하나가 점을 지적하는 경우, 3 다음 7의 자식입니다. - 우리가 7의 아이들이 무엇을 할 수 있는지 알아내는라면 그래, 우리가, 7 3 포인터, 9에 대한 포인터를 가지고 볼 수 그래서 9 3 7 아이들입니다. 나인은 자식 포인터가 null이기 때문에 자식이 없습니다, 3는 한 자녀 6이 있습니다. 그 포인터 모두 우리가 지금 그려 줄게 널, 때문에 여섯 또한 자식이 없습니다. 

또한, 우리는 또한, 특정 노드의 부모님에 대한 얘기 당신이 기대대로이는이 아이 설명의 역이다. 대신 두가 인간과 예상대로 - 각각의 노드는 하나의 부모가 있습니다. 예를 들어, (3)의 부모는 7입니다. 9 부모도 7, 6의 부모는 3입니다. 거기에 많이는 말고. 또한, 조부모와 손자 얘기 할 조건이 있습니다 더 일반적으로 우리는 조상에 대해 이야기 그리고 특정 노드의 자손. 노드의 대신이나 조상, - 노드의 조상 - 루트에서 해당 노드에 대한 경로에 누워 노드에 있습니다. 예를 들면, 노드 6에 찾고 있어요 경우, 그리고 조상은 3과 7 모두가 될 것이다. 9 조상들은 예를 들어, 아르 - 나 노드 9시를 찾고 있어요있는 경우 - 그리고 9 조상은 7입니다. 그리고 자손은 정확히 반대입니다. 나는 7 자손의 모든보고 싶다면, 그럼 내가 그 아래 노드의 모든보고해야합니다. 그래서 7의 자손으로 3, 9, 6을 모두 갖추고 있습니다. 

우리가 얘기하겠다고 마지막 용어는 형제되는이 개념입니다. 형제 -이 가족 조건에 따라 다음과 같은 종류의 - 트리에서 동일한 수준의 노드 수 있습니다. 그들은 트리에서 같은 수준이기 때문에 따라서 3 9 형제입니다. 둘 다 같은 부모, 7을 갖추고 있습니다. 9 아이가 없기 때문에 6는 형제가 없습니다. 그게 우리의 트리의 루트이기 때문에 그리고 7, 어떤 형제가 없습니다 만 어느 한 루트가 있습니다. 7 형제가 거기에 7 위 노드 있어야합니다. 더 이상 트리의 루트 없을 것이 경우 7 7의 부모,이있을 수 있습니다 것입니다. 그런 다음 7의 새로운 부모도 아이를 가질해야 그 아이는 7 형제가 될 것입니다. 

좋아. 움직여. 우리가 이진 나무의 우리의 논의를 시작했을 때, 우리는 우리가 그들을 사용하는 거라고하는 방법에 대해 이야기 배열과 링크 된 목록을 모두 이상의 장점을 습득합니다. 그리고 우리가 할 수있는 것 방법이 주문 재산이다. 우리는 사양에 따라 이진 트리가 주문되는 말 우리 나무의 각 노드에 대해 경우, 왼쪽의 자손​​의 모든 - 왼쪽 자녀와 왼쪽 자녀의 자손의 모든 - 작은 값을, 오른쪽에있는 노드의 모든이 - 오른쪽 아동과 오른쪽 아이의 자손의 모든 - 우리가보고있는 현재 노드의 값보다 큰 노드가 있습니다. 그냥 단순에, 우리는 트리의 중복 노드가 없을 거라 생각하고 있습니다. 예를 들어,이 나무에서 우리는 경우를 처리 할 수​​ 없어 우리는 루트에서 값이 7이있는 곳  그리고 우리는 또한 값이 다른 나무에서 7을 갖추고 있습니다. 이 경우, 당신은이 나무가 실제로 주문이된다는 것을 명심해야합니다. 우리는 루트에서 값이 7이 있습니다. 7 왼쪽에 모든 - 여기이 작은 마르크의 모든 사항을 취소하는 경우 - 7 왼쪽에 모든 - 3 6 - 이러한 값은 모두 일곱보다이며, 오른쪽에있는 모든 - 그냥이 9입니다 - 7보다 큽니다. 

이이 값을 포함하는 유일한 명령을 나무 아니라, 하지만 우린 그 중 몇 가지 더 그려 보자. 우리가 이런 일을 할 수있는 방법을 아주 많이 실제로있다. 난 그냥 어디에서 일을 간단하게하기 위해 속기를 사용하여 갈거야 - 오히려 박스 - 및 - 화살표 전체를 그리기보다 - 난 그냥 숫자를 그리하고 연결 화살표를 추가 할거야. , 3 후, 시작하려면 우리가 7을 한 곳에서 우리는 다시 우리의 원래의 트리를 작성되고, 그리고 3 6 오른쪽으로 돌아 지적 그리고 7 9 살 권리가 아이도 가졌어요. 좋아. 우리가이 나무를 작성할 수있는 또 다른 방법은 무엇입니까? 3 갖는 것은, 7의 왼쪽 자식 대신에 우리는 또한 6, 7의 왼쪽 자식 가질 수 그리고 3은 6의 왼쪽 자식. 나는 7이있어있는 곳 바로 여기이 나무처럼 보인다는 건가요 다음엔 6, 3, 오른쪽에 9. 우리는 또한 루트 노드 7이 할 필요가 없습니다. 우리는 또한 루트 노드로 6을 만들 수 있습니다. 어떤 모양 겠어요? 우리는이 주문한 재산을 유지하려는 경우, 6의 왼쪽에 모든 게 이상이어야합니다. 이 하나의 가능성은, 그리고 3입니다. 하지만 6의 오른쪽 자식으로, 우리는 두 가지 가능성이 있습니다. 첫째, 우리는 9 다음 7이 있으며 수 또는 우리가 그릴 수 있어요 - I가 여기서 할 것 같은 - 우리가 6의 오른쪽 자식으로 9을 가지고있는, 그리고 9의 왼쪽 어렸을 때 7. 

이제 7 6 루트 만 가능한 값이 아닙니다. 우리는 또한 3 루트에 있어야 만들 수 있습니다. 3 루트에있는 경우 어떻게됩니까? 여기 일이 좀 흥미로운. 셋, 그 미만에 값이 없습니다 그래서 나무의 전체 왼쪽은 null이 될 것입니다. 뭐가있을 거라 구요. 오른쪽, 우리는 오름차순으로 물건을 나열 수 있습니다. 우리는 3 다음 다음 6, 7, 9가있을 수 있습니다. 또는, 우리는 7, 다음, 다음, 9 6 3 할 수 있습니다. 또는, 우리는 9, 다음, 다음, 6 7 3 할 수 있습니다. 또는, 3, 7 - 실제로 더, 우리는 더 이상 7하지 않을 수 없습니다. 그분은 우리의 하나입니다. 우리는 9 할 수 있으며, 다음 9 우리는 7 다음 6 할 수 있습니다. 또는, 우리는 그 다음에, 7 9 3 할 후 6 할 수 있습니다. 

여기에 사용자의 관심을 끌기 위해 한가지입니다 이 나무가 좀 이상한 모양의 것을. 특히, 경우에 우리는 오른쪽에있는 4 나무를 봐 - 여기, 그들에게 돌아갈 게 - 이 나무는 연결리스트처럼 거의 봐. 각 노드는 하나의 자녀가 그래서 우리는 예를 들어, 우리가 보는이 나무와 같은 구조를가 없습니다  하단 왼쪽에 이쪽 건 외로운 나무 인치 이 나무는 실제로 이진 트리를 타락한라고합니다 우리는 앞으로이 더 많은 얘기하자 - 당신은 다른 컴퓨터 과학 과정을로 이동 특히. 이 나무 타락한입니다. 사실은,이 구조가 자체적으로 있기 때문에 매우 유용하지  연결리스트의와 비슷한 시간을 조회합니다. 우리는 여분의 메모리 활용하기 위해 못 -이 추가 포인터를 - 때문에 우리의 구조 이런 식으로 나쁜 것. 에 가서 루트에 9를 가지고있는 이진 나무를 끌어보다는하면, 우리가해야 할 것이 마지막 경우는, 그입니다 우리는이 다른 용어에 대해 조금 이야기하는이 시점에서, 대신이야 높이라고 나무에 대해 얘기 할 때 우리는 사용하는. 

나무의 높이는, 루트에서 가장 멀리 떨어져있는 노드의 거리입니다 나보다 당신이하기 위해에 확인해야하는 홉의 수 루트에서 시작하여 다음 트리에서 가장 먼 노드에 도착. 우리는 여기에 그려진 한이 나무의 일부에서, 보면 우리는 3에서 우리는 왼쪽 상단 모서리에있는이 나무를 타고 있다면 우리가 시작할 것을 알 수 있습니다 그런 다음 1 홉 (Hop) 6로 이동하려면 7까지가는 ​​두 번째 홉을해야 세 번째 홉 (Hop)는 9 져요. 그래서,이 나무의 높이는 3. 우리는이 녹색으로 설명 된 다른 나무에 대해 동일한 운동을 할 수 우리는이 나무의 높이가 실제로도 3 것을 볼 수 있습니다. 그렇다고 그들이 타락한 만드는 부분이에요 - 자신의 높이는 전체 트리의 노드 수보다 하나 적은 것을. 우리는 반면에 빨간색으로 둘러 쌓여 야이 다른 나무에서 보면 우리는 가장 멀리 떨어져있는 잎 노드는 6 9이 있다는 것을 알 - 자식이없는 그 노드되고 출발합니다. 그래서, 루트 노드에서 6 9 중까지하기 위해서는하면, 우리는 7까지 한 홉을해야하고 9 얻는 두 번째 홉 와 마찬가지로, 7에서 두 번째 홉 (Hop)는 6 져요. 그럼, 여기이 나무의 높이 만 2입니다. 당신은 돌아 가야 우리가 이전에 논의 된 다른 나무의 모든 것 할 수 7 6로 시작, 그리고 당신은 그 나무의 높이도 2 점입니다. 

우리가 얘기 한 이유는 이진 나무를 주문 당신이에서를 검색 할 수 있습니다 때문 왜이 멋지다고 것은 정렬 배열을 통해 검색에 매우 유사한 방법입니다. 이것은 우리가 그 개선 조회 시간을 받고 대해 이야기 곳 간단한 연결리스트여. 연결된 목록과 - 당신이 특정 요소를 찾으려면 - 당신은 최고의 선형 검색 어떤 종류의 일을 할거야에 있어요 당신은 목록과 홉 하나 하나의 시작 부분에서 시작 위치 - 한 노드로 하나의 노드 - 당신이 검색하는 무엇이든 찾을 때까지 전체 목록을. ,이 좋은 형식으로 저장된 이진 트리를 가지고 있다면, 반면에 당신은 실제로 무슨 이진 검색의 더 많은 정보를 얻을 수 있습니다 당신은 분할 및 정복 곳 각 단계에서 트리의 적절한 이분의 일을 통해 검색 할 수 있습니다. 씨가 어떻게 작동 보자. 

우리가이있을 경우 - 다시, 우리의 원래의 나무로 돌아 간다 - 우리는 오른쪽에, 우리는 왼쪽에서 3가, 7시 9 시작 그리고 3 아래 우리는 6 있습니다. 우리가이 나무에서 번호 6을 검색하려는 경우, 우리는 루트에서 시작 할. 우리는 6을 말하면, 원하는 값을 비교 것 현재 7,보고있는 노드에 저장되어있는 값으로, 6 실제로 미만 7, 그래서 우리가 왼쪽으로 이동하려는 것을 알게됩니다. 6의 값이 7보다 큰 였다면, 우리는 대신 오른쪽으로 이동 한 것입니다. 우리가 아는부터 그 - 우리의 주문 이진 트리의 구조로 인해 - 7보다 적은 값의 모든 7의 왼쪽에있는 저장 될 거에요 심지어 나무의 오른쪽을 통해 찾아 보지 않고도 할 필요가 없습니다. , 일단 우리가 왼쪽으로 이동하고 3를 포함하는 노드에서 지금이야 우리가 3 6을 비교 어디에서 우리는 다시 같은 비교 작업을 수행 할 수 있습니다. 3보다 큰 - 우리가 찾고있는 값을 - 그리고 우리는 동안 6 발견 우리는 3가 포함 된 노드의 오른쪽으로 이동 할 수 있습니다. 그럴 왼쪽이 여기 없기 때문에 우리가 그걸 무시할 수 있습니다. 그러나 우리는, 우리는 나무 자체를보고 있기 때문에 알고 우리는 나무가 자식이없는 것을 볼 수 있습니다. 

그것은 우리가 인간으로 스스로를 수행하는 경우이 나무에 6 찾아도 매우 간단합니다 하지만 거죠가 컴퓨터처럼 기계적으로이 과정을 수행하게 정말 알고리즘을 이해합니다. 이 시점에서, 우리는 지금 6를 포함하는 노드보고 우리는,이 값 6을 찾고 그래서, 실제로, 우리는 해당 노드를 발견했습니다. 우리는 나무의 값 6 찾았는데, 우리는 검색을 중지 할 수 있습니다. 이 시점에서, 무슨 일이 일어나고 있는지에 따라 우리가 말할 수, 그래, 우리가 값을 6 발견, 우리의 나무에 존재합니다. 우리가 뭔가 노드를 삽입하거나 할 계획이 없으면, 우리는이 시점에서 그 작업을 수행 할 수 있습니다. 

얼마나이 작품을 볼 몇 가지 더 조회를 수행하자. 의 우리가 시도하고 값을 10 조회 할 경우 어떻게 살펴 보도록하겠습니다. 우리가 값을 10 조회 할 경우, 우리는 루트에서 시작합니다. 우리는 10 7보다 큰 것을 볼 줄, 우리는 오른쪽으로 옮겨야 겠어요. 우리는 9하고 10 ~ 9 비교하고 9 실제로 10 개 미만입니다 볼 줄. 그럼 다시, 우리는 오른쪽으로 이동하려고 할. 그러나이 시점에서, 우리는 우리가 널 노드에 걸 눈치 채 셨을 거에요. 거기 엔 아무 것도 없어요. 10이 있어야 할 건 없어요. 나무에 열이 실제로 없다는 것을 - 우리가 실패를보고 할 수있는 곳입니다. 그리고 마지막으로, 어디 우리가 나무에 1을 찾아하려는 경우를 통해 가자. 이것은 우리가 10을 보면 어떤 대신 오른쪽으로가는 경우를 제외하고, 무슨 일이 비슷합니다 우리는 왼쪽으로 갈거야. 우리는 7시에 시작하고 1 7보다 적은 것을 알, 우리는 왼쪽으로 이동합니다. 우리는 3하고 1 3보다 적은 것을 알, 그래서 우리는 왼쪽으로 이동하려고합니다. 이 시점에서 우리가 널 노드를 가지고, 그래서 우리는 실패를보고 할 수 있습니다. 

당신은 이진 나무에 대한 자세한 내용을 보려면 원하는 경우 당신이 그들과 함께 할 수있는 재미 작은 문제의 모든 무리가 있습니다. 나는이 도표 하나 하나의 그림을 연습하는 것이 좋습니다 하고, 다른 모든 단계에 따라 이 슈퍼 - 유용하기 때문 당신은 허프만 인코딩 문제 세트를하는 일이 아니요 경우에만 뿐만 아니라, 향후 과정에 - 단지 이러한 데이터 구조를 이끌어 문제를 통해 생각하는 방법을 학습 로 펜과 종이, 또는이 경우에는 아이 패드와 스타일러스. 

하지만이 시점에서, 우리는 몇 가지 코딩 연습을 수행하는 이동 할거야 실제로 이러한 이진 나무 놀이를 참조하십시오. 나는 내 컴퓨터에 다시 전환하는거야. 대신 CS50 실행 또는 CS50 스페이스를 사용하는 섹션의 일부를 들어, 나는 어플라이언스를 사용할거야. 

문제 세트 사양과 함께 후, 내가이 어플라이언스를 엽니 다한다는보고 내 보관 폴더로 이동, 제 7이라는 폴더를 만듭니다 그리고 binary_tree.c라는 파일을 만듭니다. 여기 우리는 간다. 나는 어플라이언스가 이미 열려있어. 나는 터미널을 뽑아거야. 제가 보관 폴더로 갈거야 section7라는 디렉토리를 만들고 하고 완전히 비어를 참조하십시오. 지금은 binary_tree.c을 열어거야. 좋아. 간다 - 빈 파일을. 

의이 사양으로 돌아 가자. 사양은 새로운 유형 정의를 작성하기를 부탁합니다 INT 값을 포함하는 이진 트리 노드에 대해 - 우리가 우리의 이전 다이어그램에서 그린 값처럼. 우리는 여기에 수행 한이 틀에 박힌는 typedef 사용하는 것 당신은 문제 세트 5에서 인식해야하는 - 당신은 정복 도전자 프로그램의 해시 테이블 방법을 알았다면. 당신은 또한 지난주 섹션에서 인식해야한다 우리는 연결리스트에 대해 얘기 곳. 우리는 구조체 노드의 typedef있어 우리는이 구조체 노드에게 사전에 구조체 노드의 이름을 제공 한 우리가 구조체 노드 포인터를 갖고 싶어하므로 우리는 다음 참조 할 수 있도록 우리 구조체의 일환으로, 우리는 다음이를 둘러싸고 한 - 또는 오히려,이 동봉 - typedef에 그래서 그게 나중에 코드에서, 우리는 대신 구조체 노드의 단 노드로이 구조체를 참조 할 수 있습니다. 

이것은 우리가 지난 주 본 단독으로 연결된 목록 정의와 매우 비슷 될 것입니다. 이 작업을 수행하려면, 그냥 반복을 작성하여 시작하자. 우리는 우리가 정수 값을 가져야 알고 그래서 우리는 int 값에 넣어하고 대신 다음 요소로 하나의 포인터를 갖는의 것 - 우리는 단독으로 연결된 목록과 함께했던 것처럼 - 우리는 왼쪽과 오른쪽 자식 포인터를 할 겁니다. 너무 꽤 간단 - 구조체 노드 * 왼쪽의 자녀, 그리고 구조체 노드 * 오른쪽 자식,. 좋아. 그거 아주 좋은 시작 것 같습니다. 의이 사양으로 돌아 가자. 

이제 우리는 트리의 루트에 대한 글로벌 노드 * 변수를 선언해야합니다. 우리는 또한 세계의 연결 목록의 맨 위에 포인터를 만들어처럼이 세계 만드는거야. 이건 정말 저게 우리가 작성하는 기능에 우리는이 루트 돌아 다닌다 유지 할 필요가 없습니다 - 우리는 당신이 경우는 재귀 적으로이 함수를 작성하려는 볼 수 있지만 그것은 처음에도 글로벌로 주위에 전달하지 더 나은 것 대신 기본 기능에 로컬를 초기화합니다. 그러나, 우리는 시작 전 세계적으로 할 수 있습니다. 다시 말하지만, 우리는 공간을 두어주지, 나는 노드 * 루트를 선언하는거야. 그냥 내가이 초기화되지 않은 두지 않도록하기 위해서, 제가 null로 동등한를 설정하는거야. 이제 main () 함수에 - 우리는 여기에 정말 신속하게 쓰​​겠 다되는 - INT 메인 (int는 argc, const 숯불 * 변수는 argv []) - 그리고 난 그냥 내가 아는 const로 내 argv 배열을 선언 시작 할거야 이러한 주장은 나는 아마도 수정하지 않으려는 인수 있다고. 내가 그들을 수정하려는 경우 아마 그 사본을해야합니다. 이 코드에서 많이 볼 수 있습니다. 괜찮아, 어느 방법입니다. 원하는 경우 const를 생략 - 그건로 떠나 괜찮아. 나는 일반적으로 내 자신을 생각 나게하는 너무 그것을 뒀을  아마 그 인자를 수정하는 건 아니다. 

늘 그랬듯이 주요 끝에 반환 0 행을 포함 할거야. 여기, 내 루트 노드를 초기화합니다. 지금 당장 의미하는 바와 같이, 전 null로 설정하는 포인터있어 그래서 아무 것도 눈치입니다. 위해 실제로 노드를 구축 시작 나는 먼저 메모리를 할당해야합니다. 나는 malloc를 사용하여 힙에 메모리를함으로써 그렇게 할거야. 나는 malloc의 결과와 동일한 루트를 설정하는거야 나는 노드의 크기를 계산하는 sizeof 연산자를 사용할거야. 반대로 I는 sizeof 노드를 사용하는 이유는, 말 malloc (4 + 4 +4) 또는 malloc 12 -이 이런 일을한다는 것은 - 내 코드는 최대한 호환되도록 싶어서입니다. 내가이. C 파일을 취할 수 있도록하려면, 기기에 컴파일 그리고 내 64 비트 Mac에서 그것을 컴파일 - 또는 완전히 다른 아키텍처에 - 그리고이 모두가 같은 일을하고 싶습니다. 

나는 변수의 크기 가정을한다면 ... - 정수 또는 포인터의 크기의 크기 - 그리고 나는 또한 아키텍처의 종류에 대해 가정을 만들고 있어요 실행할 때하는 내 코드를 성공적으로 컴파일 할 수 있습니다. 수동 구조체 필드를 합계는 반대로 항상 sizeof를 사용합니다. 다른 이유는 컴파일러가 구조체에두고있는 패딩있을 수 있다는 점입니다. 그저 각 필드를 합계하면, 당신이 일반적으로 원하는 것이 아닙니다 그래서 그 줄을 삭제합니다. 이제, 정말,이 루트 노드를 초기화 나는 그것의 다른 영역에서의 각 값에 연결해야 겠어. 예를 들어, 값에 대해 내가 7 초기화하고 싶어한다는 걸 알아, 그리고 지금 나는 왼쪽 아이가 널 (null)로 설정하는거야 하고 오른쪽 어린이는 null 일 수 있습니다. 좋아요! 우리는 사양의 일부를 했어. 

3 페이지의 하단에있는 사양 다운 더 3 개의 노드를 작성하라고 요청 - 9 3, 6를 포함하는 하나 하나를 포함하는 하나 - 그리고 그래서 정확히 우리 나무 다이어그램 모양 올려 송금 우리는 이전에 말한. 하자 여기 아주 빨리. 당신은 내가 중복 코드의 무리를 작성할 할테니까 정말 빠르게 볼 수 있습니다. 나는 노드 *을 만들거야 그리고 난가 3 전화 할께. 나는 malloc (sizeof (노드))에이 같은 설정을거야. 난 세 -> 가치를 = 3을 설정하는거야. 세 -> left_child = NULL, 3 -> 오른쪽 _child = NULL;뿐만 아니라. 그 뿌리를 초기화 꽤 유사하고, 그게 정확히 무슨입니다 나는뿐만 아니라 6, 9를 초기화 시작하면해야 겠어. 정말 빨리 그렇게한다는거야 - 사실, 조금 복사 및 붙여 넣기 작업을 수행 할 거예요, 괜찮아 - 그 확신합니다.  지금, 내가 복사 잖아? 내가 가서 6이 동일을 설정할 수 있습니다. 당신이 잠시 소요 수퍼 효율적이지 않습니다 것을 볼 수 있습니다. 조금에서, 우리는 우리를 위해이 작업을 수행하는 함수를 작성합니다. 전 9로이를 교체 할 6 랑을 대체합니다. 

이제 우리는 우리의 모든 노드 생성하고 초기화있어. 우리는 우리의 루트는 7과 동일하고 있다고, 또는 값 7을 포함 한 3 포함의 노드, 9를 포함하는 6를 포함하는 우리의 노드와 노드. 이 시점에서 우리가해야 할 일은 최대 와이어 모든 것입니다. 나는 null로 모든 포인터를 초기화하는 이유는 확신하는 확인 너무나 것입니다 내가 실수로 거기에 아무 초기화되지 않은 포인터가 없습니다. 또한 이후,이 시점에서, 나는 실제로 서로 노드를 연결해야합니다 - 그들이 실제로 연결하고있는 이들에게 - 난을 통해 가서 할 필요가 없습니다 모든 nulls가 적절한 장소에가에 있는지 확인합니다. 

루트에서 시작하여, 내가 루트의 왼쪽 아이가 셋 것을 알고있다. 나는 루트의 오른쪽 아이는 9입니다 알아요. 그 후, 내가 걱정 남아있는 유일한 다른 하위 6이다 3의 오른쪽 자식입니다. 이 시점에서, 모든 아주 잘 보입니다. 우리는이 라인 중 일부를 삭제합니다. 지금은 모든게 잘 보입니다. 이 우리의 사양에 가서 우리가 다음 할 일을 보자. 

이 시점에서, 우리는라는 함수가 '포함'작성해야 'BOOL 포함되어 있습니다 (int 값)'의 프로토 타입이 있습니다. 그리고이 함수가 TRUE를 반환 것입니다 포함되어 있습니다  나무는 우리의 글로벌 루트 변수에 의해을 지적하는 경우  기능과 허위 기타에 전달 된 값이 포함되어 있습니다. 가 가서 그런 짓을 보자. 지금이 바로 우리가 조금 전에 아이 패드에 손으로 한 것을 조회처럼 될 것입니다. 하자 약간은 다시 확대 위로 스크롤합니다. 우리가 바로 우리의 주요 기능 이상이 기능을 넣어 것 수 있도록 우리는 프로토 타입의 어떤 종류를 할 필요가 없습니다. 그래서, BOOL은 (int 값)이 포함되어 있습니다. 우리는 간다. 우리 상용구 선언이 있어요. 그냥,이 컴파일됩니다 확인하기 위해서 나는 가서 그냥 거짓 돌아 평등을 설정하는거야. 지금이 함수는 아무 짓도하지 않으며 항상보고 우리가 찾고있는 값은 트리에 없습니다. 

이 시점에서, 아마 좋은 생각입니다 - 우리는 코드를 많이 작성했고 우리는 아직 테스트를 시도하지 않은 이후로 - 이 모든 컴파일되었는지 확인합니다. 우리가이 실제로 컴파일 될 수 있도록해야 할 것이 몇 가지가 있습니다. 우리가 아직 포함되지 않은 모든 라이브러리의 모든 기능을 사용하고하면 먼저 참조하십시오. 우리가 지금까지 사용한 기능은, malloc 아르 그리고 우리는 또한이 유형을 사용하고 - 'bool'이라는 비표준 형식을 - 어떤는 표준 BOOL 헤더 파일에 포함되어 있습니다. 우리는 확실히 BOOL 유형에 대한 표준 bool.h를 포함 할 우리는 또한 # 표준 라이브러리에 대한 표준 lib.h을 포함 할 그 malloc, 무료, 그 모두 포함되어 있습니다. 그래서, 축소, 우리는 그만 둘거야. 그러자이 실제로 컴파일 짓을했는지 확인하자. 우리는 않는 것을 볼, 우리는 오른쪽 궤도에있어. 

의 다시 binary_tree.c을 열어 보자. 이 컴파일됩니다. 가 내려 가서 우리가 포함 기능에 몇 가지 호출을 삽입되었는지 확인하자 - 그 모든게 잘하고 잘 있는지 확인합니다. 예를 들어, 우리가 이전의 트리에서 일부 조회를 한 때 우리는 값 6, 10, 1을 조회하려고, 우리는 6 트리에 있던 것을 알고 10 트리에 있지 였고, 1 중 나무가 아니 었습니다. 가 알아내는 방법으로 이러한 샘플 호출을 사용하자 여부 우리가 포함되어 기능이 작동합니다. 그렇게하기 위해, 난 printf 함수를 사용 거예요 우리는이 포함 할 수있는 호출의 결과를 인쇄거야. 나는 문자열에 넣어거야 "를 포함하는 (% d 개) = because  우리는 우리가 보는거야하는 값에 플러그에가는거야, 와 = % s의 \ N "과 그렇게 사용의 형식 문자열로. 그대로 화면에 출력 - 우린 그냥 보러가요 - 어떻게 함수 호출 것 같습니다. 이 실제로 함수 호출되지 않습니다.  이건 그냥 함수 호출처럼 보이도록 디자인 된 문자열입니다. 

이제, 우리는 값에 연결하려고하고 있습니다. 우리는 6이 포함되어 해 볼거야 그리고 우리가 어떻게 할 거냐는 3 원 연산자를 사용합니다. 6이 포함 - - 저 볼 수 있도록, 지금은 6 포함 한 6이 포함되어있는 경우는 사실입니다, 우리가 % s의 형식 문자로 보낼 것처럼 문자열 문자열 "사실"가 될 것입니다. 하자 조금 위에 스크롤됩니다. 그렇지 않으면, 우리는 거짓 여섯 반품이 포함되어있는 경우 문자열은 "false"를 보내려고합니다. 이 약간 정신 이상자 모양이지만, 나는뿐만 아니라 설명 할 수 파악 어떤 3 중 연산자는 우리가 한동안 못 봤어요부터 것 같습니다. 이것은 우리가 포함되어 기능이 제대로 작동하는지 파악 할 수있는 좋은, 편리한 방법이 될 것입니다. 나는 왼쪽에 다시 스크롤거야 나는 몇 번 복사하고이 줄을 붙여 넣 겠어. 그것은 약이 값의 일부를 변경 그래서이 1이 될 것입니다,이 10가 될 것입니다. 

이 시점에서 우리는 멋진 기능이 포함되어있어. 우리는 몇 가지 검사가 있는데, 만약이 모든 작품을 우리는 볼 수 있습니다. 이 시점에서 우리는 좀 더 코드를 작성했습니다. 아웃 종료하고 모든 여전히 컴파일되었는지 확인 할 시간. 아웃 종료하고 지금의 다시 이진 트리를 만들어 봅시다. 우리가 오류가 생긴 것 뭐, 눈에 보이는 우리는이 명시 적으로 printf 라이브러리 함수를 선언있어. 우리가 가서 # standardio.h을 포함시킬 필요가있는 것 같습니다. 그리고 그와 함께, 모든 컴파일해야합니다. 우리 모두 됐어요. 지금의 이진 트리를 실행하고 어떻게 보자. 여기. / binary_tree, 아르 우리는 우리가 예상 한대로, 알 - 우리가 구현되지 않았기 때문에, 아직이 포함되어 또는 오히려, 우리가 FALSE 리턴에 넣어어요 - 우리는 그냥 모두에 대해 잘못된 반환 있다고 볼 수 그래서 모든 꽤 잘 대부분의 일. 

의이 시점에서 포함 된 뒤로 가서 실제로 구현 보자. 나는 아래로 스크롤 확대 가야겠다 - 기억, 우리가 사용하는 알고리즘은 우리가 루트 노드에서 시작 였죠 그리고 우리가 발생하는 각 노드에서, 우리는 비교를 할 그 비교를 기반으로 우리는 하나 왼쪽 자녀 또는 오른쪽 자녀로 이동합니다. 이것은 우리가 이전 기간에 쓴 이진 검색 코드와 매우 유사 예정이다. 우리가 시작하면, 우리는 우리가 현재 노드에 개최 싶어하는지 알 우리는보고하고 있으며, 현재 노드가 루트 노드로 초기화 될 것입니다. 그리고 지금, 우리는 나무를 계속 할거야 우리의 정지 상태 그 기억 -  우리는 실제로 손으로 예를 통해 일할 때 - 우리가 널 노드가 발생했습니다였다 하지 우리가 null이 아이를 바라 보았다 때, 오히려 우리가 나무에서 노드로 이동하면 우리가 널 노드에와있는 것으로 나타났습니다. 현재는 null로 같지 않음 때까지 우리는 반복거야. 그리고 우리가 어떻게 할 거예요? 우리는 테스트하려는 경우 (현재 -> 값 == 값), 그때 우리가 실제로 우리가 찾고있는 노드를 발견 한 알. 그래서 여기, 우리는 TRUE를 반환 할 수 있습니다. 그렇지 않으면, 우리는 값이 값보다 작 여부를 확인하고 싶습니다. 현재 노드의 값이 값보다 작 으면 우리는 찾고 우리는 오른쪽으로 이동거야. 그래서, 현재는 = 현재 -> right_child, 그렇지 않으면, 우리는 왼쪽으로 이동거야. 현재 = 현재 -> left_child,. 아주 간단합니다. 

당신은 아마에서 매우 유사 루프를 인식 이전 용어의 이진 검색 다음을 제외하고 우리는 낮은, 중간, 높은 처리되었습니다. 여기, 우리는 단지 현재 값을 볼 수 있습니다 그래서 좋은하고 간단합니다. 자,이 코드가 작동하는지 확인하십시오. 첫째, 컴파일해야합니다. 그러길 것 같습니다. 한번 실행 해 보자. 그리고 사실, 우리가 기대하는 모든 출력합니다. 10 트리하지 않기는 트리에서 6 발견, 10를 찾을 수 없습니다 1 나무로도하지 않기 있으며 1을 (를) 찾을 수 없습니다. 멋진 물건. 

좋아. 이 우리의 사양에 가서 다음에 일어날 일들을 보자. 이제 우리 나무에 좀 더 노드를 추가하려고합니다. 은 5, 2, 8을 추가하고 코드가 포함되어 있는지 확인하고 싶어 여전히 예상대로 작동합니다. 자, 그렇게 이동합니다. 이 시점에서, 오히려 다시 성가신 복사 및 붙여 넣기하고보다 의 실제 노드를 생성하는 함수를 작성하게. 우리가 메인에 모든 방법을 아래로 스크롤하면, 우리는이 일을 해왔 것을 볼 우리가 노드를 만들 때마다 반복과 매우 유사 코드입니다. 

의 실제로 우리 노드를 구축하고 반환합니다 함수를 작성하자. 나는 build_node 부를께요. 나는 특정 값을 가진 노드를 만들거야. 여기에 확대합니다. 제가 제일 먼저 할 것은 실제로 힙에있는 노드에 대한 공간을 만들 수 있습니다. 그래서, 노드 * N = malloc (sizeof (노드)), N -> 값 = 값; 그리고 여기, 난 그냥 적절한 값으로 모든 필드를 초기화거야. 그리고 맨 끝에서, 우리는 노드를 반환합니다. 좋아. 한가지 유의할 사항은이 기능을 맞아 여기 힙 - 할당 된 메모리에 대한 포인터를 반환 예정이다. 이게 무슨 좋은 것은 이제이 노드입니다 - 우리는 경우 우리가 스택에 선언하기 때문에 힙에 선언해야 우리는이 같은이 기능에 할 수 없을 것입니다. 그 메모리 범위를 벗어나 것 우리가 나중에에 액세스하려고하면 잘못된 것입니다. 우리는 힙 - 할당 된 메모리를 선언되기 때문에, 우리는 나중에 자유롭게 처리해야 할 거예요 우리의 프로그램에 대한 모든 메모리를 누출하지. 우리는 코드에서 다른 모든 것을 거기에 punting 있었어요 그냥 시간에 단순화하기 위해, 하지만 이런 모양의 함수를 작성하는 경우 당신이 가진 곳 - 일부는 내부 malloc이나 realloc 호출 - 당신은, 당신이하는 말 여기에 댓글 일종의을 넣어 있는지 확인하려면 이봐, 당신도 알다시피, 전달 된 값으로 초기화 힙 - 할당 된 노드를 반환합니다. 그리고 당신은 말한다 노트 일종의에 넣어 있는지 확인하려면 호출자는 반환 된 메모리를 확보해야합니다. 그 방법은, 누군가가 어느 들어가서 경우, 그 함수를 사용하여 그들은 그 함수에서 다시 무엇이든 알고 어느 시점에서 해제해야합니다. 

모든 여기서 잘하고 좋은 것을 가정 우리는 우리의 코드에 내려 가서 여기있는 줄을 모두 교체 할 수 있습니다 우리의 빌드 노드 기능을 호출. 씨가 정말 빠르게 보자. 우리가 대체 할 수 없어하는 한 부분은 여기이 부분이 우리가 실제로 서로를 가리 키도록 노드를 송금 하단에있는, 그 때문에 우리는 우리의 기능에 할 수 없습니다. 그러나합시다 할 루트 = build_node (7), 노드 * 세 = build_node (3); 노드 * 여섯 = build_node (6), 노드 * 구 = build_node (9);. 이제, 우리는 또한에 노드를 추가하고 싶어 - 노드 * 오 = build_node (5), 노드 * 팔 = build_node (8); 와 다른 노드는 무엇 이었습니까? 여기 보자. 우리는 또한 2를 추가하고 싶어 - 노드 * 두 사람은 = build_node (2);. 좋아. 이 시점에서, 우리는 7, 3, 9, 6이있어 알고 모든 적절한까지 유선,하지만 5, 8, 2에 대해? 적절한 순서로 모든 것을 유지하기 위해, 우리 세의 오른쪽 아이는 6 것을 알고있다. 그래서, 우리는 5를 추가하는 거라면, 5 또한, 3 루트 인 나무의 오른쪽에 속해 그래서 5 6 왼쪽 자식으로 포함되어 있습니다. 우리는 여섯 말하여이 작업을 수행 할 수 있습니다 -> left_child = 오; ;> left_child = 팔 - 후 8 9 명, 9의 왼쪽 자식으로 속 그리고 2 세의 왼쪽 자식, 그래서 우리가 여기 할 수 - 그대를 -> left_child = 2;. 당신이 꽤 많이와 함께 수행하지 않은 경우, 당신은 자신을 오래 끌어 좋습니다. 

좋아. 의이 저장 보자. 가자, 나가서는 컴파일해야합니다 그리고 우리는 우리가 포함되어 통화에 추가 할 수 있습니다. 모든 여전히 컴파일 것 같습니다. 가에 가서 전화를 포함하고에 추가 할 수 있습니다. 다시, 나는 복사 및 붙여 넣기 약간을 할거야. 자, 가자 5 8, 2,을 검색합니다. 좋아. 자,이 모든 상태 양호 있는지 확인하십시오. 좋아요! 저장하고 종료합니다. 이제 컴파일, 어디 하세, 그리고 지금의이 실행할 수 있습니다. 모든 것이 잘 잘 작동과 같은 결과에서, 그것은 보인다. 좋아요! 이제 우리는 우리의가 포함되어 작성 제대로 작동있어. 하자에 이동하고 트리에 노드를 삽입하는 방법에 대한 작업을 시작 우리가 지금하고 있어요로부터 일이 아주 예쁜하지 않습니다. 

우리는 사양으로 돌아 가면하면, BOOL을 반환, 다시 -이 삽입라는 함수를 작성하는 데를 부탁합니다 여부에 대해 우리가 나무에 노드를 삽입 할 수 - 다음 트리에 삽입 할 값은 다음과 같이 지정됩니다 우리의 삽입 기능에 유일한 인수입니다. 우리가 실제로 트리에 노드가 포함 된 값을 삽입 할 수 있다면 우리는 TRUE를 반환한다 이는, 우리, 하나, 충분한 메모리를 가지고 있다는 것을 의미 그리고 두 노드는 이미 이후 트리에 존재하지 않았어 - 기억, 우리가 일을 간단하게하기 위해 나무에서 중복 된 값을 가지고하지 않을 수 있습니다. 좋아. 코드를 백업합니다. 그걸 엽니 다. 조금 확대 한 다음 아래로 스크롤합니다. 가 바로이 포함되어 위의 삽입 기능을 넣어 보자. 다시, 그것은 (int 값) BOOL 삽입 호출 할거야. 기본적으로 다음 조금 더 많은 공간을 지정하고, 가 매우 끝 부분에 false를 반환에 넣어 보자. 당장 하단에있는, 어디 앞서 대신 수동으로 노드를 구축 가자 메인에 자신과 배선 올려 우리가하는 것처럼 서로를 가리 키도록, 우리는 그 작업을 수행하기 위해 삽입 기능에 의존합니다. 우리는 아직 처음부터 전체 트리를 구축하기 위해 삽입 기능에 의존하지 않습니다 오히려 우리는이 라인을 제거하는거야 - 꼭이 줄 주석 - 그 노드 5, 8, 2을 구축 할 수 있습니다. 그리고 대신에, 우리는 삽입 함수 호출을 삽입합니다 실제로 작동하는지 확인합니다. 여기 우리는 간다. 

이제 우리는이 라인을 주석했습니다. 우리는이 시점에서 우리 트리에서 7, 3, 9, 6을 갖추고 있습니다. 이 모든 작동하는지 확인하려면, 우리는 우리의 이진 트리를 확인 축소 할 수 있습니다 을 실행하고, 우리는 이제 우리가 완전히 맞아, 우리에게 말하고 포함 볼 수 있습니다 - 5 8, 2,은 나무에 더 이상 없습니다. 코드로 다시 가서, 와 어떻게 삽입하는거야? 우리가 실제로 이전에, 8, 2 5 삽입 때 우리가 무슨 짓을했는지 기억하십시오. 우리는 루트에서 시작 위치를 우리는 그 Plinko 게임을 재생 하나 하나 나무 하나를 추락 우리는 적절한 빈틈을 발견 할 때까지, 그리고 우리는 원하는 지점에있는 노드에 유선. 우리는 같은 일을 할 겁니다. 본 문서의 시작 부분에 우리가 사용하는 코드를 작성하는 것처럼 기본적으로하면 함수를 포함 노드가 있어야합니다 장소를 찾으려면, 그리고 우리는 바로 노드를 삽입하는거야. 하자있는 일을 시작합니다. 

그래서 우리는 노드 * 현재 = 루트가, 우리는이 코드가 포함되어 따릅 우리는 매우 우리 작동하지 않는 것을 발견했습니다 때까지. 현재 요소가 null이 아닙니다 동안 우리는 나무를 가서, 우리가 발견하면 그 이전의 값이 우리가 삽입 할 노력하는 값이 같다 - 잘, 우리가 실제로 노드를 삽입 할 수 없습니다있는 사건 중 하나입니다 나무로이 우리가 중복 된 값을 의미 때문입니다. 여기, 우리가 실제로 False를 반환거야. 이제 현재의 값은 값보다 작 다른 경우 이제 우리는 오른쪽으로 이동 알고  값은 현재 트리의 오른쪽 절반에 속해 때문입니다. 그렇지 않으면, 우리는 왼쪽으로 이동거야. 그래서 기본적으로 우리가 포함되어 거기 기능입니다. 

이 시점에서, 우리는이 동안 루프를 완료 한 우리의 현재 포인터는 null로 지목 될 것입니다 기능은 이미 반환하지 않은 경우. 우리가 새 노드를 삽입 할 위치를 따라서 우리는 그 자리에서 현재 발생하고 있습니다. 어떤 남았 것은 실제로 새 노드를 구축하는 것입니다 있는 우리는 아주 쉽게 할 수 있습니다. 우리는 우리의 슈퍼 - 편리한 빌드 노드 기능을 사용할 수 있습니다 우리가 이전에하지 않은 뭔가를 - 우리가 가지 당연한 줬는데 지금 우리는되도록 도와 드리겠습니다 - 우리는 새로운 노드에 의해 반환 된 값이 사실은 있는지 테스트합니다 null이 아닌 우리가이 null 인 경우 해당 메모리를 액세스 할 싶지 않아요 때문입니다. 우리는 새로운 노드가 null이 동일하지 있는지 확인 테스트 할 수 있습니다. 실제로 널 (null) 인 경우 또는 대신에, 우리는 볼 수 있습니다 가 널 (null)이되면, 우리는 초기 false를 반환 할 수 있습니다. 

이 시점에서, 우리는 나무에서의 적절한 장소에 새로운 노드를 송금 할 수 있습니다. 우리가 주를 다시 확인하고있는 경우는, 이전에 실제로 값에 배선을했다 우리는 우리가하고 있던 방법은 우리가 트리에서 3 넣어 싶었을 때 알 우리는 루트의 왼쪽 자녀를 액세스했습니다. 우리가 나무 9 넣을 때, 우리는 루트의 오른쪽에 아이를 액세스 할 수있었습니다. 우리는 나무에 새로운 값을 넣어하기 위해 부모에 대한 포인터를 가지고 있었다. 삽입 백업 스크롤, 여기서 그런 잘 작동하지 않을거야 우리는 부모 포인터가 없기 때문에. 우리가 할 수 있기를 원하는 것은이 시점에서입니다 부모의 가치를 확인하고 볼 - 어이쿠, 부모의 값이 현재 값보다 작다면, 다음 부모의 권리 자녀가 새 노드이어야합니다; 그렇지 않으면, 부모의 왼쪽 아이가 새 노드해야합니다. 그러나, 우리는 아직이 부모 포인터가 없습니다. 

우리가 나무 통과로 얻으려면, 우리는 실제로 추적 할거야 그리고 위의 루프에서 해당 장소를 찾으십시오. 우리는 우리의 삽입 함수의 상단에 다시 스크롤하여 그렇게 할 수 다른 포인터 변수를 추적하면 부모했다. 우리는 처음에 null로 동등한를 설정하는 것 그리고 때마다 우리는 나무 통과 우리는 현재의 포인터를 일치하도록 부모 포인터를 설정하는거야. 현재와​​ 같은 부모를 설정합니다. 이 방법, 우리가 통과 할 때마다, 우리는 현재의 포인터가 있는게 증가되도록 할거야 부모 포인터는 다음에 - 트리에서 현재 포인터보다 한 단계 높다. 그게 다 잘 보입니다. 

난 우리가 조정하는 것이 좋습니다 수있는 유일한 일이이 노드 반환 null을 구축이라고 생각합니다. 실제로 성공적으로 null을 반환하는 노드를 구축 얻을하기 위해하는 것은 우리는 그 코드를 수정해야합니다 여기에 있기 때문에, 우리는 malloc가 유효한 포인터를 반환 있는지 테스트하지 마십시오. 그래서, (n은 = NULL!) 다음 - malloc은 유효한 포인터를 반환하는 경우, 우리는 그것을 초기화됩니다; 그렇지 않으면, 우리는 돌아갈 겁니다 그리고 우리를 위해 null을 반환 끝장 날 것이다. 이제 아주 잘 보입니다. 의이 실제로 컴파일하고 있는지 확인할 수 있습니다. 이진 트리를 만들어, 아, 우리가 여기 일이 좀있어. 

우리는 함수의 암시 적 선언이 노드를 구축있어. 다시 말하지만,이 컴파일러와 함께, 우리는 상단에 시작할 거에요. 무슨 뜻합니다 건 사실을 선언했고 전에 노드를 구축 부르 겠어요 것입니다. 진짜로 빠르게 코드로 돌아가 보자. 아래로 스크롤하고, 확실히 충분히, 내 삽입 함수는 선언 빌드 노드 기능 이상 하지만 삽입물의 내부 노드를 구축 사용하는 중이 야. 나는 복사에 갈거야 - 그리고 상단에 여기까지 빌드 노드 기능 방식을 붙여 넣습니다. 그 방법은, 희망 그 작동합니다. 이 다른가요가 드릴께요. 이제 모든 컴파일됩니다. 모든 좋은 것입니다. 

그러나이 시점에서, 우리는 실제로 삽입 기능을 호출하지 않았습니다. 우리는 그냥 컴파일 알고 있으니,이에 가서 전화를 인치 놓고 우리 main () 함수에서 해당 작업을 수행하자. 여기, 우리는 5 8​​, 2,을 댓글을 달았습니다 그리고 우리는 아래 여기를 송금 없습니다. 의 일부 통화 삽입 할 수 있도록하자, 과의뿐만 아니라 우리가 사용하는 물건을 같은 종류를 사용하게 우리는 모든 것이 올바르게 삽입하기 않았는지 확인하려면 다음 printf 호출했을 때. 나는 복사 및 붙여 넣기거야 그리고 우리가 삽입 할 수있는 것 대신이 포함되어 있습니다. 그리고 대신에 6, 10, 1, 우리는 5 8​​, 2,를 사용하는거야. 이 희망 트리로 5 8, 2,를 삽입해야합니다. 컴파일합니다. 모든 좋은 것입니다. 이제 우리는 실제로 프로그램을 실행합니다. 

다 가짜 돌아 왔습니다. 그럼, 5, 8, 2 가지 않았어, 그리고이 포함되어 어느를 찾을 수 없습니다 것 같습니다. 무슨 일이야? 가 축소 보자. 첫 번째 문제는 삽입이 false 반환 듯 였어요 그리고 우리 반환 거짓 전화에 남아 때문이다처럼 보이지만, 우리는 실제로 진짜 돌아 오지 않을 꺼야. 우리는을 설정할 수 있습니다. 우리가 할 경우에도 두 번째 문제는, 지금은 -이 저장이를 종료 다시 make 명령을 실행, 그걸 실행 한 다음 컴파일했습니다 - 우리는 다른 무슨 일이 일어난 것을 볼 수 있습니다. 5, 8, 2는 아직 트리에서 발견되지 않았다. 그럼, 무슨 일이야? 

가 코드에서 살펴 보자. 우리가이 일을 알아낼 수 있는지 봅시다. 우리는 부모가 null 게 아니라 함께 시작합니다. 우리는 루트 포인터와 같은 현재의 포인터를 설정 우리는 나무를 통해 우리의 방법을 작동거야. 현재 노드가 null가 아닌 경우, 우리는 우리가 조금 아래로 이동 수 있다는 것을 알고. 우리는 현재의 포인터와 일치 우리의 부모 포인터를 설정 값을 확인 - 값이 동일한 경우는 true를 반환. 값이 덜 경우 우리는 오른쪽으로 이동, 그렇지 않으면, 우리는 왼쪽으로 이동합니다. 그럼 우리가 노드를 구축 할 수 있습니다. 조금 확대됩니다. 여기, 우리는 동일 값을 송금하려고 할거야. 무슨 일이야? 가능 Valgrind 우리에게 힌트를 줄 수 있는지 봅시다. 

정말 제가 정말 빠르게 실행 Valgrind Valgrind를 사용하려면 모든 메모리 오류가있는 경우와 당신을 알려줍니다. 우리는 코드에 Valgrind를 실행하면 당신이 볼 수 있듯이 오른쪽 here--Valgrind./binary_tree--and이 떨어질 입력합니다. 당신은 우리가 어떤 메모리 오류가 발생하지 않았다는 걸 알 때문에 모든 지금까지 괜찮아 것 같습니다. 우리가 않기 때문에 우리는 우리가 알고있는 일부 메모리 누수를, 있나 우리 노드 중 하나를 해방 벌어지고 있습니다. 의 실제로 무슨 일이 볼 수 GDB를 실행 해보자. 우리는 gdb를 할 수 있습니다. / binary_tree. 단지 벌금을 부팅. 의 삽입에 브레이크 포인트를 설정할 수 있습니다. 의 실행합시다. 우리가 실제로 삽입 전화가 안 것 같습니다. 문제가 그냥 메인에 여기까지 변경 때 였죠 것 같습니다 - 포함 된에서 이러한 printf 전화의 모든 - 사실은 삽입에 연락하려면 다음을 변경하지 마십시오. 이번에는 한번 해 줘. 가 컴파일한다. 모든이 좋아 보여요. 지금의이을 실행 해보자, 무슨 일이 참조하십시오. 좋아! 모든 자료가 아주 잘 보입니다. 

생각하는 마지막으로 한가지는, 본 삽입물에 대한 모든 가장자리 경우가 있습니다? 그리고 밝혀 항상 생각하는 재미 하나의 에지 경우, 음, 이며, 나무가이 비어있을 경우 어떤 일이 발생하고이 삽입 함수를 호출? 작동됩니까? 음, 그것을 시도 줘. - binary_tree 다. - 우리가이를 테스트 할 것으로는, 우리는, 우리의 주요 기능으로 가서는거야 그리고 오히려 같은 배선이 노드를보다 우리는, 전체 일을 주석 할거야 대신 노드 자신까지 배선, 우리는 실제로 가서이 모두 삭제할 수 있습니다. 우리는 모든 삽입하는 전화를 걸거야. 자, 어떻게 구 - 대신 5, 8, 2, 우리는 3, 7를 삽입, 9거야. 그리고 우리는 또한뿐만 아니라 6을 삽입 할 수 있습니다. 저장합니다. 종료합니다. 이진 트리를 확인하십시오. 다 컴파일합니다. 우리는 그냥, 그대로 실행하고 어떻게 볼 수 있습니다 하지만 또한 확인하기 위해 정말 중요한 될거야 우리는 모든 메모리 오류가 없습니다 이게 우리가 알고있는 우리의 에지 사례 중 하나이기 때문이다. 

가자, 이건 Valgrind 아래에 잘 작동하는지 확인 우리는 Valgrind. / binary_tree를 실행하여 할게요된다. 우리가 실제로 한 상황에서 하나의 오류를 가지고있는 것 같습니다 - 우리는이 분류 오류가 있습니다. 무슨 일이 있었죠? 그게 어디 Valgrind은 사실 우리에게 알려줍니다. 약간의 축소. 그게 우리의 삽입 기능에서 일어나고있는 것처럼 보이지만, 우리가 삽입시 크기를 4의 잘못된 읽기를 줄 60. 가 돌아가서 여기서 무슨 일이 벌어 보자. 정말 빠른 축소. 나는 우리가 모든 것을 볼 수 있도록이 화면의 가장자리로 이동하지 않도록하고 싶습니다. 잠시 후 그를 당겨. 좋아. 아래로 스크롤하고, 문제는 바로 여기에 있습니다. , 우리가 내려하면 어떻게 되나요 및 현재 노드가 이미 null입니다 우리가 맨 위에, 여기에서 찾아 볼 있으므로 경우, 부모 노드는 null입니다 - 이 동안 루프는 실제로 수행되지 않는 경우 현재 값은 널 (null)이기 때문에 - 현재이 null하도록 우리의 뿌리가 null입니다 - 그러면 우리 부모가, 현재 또는 유효한 값으로 설정되지 않을됩니다 따라서 부모는 null이됩니다. 우리는 확인하기 위해 기억해야 시간에 우리는 여기 내려와, 우리는 부모의 가치에 액세스 할 수 있습니다. 그래, 무슨 일이 벌어 질까요? 음, 경우 부모가 null입니다 - (상위 == NULL)하는 경우 - 다음에 우리가 알아 나무에 뭔가가 안됩니다. 우리는 루트에서를 삽입하려고합니다. 우리는 새로운 노드와 같은 루트를 설정하여 해당 작업을 수행 할 수 있습니다. 그런 다음이 시점에서, 우리는 실제로 다른 일을 통해 가고 싶지 않아. 대신, 여기, 우리는 다른 - 경우 - 다른 하나 할 수 또는 우리는 다른 여기 모든을 결합 할 수 그러나 여기서 우리는 다른 사용하여 그렇게 할 수 있습니다. 이제, 우리는 우리의 부모가 null이 아니라는 것을 확인하기 위해 테스트 할거야 그 전에 실제로 해당 필드를 액세스하려고. 이 우리가 세그먼트 오류를​​ 방지하는 데 도움이됩니다. 그럼, 우리가 포기, 축소 컴파일, 실행합니다. 

어떤 오류가 있지만, 우리는 여전히 메모리 누수의 무리가 없습니다 우리는 우리의 노드 중 하나를 확보하지 않았기 때문입니다. 우리가 여기에 올라 가서한다면, 우리는 우리의 출력 살펴 우리는 좋은입니다 사실 반환 된, 음, 우리 삽입의 모든 것 같군요 참조하십시오. 삽입은 모든 사실, 한 다음 해당이 포함되어 호출에도 마찬가지입니다. 

일을 잘 했어! 우리가 성공적으로 삽입을 작성한 것 같습니다. 우리가 이번 주 문제 세트 사양이 전부 야. 생각하는 하나의 재미 도전은 실제로에 갈거야 방법입니다 이 트리의 노드의 모든 무료입니다. 우리는, 그래서 다른 여러 가지 방법으로 할 수 있습니다 하지만, 실험 너에게 맡기 겠네 그리고 재미있는 도전으로 시도하고 확실 할 수 있는지 확인 이 Valgrind 보고서는 오류 및 누수도를 반환하지 않을 수 있습니다. 

행운을 빌어 이번 주 허프만 코딩 문제 세트에, 우리는 다음주에 뵐께요! [CS50.TV]