1
00:00:00,450 --> 00:00:05,010
‫So now we're going to look at binary search tree big O.

2
00:00:05,520 --> 00:00:10,170
‫In order to do this, we'll have to do some simple math.

3
00:00:10,350 --> 00:00:15,630
‫So the number of nodes in this tree right now obviously is one.

4
00:00:16,110 --> 00:00:21,060
‫But you could also write this as two to the one minus one.

5
00:00:21,080 --> 00:00:25,080
‫Two to the one is two, minus one equals one.

6
00:00:25,530 --> 00:00:27,750
‫And you'll see why I'm doing this here in a second.

7
00:00:28,530 --> 00:00:34,620
‫But if we have a second level like this, this is two to the two -1 to 2.

8
00:00:34,680 --> 00:00:36,840
‫The two is four, minus one is three.

9
00:00:37,800 --> 00:00:39,600
‫Two of the three minus one.

10
00:00:39,600 --> 00:00:42,510
‫Two to the four minus one.

11
00:00:43,270 --> 00:00:49,780
‫Now as we get into very large numbers here, that one is insignificant.

12
00:00:50,290 --> 00:00:55,450
‫So let's remove this and we'll say this is approximately two to the four nodes.

13
00:00:55,780 --> 00:00:59,260
‫This is approximately two to the three and two to the two.

14
00:00:59,970 --> 00:01:01,560
‫And two to the one.

15
00:01:02,350 --> 00:01:07,360
‫Now, if you're going to look for a node in this tree, it's going to take.

16
00:01:07,900 --> 00:01:10,240
‫One step, obviously.

17
00:01:10,720 --> 00:01:15,460
‫But when we go to two levels, let's say we're going to look for the number 76.

18
00:01:15,460 --> 00:01:17,920
‫That is one two steps.

19
00:01:18,370 --> 00:01:22,060
‫So we have two to the two nodes approximately.

20
00:01:22,060 --> 00:01:25,270
‫And it took us two steps to find something.

21
00:01:26,270 --> 00:01:29,180
‫Let's say we're going to look for the number 27.

22
00:01:29,510 --> 00:01:33,200
‫It is one, two, three steps.

23
00:01:34,260 --> 00:01:42,580
‫And if we were going to look for the number 49 in this case, it would be one, two, three, four steps.

24
00:01:42,600 --> 00:01:47,190
‫We have two to the four nodes and it took four steps.

25
00:01:47,520 --> 00:01:50,700
‫So it's four steps to find something.

26
00:01:51,930 --> 00:01:57,870
‫It's four steps to remove something because you have to iterate through the list, find the node, and

27
00:01:57,870 --> 00:01:59,100
‫then remove it.

28
00:02:00,190 --> 00:02:01,810
‫And it's also four steps.

29
00:02:01,810 --> 00:02:07,420
‫If we're going to add a node, if we're going to add a node under that 49, we would have to iterate

30
00:02:07,420 --> 00:02:10,330
‫through four steps and then we could insert it.

31
00:02:10,840 --> 00:02:21,190
‫So that means that all of these are o of log in and of log in is very efficient.

32
00:02:21,910 --> 00:02:27,310
‫So remember o of log in is achieved by doing divide and conquer.

33
00:02:27,760 --> 00:02:31,930
‫So let's bring our tree back here and show how it is that we're doing that.

34
00:02:32,590 --> 00:02:37,780
‫So if we're going to look for that 49 node again, we start at the top.

35
00:02:38,380 --> 00:02:39,550
‫And then we go.

36
00:02:39,580 --> 00:02:40,510
‫Right.

37
00:02:41,230 --> 00:02:42,340
‫And what do we do?

38
00:02:42,370 --> 00:02:48,400
‫We just made it where we never have to look at anything that's on the left of the 47.

39
00:02:49,670 --> 00:02:53,930
‫So we are effectively removing these from the search.

40
00:02:54,380 --> 00:02:57,500
‫And that's not a big deal when you have a small tree like this.

41
00:02:57,500 --> 00:03:03,650
‫But if you had a million items in the tree, you just made it where there are half a million items that

42
00:03:03,650 --> 00:03:05,210
‫you don't have to look at.

43
00:03:05,510 --> 00:03:08,630
‫And then from here, we're going to go left.

44
00:03:09,230 --> 00:03:14,990
‫And now we have made it where half of the remaining nodes don't need to be looked at like that.

45
00:03:15,500 --> 00:03:21,230
‫And then we finally come down to the 49 node, and we have done that again.

46
00:03:21,920 --> 00:03:24,350
‫And that is divide and conquer.

47
00:03:25,200 --> 00:03:27,630
‫So let's bring all of this back.

48
00:03:28,420 --> 00:03:36,970
‫So for our examples, for calculating time complexity, so far we have used a perfect tree and a perfect

49
00:03:36,970 --> 00:03:41,350
‫tree is going to give you your best possible scenario.

50
00:03:41,830 --> 00:03:46,450
‫And remember, we measured best possible scenario with Omega.

51
00:03:47,260 --> 00:03:51,130
‫You're more likely to see a tree that looks like this.

52
00:03:51,990 --> 00:03:57,360
‫But even in this situation, you would say that this is roughly log in.

53
00:03:58,000 --> 00:04:00,490
‫But now let's look at our worst case.

54
00:04:00,730 --> 00:04:08,560
‫Our worst case would be if we had a node and then the next one was greater than and it goes to the right

55
00:04:08,890 --> 00:04:12,700
‫and the next one is greater than that, and it goes to the right of that one.

56
00:04:12,700 --> 00:04:14,410
‫And the next one is greater than that.

57
00:04:14,410 --> 00:04:18,460
‫And it just keeps going on and on in a straight line.

58
00:04:19,060 --> 00:04:23,050
‫If the tree never forks, it is essentially.

59
00:04:23,810 --> 00:04:25,070
‫A linked list.

60
00:04:25,520 --> 00:04:28,590
‫So let's say we want to go look for the 91 node.

61
00:04:28,610 --> 00:04:30,530
‫How many steps would it take?

62
00:04:30,680 --> 00:04:34,700
‫It would be one, two, three, four.

63
00:04:35,330 --> 00:04:38,000
‫And we have four nodes in the tree.

64
00:04:38,510 --> 00:04:40,820
‫That is O of N.

65
00:04:41,480 --> 00:04:49,520
‫So the big O of a binary search tree technically is o of n, not o of log in.

66
00:04:50,030 --> 00:04:53,690
‫So let's bring our other nodes up here like this.

67
00:04:53,990 --> 00:04:59,930
‫What we assume with a binary search tree is it's not going to be a straight line.

68
00:04:59,930 --> 00:05:07,400
‫We're not going to have that worst possible scenario and we treat it as if it is o of log in.

69
00:05:07,940 --> 00:05:12,650
‫We don't treat this like an o of n data structure.

70
00:05:13,910 --> 00:05:22,280
‫So for lookup insert and remove we treat this as if it is o of log in.

71
00:05:23,160 --> 00:05:29,940
‫So now let's take all three of these, the lookup, the insert, the remove and compare it to a linked

72
00:05:29,940 --> 00:05:30,840
‫list.

73
00:05:31,890 --> 00:05:33,930
‫So look up in a linked list.

74
00:05:33,930 --> 00:05:38,820
‫If we're going to look up the number 91, we would have to iterate through the entire list until we

75
00:05:38,820 --> 00:05:42,510
‫found that number, which makes this a within.

76
00:05:43,350 --> 00:05:47,160
‫Which makes a binary search tree better at this.

77
00:05:48,380 --> 00:05:51,200
‫So now let's look at remove.

78
00:05:51,990 --> 00:05:57,600
‫If we're going to remove that number 91, whether we're going to look it up by index is at the index

79
00:05:57,600 --> 00:06:00,450
‫of three or if we're going to look it up by value.

80
00:06:00,450 --> 00:06:07,410
‫Either way, we have to iterate through the length list until we get to this node and then we can remove

81
00:06:07,410 --> 00:06:07,860
‫it.

82
00:06:08,310 --> 00:06:10,560
‫And that is o of n.

83
00:06:11,450 --> 00:06:17,180
‫But now let's look at insert see with a linked list.

84
00:06:17,750 --> 00:06:20,810
‫There is no advantage to keeping it sorted.

85
00:06:20,810 --> 00:06:24,710
‫We're not able to find anything faster because it's sorted.

86
00:06:24,710 --> 00:06:29,120
‫When we looked for the 91, we still had to iterate through the list.

87
00:06:29,970 --> 00:06:34,890
‫So for insert we would just add an item to the end.

88
00:06:35,650 --> 00:06:37,900
‫And that is o of one.

89
00:06:37,900 --> 00:06:42,130
‫So insert is actually faster with a linked list.

90
00:06:42,700 --> 00:06:49,000
‫So let's look at all three of these side by side with a linked list and a binary search tree.

91
00:06:49,330 --> 00:06:56,350
‫Insert is faster for a linked list and that's because we can just add an item to the end.

92
00:06:56,350 --> 00:07:02,020
‫And it's o of one where inserting an item in a binary search tree is o of log in.

93
00:07:03,270 --> 00:07:11,400
‫Look up as faster with a binary search tree because it's over, log in instead of o of n and then removing

94
00:07:11,400 --> 00:07:14,700
‫an item is also faster with a binary search tree.

95
00:07:15,330 --> 00:07:25,230
‫And the big O for these three operations is also the same for vectors as it would be for linked lists.

96
00:07:25,680 --> 00:07:33,330
‫So I'm going to use a vector here because length lists and binary search trees are dynamic in size.

97
00:07:33,330 --> 00:07:35,520
‫So this is a better comparison.

98
00:07:35,970 --> 00:07:41,370
‫So inserting an item with a vector, you would just add it to the end.

99
00:07:41,370 --> 00:07:48,690
‫That's of one that's the same as a linked list and it is also better than a binary search tree.

100
00:07:48,960 --> 00:07:58,470
‫But if you're going to do a lookup or remove based on value, not index but value, it is aux of in

101
00:07:58,470 --> 00:08:03,270
‫with a vector and log in with a binary search tree.

102
00:08:03,810 --> 00:08:09,360
‫And that is our overview of binary search tree big oh.