1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Как бы вы представляете всех членов вашей семьи в компьютере?

2
00:00:10,790 --> 00:00:12,390
Мы могли бы просто использовать список,

3
00:00:12,390 --> 00:00:14,400
но есть четкая иерархия здесь.

4
00:00:14,400 --> 00:00:17,110
>> Скажем, мы начинаем с вашей прабабушки, Alice.

5
00:00:17,110 --> 00:00:19,030
Она имеет 2 сыновей, Боба

6
00:00:19,030 --> 00:00:21,310
и ваши дедушки, Чарли.

7
00:00:21,310 --> 00:00:23,190
Чарли имеет 3 детей,

8
00:00:23,190 --> 00:00:26,730
Ваш дядя, Дэйв, твоя тетя, Ева, и ваш отец, Фред.

9
00:00:26,730 --> 00:00:28,750
Вы единственный ребенок в семье Фреда.

10
00:00:28,750 --> 00:00:30,950
>> Почему организацию членов вашей семьи, таким образом,

11
00:00:30,950 --> 00:00:34,010
быть лучше, чем простое представление списка?

12
00:00:34,010 --> 00:00:36,630
Одной из причин является то, что эта иерархическая структура,

13
00:00:36,630 --> 00:00:39,660
называют «деревом», содержит больше информации, чем простой список.

14
00:00:40,540 --> 00:00:43,520
Мы знаем, что семейные отношения между всеми

15
00:00:43,520 --> 00:00:45,440
только путем изучения дерева.

16
00:00:45,440 --> 00:00:47,250
Кроме того, это может ускорить

17
00:00:47,250 --> 00:00:50,010
справочной время чрезвычайно, если дерево сортировки данных.

18
00:00:50,010 --> 00:00:53,850
>> Мы не можем воспользоваться тем, что здесь, но мы видим пример этому в ближайшее время.

19
00:00:53,850 --> 00:00:56,150
Каждый человек представляет собой узел на дереве.

20
00:00:56,680 --> 00:00:58,370
Узлы могут иметь дочерние узлы

21
00:00:58,370 --> 00:01:00,350
а также родительского узла.

22
00:01:00,350 --> 00:01:02,390
Эти технические термины,

23
00:01:02,390 --> 00:01:05,220
даже при использовании деревьев для вещей, кроме семьи.

24
00:01:05,220 --> 00:01:07,940
Узлу Алисы имеет 2 детей, и нет родителей,

25
00:01:07,940 --> 00:01:11,500
в то время как узел Чарли имеет 3 детей и 1 родитель.

26
00:01:11,500 --> 00:01:14,330
>> Листовым узлом является тот, который не имеет детей

27
00:01:14,330 --> 00:01:16,410
по внешнему краю дерева.

28
00:01:16,410 --> 00:01:18,520
Самый верхний узел дерева, корневой узел,

29
00:01:18,520 --> 00:01:20,240
не имеет родителя.

30
00:01:20,240 --> 00:01:23,170
>> Бинарное дерево является специфический тип дерева,

31
00:01:23,170 --> 00:01:26,720
, в которой каждый узел имеет, самое большее, 2 детей.

32
00:01:26,720 --> 00:01:30,490
Вот структура узла в бинарном дереве в C.

33
00:01:31,560 --> 00:01:34,530
Каждый узел имеет некоторые связанные с ним данные

34
00:01:34,530 --> 00:01:36,520
и 2 указатели на другие узлы.

35
00:01:36,520 --> 00:01:38,110
>> В наше генеалогическое дерево,

36
00:01:38,110 --> 00:01:40,900
связанные с ним данные звали каждого человека.

37
00:01:40,900 --> 00:01:43,850
Вот она Int, хотя это может быть что угодно.

38
00:01:44,510 --> 00:01:46,200
Как выяснилось,

39
00:01:46,200 --> 00:01:48,990
бинарное дерево не было бы хорошее представление для семьи,

40
00:01:48,990 --> 00:01:51,960
так как люди часто имеют более 2 детей.

41
00:01:51,960 --> 00:01:53,510
>> Бинарное дерево поиска

42
00:01:53,510 --> 00:01:56,380
это особый, упорядоченный тип бинарного дерева

43
00:01:56,380 --> 00:01:58,090
, что позволяет нам смотреть на значениях быстро.

44
00:01:58,740 --> 00:02:00,050
Вы, возможно, заметили,

45
00:02:00,050 --> 00:02:02,010
что каждый узел под корень дерева

46
00:02:02,010 --> 00:02:04,620
корень другого дерева, называемого "поддерево".

47
00:02:04,960 --> 00:02:07,090
Здесь, корень дерева 6,

48
00:02:07,090 --> 00:02:09,860
и ее ребенка, 2, является корнем поддерева.

49
00:02:09,860 --> 00:02:11,870
>> В бинарном дереве поиска

50
00:02:11,870 --> 00:02:15,790
все значения узла правого поддерева

51
00:02:15,790 --> 00:02:18,690
больше, чем значение узла. Здесь: 6.

52
00:02:18,690 --> 00:02:22,640
Ну, значения в левом поддереве узла

53
00:02:24,540 --> 00:02:26,890
меньше, чем значение узла.

54
00:02:26,890 --> 00:02:28,620
Если нужно обрабатывать повторяющиеся значения,

55
00:02:28,620 --> 00:02:31,760
мы можем изменить любой из тех, свободные неравенство,

56
00:02:31,760 --> 00:02:34,410
то есть одинаковые значения может упасть либо на левый или правый,

57
00:02:34,410 --> 00:02:37,400
тех пор, как мы последовательны об этом всем.

58
00:02:37,400 --> 00:02:39,620
Это дерево бинарное дерево поиска

59
00:02:39,620 --> 00:02:41,540
потому что он следует этим правилам.

60
00:02:42,320 --> 00:02:46,020
>> Вот как это будет выглядеть, если мы повернули всех узлов в структурах C.

61
00:02:46,880 --> 00:02:48,410
Обратите внимание, что если ребенок отсутствует,

62
00:02:48,410 --> 00:02:50,340
указатель является нулевым.

63
00:02:50,340 --> 00:02:53,270
Как мы проверяем, если 7 в дереве?

64
00:02:53,270 --> 00:02:55,020
Мы начинаем в корне.

65
00:02:55,020 --> 00:02:58,690
Семь больше 6, так что если это в дерево, оно должно быть с правой стороны.

66
00:02:59,680 --> 00:03:03,650
Тогда, это меньше, чем 8, поэтому он должен быть слева.

67
00:03:03,650 --> 00:03:06,210
Здесь мы нашли 7.

68
00:03:06,210 --> 00:03:08,160
Сейчас мы проверим на 5.

69
00:03:08,160 --> 00:03:11,500
Пять меньше, чем 6, поэтому он должен быть слева.

70
00:03:11,500 --> 00:03:13,460
Пять больше 2,

71
00:03:13,460 --> 00:03:15,010
поэтому он должен быть правильным,

72
00:03:15,010 --> 00:03:18,100
и это также больше 4, поэтому он должен быть еще раз направо.

73
00:03:18,100 --> 00:03:20,300
Тем не менее, нет ни одного ребенка здесь.

74
00:03:20,300 --> 00:03:22,000
Указатель является нулевым.

75
00:03:22,000 --> 00:03:24,270
Это означает, что 5 не в наших деревьев.

76
00:03:24,270 --> 00:03:27,250
>> Мы можем искать двоичного дерева с помощью следующего кода:

77
00:03:28,430 --> 00:03:31,140
На каждом узле, мы проверяем, если мы нашли

78
00:03:31,140 --> 00:03:33,020
Значение, которое мы ищем.

79
00:03:33,020 --> 00:03:35,740
Если мы не найдем его, мы определить, если она должна быть

80
00:03:35,740 --> 00:03:38,990
на левый или правый и убедиться, что поддерево.

81
00:03:38,990 --> 00:03:41,160
Этот цикл будет продолжаться вниз по дереву

82
00:03:41,160 --> 00:03:44,190
пока не будет дочерний узел на левом или правом.

83
00:03:45,190 --> 00:03:48,600
>> Помните, что 5 не был в дерево.

84
00:03:48,600 --> 00:03:50,460
Как мы можем вставить его?

85
00:03:50,460 --> 00:03:52,370
Этот процесс похож на поиск.

86
00:03:52,370 --> 00:03:54,830
Мы итерацию по дереву, начиная с 6,

87
00:03:54,830 --> 00:03:57,040
слева 2,

88
00:03:57,040 --> 00:03:59,140
Право 4,

89
00:03:59,140 --> 00:04:02,500
и еще раз направо, а 4 не имеет ребенком на этой стороне.

90
00:04:02,500 --> 00:04:06,090
Это будет новая должность на 5,

91
00:04:06,090 --> 00:04:08,500
и он начнет без детей.

92
00:04:09,020 --> 00:04:12,220
>> Как быстро операций на бинарном дереве поиска?

93
00:04:12,220 --> 00:04:15,410
Помните, что Bigohnotation стремится обеспечить верхней границы.

94
00:04:15,410 --> 00:04:17,390
В худшем случае,

95
00:04:17,390 --> 00:04:19,480
наше дерево может быть просто связанный список

96
00:04:19,480 --> 00:04:22,220
Это означает, что вставки, удаления и поиска

97
00:04:22,220 --> 00:04:25,380
может занять время, пропорциональное числу узлов в дереве.

98
00:04:25,380 --> 00:04:27,380
Это O (N).

99
00:04:27,380 --> 00:04:30,690
>> Например, следующее является действительным бинарное дерево поиска.

100
00:04:31,850 --> 00:04:34,020
Однако, если мы пытаемся найти 9,

101
00:04:34,020 --> 00:04:36,760
мы должны пройти каждом узле.

102
00:04:36,760 --> 00:04:39,120
Это не лучше, чем связанный список.

103
00:04:39,120 --> 00:04:41,410
В идеале, мы хотели бы, каждый узел

104
00:04:41,410 --> 00:04:44,120
наши бинарное дерево поиска, чтобы иметь 2 детей.

105
00:04:44,120 --> 00:04:46,370
Таким образом, вставка, удаление и поиск

106
00:04:46,370 --> 00:04:50,190
бы, на худой конец, O (журнал N) времени.

107
00:04:50,190 --> 00:04:52,470
Дерево, прежде чем могла бы быть более сбалансированной,

108
00:04:52,470 --> 00:04:54,140
как это.

109
00:04:54,140 --> 00:04:57,980
Теперь, глядя любое значение имеет, самое большее, 3 шага.

110
00:04:57,980 --> 00:04:59,460
Это дерево является сбалансированным,

111
00:04:59,460 --> 00:05:01,190
значение, которое имеет минимальную глубину

112
00:05:01,190 --> 00:05:03,680
по сравнению с числом узлов.

113
00:05:03,680 --> 00:05:06,300
>> Ищет значение в бинарное дерево

114
00:05:06,300 --> 00:05:09,540
похоже на двоичный поиск в отсортированном массиве.

115
00:05:09,540 --> 00:05:12,290
В самом деле, если нам не нужно вставлять или удалять элементы,

116
00:05:12,290 --> 00:05:15,150
они ведут себя точно так же.

117
00:05:15,150 --> 00:05:17,600
Тем не менее, структура дерева лучше

118
00:05:17,600 --> 00:05:19,530
для обработки вставок и удалений

119
00:05:20,360 --> 00:05:22,670
>> Меня зовут Bannus Ван-дер-Kloot.

120
00:05:22,670 --> 00:05:24,030
Это CS50.