[Powered by Google Translate] 당신은 컴퓨터에 모든 가족을 어떻게 대표까요?
우리는 단순히 목록을 사용할 수
하지만 명확한 계층 구조가 있어요.
>> 자, 우리가 네 증조 할머니 앨리스로 시작하고 있다고 가정 해 보겠습니다.
그녀는 두 아들 밥이
할아버지와 찰리.
찰리는 3 명
삼촌이, 데이브, 이모, 이브, 그리고 아버지 프레드.
당신은 프레드의 유일한 아이입니다.
>> 왜 이런 방식으로 귀하의 가족을 조직 것
간단한 목록 표현보다 더 나은?
이유 중 하나는 그이 계층 구조,
라는 '나무'를 간단한 목록보다 더 많은 정보가 포함되어 있습니다.
우리는 모든 사람들 사이의 가족 관계를 알
그냥 나무를 검토하여.
또한, 그것은 속도를 높일 수 있습니다
룩 - 업 (look-up) 시간 엄청난, 나무 데이터가 정렬되어있는 경우.
>> 우리는 여기 활용할 수는 없지만, 우리는 곧이의 예를 볼 수 있습니다.
각 사람은 트리에서 노드로 표시됩니다.
노드는 자식 노드를 가질 수 있습니다
뿐만 아니라 부모 노드 있습니다.
다음은, 기술적 인 용어입니다
가족 이외의 일을위한 나무를 사용하는 경우에도.
앨리스의 노드는, 어린이 2 명없이 부모가
찰리의 노드는 3 명이 1 부모가있을 때.
>> 잎 노드는 아이가없는 하나입니다
나무의 바깥 가장자리에.
트리의 최상위 노드, 루트 노드,
상위가 없습니다.
>> 이진 트리, 트리의 특정 유형입니다
어떤의 각 노드는 대부분에서 어린이 2 명이이 있습니다.
여기 C.에있는 이진 트리의 노드의 구조체는
모든 노드는 관련 일부 데이터가
다른 노드와 2 개의 포인터.
>> 우리 가족 트리에서
관련 데이터는 각 사람의 이름이었다.
그것은 아무 것도 될 수 있지만 여기가, 정수입니다.
그것은 밝혀
이진 나무, 가족에 대한 좋은 표현되지 않을 것
사람들은 자주 이상 어린이 2 명을 가지고 있으니까.
>> 이진 검색 트리
이진 트리의 특별한 명령 유형
그 우리는 신속하게 값을 볼 수 있습니다.
알아 챘 수 있습니다
그 트리의 루트 아래의 모든 노드
다른 나무의 뿌리는 '하위 트리'이라고합니다.
여기서, 트리의 루트는 6입니다
와 자녀, 2, 하위 트리의 루트입니다.
>> 이진 검색 트리에서
노드의 모든 값은 오른쪽 하위 트리입니다
노드의 값보다 큰 수 있습니다. 여기 : 6.
음, 노드의 왼쪽 하위 트리의 값
노드의 값보다 적습니다.
우리는 중복 값을 처리해야하는 경우,
우리는 느슨한 불평등에 두 사람들의 변경할 수 있습니다
동일한 값이 왼쪽 또는 오른쪽에 하나 빠질 수 즉,
오래 우리가 내내 그것에 대해 일관성 때문입니다.
이 나무는 이진 검색 트리입니다
그것은 다음과 같은 규칙을 따른다 때문입니다.
>> 이것은 우리가 C의 structs에 모든 노드를 설정하는 경우는 표시 방식입니다.
주의 그 아이가 누락 된 경우,
포인터가 null입니다.
우리가 어떻게 7 트리에 있는지 확인합니까?
우리는 루트에서 시작합니다.
이 트리에 있다면 세븐은 6보다 큰이기 때문에, 그것은 오른쪽에 있어야합니다.
그런 다음 8 미만이므로 왼쪽으로해야합니다.
여기, 우리는 7을 발견했습니다.
이제, 우리는 5 확인합니다.
다섯은 6 미만이므로 왼쪽에 있어야합니다.
다섯는 2보다 큰 수 있습니다
그래서, 오른쪽이어야합니다
그리고 또한 4보다 큰 때문에 바로 다시해야합니다.
그러나, 어떤 아이는 여기에 없습니다.
포인터가 null입니다.
이 5 우리 나무에없는 것을 의미합니다.
>> 우리는 다음 코드와 바이너리 트리를 검색 할 수 있습니다 :
모든 노드에서, 우리는 우리가 발견 한 경우 확인
우리가 찾고있는 값입니다.
우리가 찾을 수없는 경우가있을 경우, 우리는 결정
왼쪽 또는 오른쪽에 그 하위 구조를 확인합니다.
이 루프는 나무를 계속
왼쪽 또는 오른쪽 중 하나에 자식 노드가 없을 때까지.
>> 5 트리에 존재하지 않았을 기억하십시오.
우리가 어떻게 그것을 삽입하려면 어떻게해야합니까?
이 과정은 검색 유사 해 보입니다.
우리는 6부터 나무를 반복
2 왼쪽,
4 자,
오른쪽 다시하지만, 4 저쪽에 자식이 없습니다.
이 5의 새로운 위치 될 것입니다
그리고 아무 아이들과 함께 시작됩니다.
>> 얼마나 빨리 이진 검색 트리에서 작업입니까?
Bigohnotation가 상위 바운드를 제공하고자 기억하십시오.
최악의 경우,
우리 나무는 단순히 링크 된 목록이 될 수 있습니다
그 삽입, 삭제, 검색을 의미
트리의 노드의 수에 비례 시간이 걸릴 수 있습니다.
이 O (n)이됩니다.
>> 예를 들어, 다음은 올바른 이진 검색 트리입니다.
그러나, 우리는 9 찾으려고하면
우리는 모든 노드를 통과해야합니다.
이 연결리스트보다 더 좋은하지 않습니다.
이상적으로, 우리는 모든 노드를 원하는 것
우리의 이진 검색 트리의 두 자녀가 있습니다.
이 방법, 삽입, 삭제 및 검색
, 최악의, O (로그 n)이 시간이 걸릴 것입니다.
이전의 나무가 더 균형이 될 수 있습니다
이처럼.
이제 어떤 값을 찾는 것은 3 단계, 대부분의시 소요됩니다.
이 나무는 균형이다
이 의미는 최소한의 깊이가
노드의 수를 기준으로.
>> 균형 이진 검색 트리에서 값을 찾고
정렬 배열에서 바이너리 검색 유사합니다.
사실, 우리가 항목을 삽입하거나 삭제할 필요가없는 경우는,
그들은 정확히 동일한 방식으로 동작합니다.
그러나, 트리 구조가 더 좋아
처리 삽입과 삭제에 대한
>> 내 이름은 Bannus 반 데르 Kloot입니다.
이 CS50입니다.