[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.08,Default,,0000,0000,0000,,So, in this video, we'll graduate beyond\Nthe domain of just vanilla binary search
Dialogue: 0,0:00:03.08,0:00:07.04,Default,,0000,0000,0000,,trees, like we've been talking about\Nbefore, and we'll start talking about
Dialogue: 0,0:00:07.04,0:00:10.07,Default,,0000,0000,0000,,balanced binary search trees.\NThese are the search trees you'd really
Dialogue: 0,0:00:10.07,0:00:13.85,Default,,0000,0000,0000,,want to use when you want to have real\Ntime guarantees on your operation time.
Dialogue: 0,0:00:13.85,0:00:17.63,Default,,0000,0000,0000,,Cuz they're search trees which are\Nguaranteed to stay balanced, which means
Dialogue: 0,0:00:17.63,0:00:21.02,Default,,0000,0000,0000,,the height is guaranteed to stay\Nlogarithmic, which means all of the
Dialogue: 0,0:00:21.02,0:00:25.00,Default,,0000,0000,0000,,operations search trees support that we\Nknow and love, will also be a logarithmic
Dialogue: 0,0:00:25.00,0:00:27.01,Default,,0000,0000,0000,,in the number of keys that they're\Nstoring.
Dialogue: 0,0:00:27.01,0:00:30.06,Default,,0000,0000,0000,,So, let's just quickly recap.\NWhat is the basic structure tree property?
Dialogue: 0,0:00:30.06,0:00:34.08,Default,,0000,0000,0000,,It should be the case that at every single\Nnode of your search tree, if you go to the
Dialogue: 0,0:00:34.08,0:00:38.06,Default,,0000,0000,0000,,left, you'll only see keys that are\Nsmaller than where you started and if you
Dialogue: 0,0:00:38.06,0:00:42.02,Default,,0000,0000,0000,,go to the right you only see keys that\Nare bigger than where you started.
Dialogue: 0,0:00:42.02,0:00:45.61,Default,,0000,0000,0000,,And a really important observation, which\Nis that, given a set of keys, there's
Dialogue: 0,0:00:45.61,0:00:48.88,Default,,0000,0000,0000,,going to be lot and lots of legitimate,\Nvalid, binary search trees with those
Dialogue: 0,0:00:48.88,0:00:50.99,Default,,0000,0000,0000,,keys.\NSo, we've been having these running
Dialogue: 0,0:00:50.99,0:00:53.53,Default,,0000,0000,0000,,examples where the keys one, two, three,\Nfour, five.
Dialogue: 0,0:00:53.53,0:00:57.59,Default,,0000,0000,0000,,On the one hand, you can have a nice and\Nbalanced search tree that has height only
Dialogue: 0,0:00:57.59,0:01:01.62,Default,,0000,0000,0000,,two, with the keys one through five.\NOn the other hand, you can also have these
Dialogue: 0,0:01:01.62,0:01:05.96,Default,,0000,0000,0000,,crazy chains, basically devolved to link\Nlists where the heights for, and elements
Dialogue: 0,0:01:05.96,0:01:08.94,Default,,0000,0000,0000,,could be as high as N - 1.\NSo, in general, you could have an
Dialogue: 0,0:01:08.94,0:01:13.48,Default,,0000,0000,0000,,exponential difference in the height.\NIt can be as small, in the best case, as
Dialogue: 0,0:01:13.48,0:01:16.42,Default,,0000,0000,0000,,logarithmic and as big, in the worst case,\Nas linear.
Dialogue: 0,0:01:16.42,0:01:20.15,Default,,0000,0000,0000,,So, this obviously motivates search trees\Nthat have the additional property that you
Dialogue: 0,0:01:20.15,0:01:23.62,Default,,0000,0000,0000,,never have to worry about their height.\NYou know they're going to be well
Dialogue: 0,0:01:23.62,0:01:25.59,Default,,0000,0000,0000,,balanced.\NYou know they're going to have height
Dialogue: 0,0:01:25.59,0:01:28.24,Default,,0000,0000,0000,,logarithmic.\NYou're never worried about them having
Dialogue: 0,0:01:28.24,0:01:32.31,Default,,0000,0000,0000,,this really lousy linear height.\NRemember, why it's so important to have a
Dialogue: 0,0:01:32.31,0:01:35.48,Default,,0000,0000,0000,,small height?\NIt's because the running time of all of
Dialogue: 0,0:01:35.48,0:01:38.77,Default,,0000,0000,0000,,the operations of search trees depends on\Nthe height.
Dialogue: 0,0:01:38.77,0:01:43.46,Default,,0000,0000,0000,,You want to do search, you want to\Ninsertions, you want to find predecessors
Dialogue: 0,0:01:43.46,0:01:48.33,Default,,0000,0000,0000,,or whatever, the height is going to be\Nwhat governs the running time of all those
Dialogue: 0,0:01:48.33,0:01:50.01,Default,,0000,0000,0000,,properties.\NSo, the high level idea behind balanced search
Dialogue: 0,0:01:50.01,0:01:54.78,Default,,0000,0000,0000,,trees is really exactly what you think,\Nwhich is that, you know, because the
Dialogue: 0,0:01:54.78,0:01:58.46,Default,,0000,0000,0000,,height can't be any better than\Nlogarithmic in the number of things you're
Dialogue: 0,0:01:58.46,0:02:02.19,Default,,0000,0000,0000,,storing, that's because the trees are\Nbinary so the number of nodes can only
Dialogue: 0,0:02:02.19,0:02:05.15,Default,,0000,0000,0000,,double each level so you need a\Nlogarithmic number of levels to
Dialogue: 0,0:02:05.15,0:02:07.04,Default,,0000,0000,0000,,accommodate everything that you are\Nstoring.
Dialogue: 0,0:02:07.04,0:02:11.01,Default,,0000,0000,0000,,But it's got to be logarithmic, lets make\Nsure it stays logarithmic all the time,
Dialogue: 0,0:02:11.01,0:02:16.40,Default,,0000,0000,0000,,even as we do insertions and deletions.\NIf we can do that, then we get a very rich
Dialogue: 0,0:02:16.40,0:02:21.01,Default,,0000,0000,0000,,collection of supported operations all\Nrunning in logarithmic time.
Dialogue: 0,0:02:21.06,0:02:25.05,Default,,0000,0000,0000,,As usual, n denotes, the number of\Nkeys being stored in the tree.
Dialogue: 0,0:02:25.05,0:02:29.01,Default,,0000,0000,0000,,There are many, many, many different\Nbalanced search trees.
Dialogue: 0,0:02:29.01,0:02:33.02,Default,,0000,0000,0000,,They're not super, most of them are not\Nsuper different from each other.
Dialogue: 0,0:02:33.02,0:02:37.09,Default,,0000,0000,0000,,I'm going to talk about one of the more\Npopular ones which are called Red Black
Dialogue: 0,0:02:37.09,0:02:40.06,Default,,0000,0000,0000,,Trees.\NSo, these were invented back in the '70s.
Dialogue: 0,0:02:40.10,0:02:44.67,Default,,0000,0000,0000,,These were not the first balanced binary\Nsearch tree data structures, that honor
Dialogue: 0,0:02:44.67,0:02:49.00,Default,,0000,0000,0000,,belongs to AVL trees, which again are not\Nvery different from red black trees,
Dialogue: 0,0:02:49.00,0:02:51.62,Default,,0000,0000,0000,,though the invariants are slightly\Ndifferent.
Dialogue: 0,0:02:51.62,0:02:55.100,Default,,0000,0000,0000,,Another thing you might want to look up\Nand read about is a very cool data
Dialogue: 0,0:02:55.100,0:02:58.45,Default,,0000,0000,0000,,structure called splay trees, due to\NSleator and Tarjan,
Dialogue: 0,0:02:58.45,0:03:01.80,Default,,0000,0000,0000,,These, unlike red black trees and AVL\Ntrees, which only are modified on
Dialogue: 0,0:03:01.80,0:03:05.72,Default,,0000,0000,0000,,insertions and deletions, which, if you\Nthink about it, is sort of what you'd
Dialogue: 0,0:03:05.72,0:03:08.58,Default,,0000,0000,0000,,expect.\NSplay trees modify themselves, even when
Dialogue: 0,0:03:08.58,0:03:11.79,Default,,0000,0000,0000,,you're doing look ups, even when you're\Ndoing searches.
Dialogue: 0,0:03:11.79,0:03:15.74,Default,,0000,0000,0000,,So, they're sometimes called\Nself-adjusting trees for that reason.
Dialogue: 0,0:03:15.74,0:03:20.65,Default,,0000,0000,0000,,And it's super simple, but they still have\Nkind of amazing guarantees.
Dialogue: 0,0:03:20.65,0:03:25.21,Default,,0000,0000,0000,,And then finally, going beyond the, just\Nthe binary tree paradigm many of you might
Dialogue: 0,0:03:25.21,0:03:28.28,Default,,0000,0000,0000,,want to look up examples of B trees or\Nalso B+ trees.
Dialogue: 0,0:03:28.28,0:03:31.44,Default,,0000,0000,0000,,These are very relevant for implementing\Ndatabases.
Dialogue: 0,0:03:31.44,0:03:35.50,Default,,0000,0000,0000,,Here what the idea is, in a given node\Nyou're going to have not just one key but
Dialogue: 0,0:03:35.50,0:03:39.57,Default,,0000,0000,0000,,many keys and from a node, you have\Nmultiple branches that you can take
Dialogue: 0,0:03:39.57,0:03:44.31,Default,,0000,0000,0000,,depending where you're searching for falls\Nwith respect to the multiple keys that are
Dialogue: 0,0:03:44.31,0:03:47.14,Default,,0000,0000,0000,,at that node.\NThe motivation in a database context for
Dialogue: 0,0:03:47.14,0:03:50.67,Default,,0000,0000,0000,,going beyond the binary paradigm, is to\Nhave a better match up with the memory
Dialogue: 0,0:03:50.67,0:03:53.30,Default,,0000,0000,0000,,hierarchy.\NSo, that's also very important, although a
Dialogue: 0,0:03:53.30,0:03:57.32,Default,,0000,0000,0000,,little bit out of the scope here.\NThat said, what we discuss about red-black
Dialogue: 0,0:03:57.32,0:04:01.13,Default,,0000,0000,0000,,trees, much of the intuition will\Ntranslate to all of these other balance
Dialogue: 0,0:04:01.13,0:04:05.64,Default,,0000,0000,0000,,tree data structures, if you ever find\Nyourself in a position where you need to
Dialogue: 0,0:04:05.64,0:04:09.17,Default,,0000,0000,0000,,learn more about them.\NSo, red black trees are just the same as
Dialogue: 0,0:04:09.17,0:04:13.41,Default,,0000,0000,0000,,binary search trees, except they also\Nalways maintain a number of additional
Dialogue: 0,0:04:13.41,0:04:16.36,Default,,0000,0000,0000,,invariants.\NAnd so, what I'm going to focus on in this
Dialogue: 0,0:04:16.36,0:04:19.78,Default,,0000,0000,0000,,video is, first of all, what the\Ninvariants are, and then how the
Dialogue: 0,0:04:19.78,0:04:22.85,Default,,0000,0000,0000,,invariants guarantee that the height will\Nbe logarithmic.
Dialogue: 0,0:04:22.85,0:04:27.08,Default,,0000,0000,0000,,Time permitting, at some point, there will\Nbe optional videos more about the guts,
Dialogue: 0,0:04:27.08,0:04:31.61,Default,,0000,0000,0000,,more about the implementations of red\Nblack trees namely how do you maintain
Dialogue: 0,0:04:31.61,0:04:34.10,Default,,0000,0000,0000,,these invariants under insertions and\Ndeletions.
Dialogue: 0,0:04:34.10,0:04:37.68,Default,,0000,0000,0000,,That's quite a bit more complicated, so\Nthat's appropriate for, for optional
Dialogue: 0,0:04:37.68,0:04:40.53,Default,,0000,0000,0000,,material.\NBut understanding what the invariants are
Dialogue: 0,0:04:40.53,0:04:44.79,Default,,0000,0000,0000,,and what role they play in controlling the\Nheight is very accessible, and it's
Dialogue: 0,0:04:44.79,0:04:47.29,Default,,0000,0000,0000,,something I think every programmer should\Nknow.
Dialogue: 0,0:04:47.29,0:04:51.15,Default,,0000,0000,0000,,So, there, I'm going to write down four\Ninvariants and really, the bite comes from
Dialogue: 0,0:04:51.15,0:04:54.42,Default,,0000,0000,0000,,the second two, okay, from the third and\Nthe fourth invariant.
Dialogue: 0,0:04:54.42,0:04:57.99,Default,,0000,0000,0000,,The first two invariants you know, are\Njust really cosmetic.
Dialogue: 0,0:04:57.99,0:05:01.98,Default,,0000,0000,0000,,So, the first one we're going to store one\Nbit of information additionally at each
Dialogue: 0,0:05:01.98,0:05:06.78,Default,,0000,0000,0000,,node, beyond just the key and we're going\Ncall this bit as indicating whether it's a
Dialogue: 0,0:05:06.78,0:05:09.83,Default,,0000,0000,0000,,red or a black node.\NYou might be wondering, you know, why red
Dialogue: 0,0:05:09.83,0:05:12.46,Default,,0000,0000,0000,,black?\NWell, I asked my colleague, Leo Guibas
Dialogue: 0,0:05:12.46,0:05:16.08,Default,,0000,0000,0000,,about that a few years ago.\NAnd he told me that when he and Professor
Dialogue: 0,0:05:16.08,0:05:20.99,Default,,0000,0000,0000,,Sedgewick were writing up this article the\Njournals were, just had access to a
Dialogue: 0,0:05:20.99,0:05:24.79,Default,,0000,0000,0000,,certain kind of new printing technology\Nthat allowed very limited color in the
Dialogue: 0,0:05:24.79,0:05:28.10,Default,,0000,0000,0000,,printed copies of the journals.\NAnd so, they were eager to use it, and so
Dialogue: 0,0:05:28.10,0:05:32.08,Default,,0000,0000,0000,,they named the data structure red black,\Nso they could have these nice red and
Dialogue: 0,0:05:32.08,0:05:36.03,Default,,0000,0000,0000,,black pictures in the journal article.\NUnfortunately, there was then some snafu,
Dialogue: 0,0:05:36.03,0:05:40.17,Default,,0000,0000,0000,,and at the end of the day, that technology\Nwasn't actually available, so it wasn't
Dialogue: 0,0:05:40.17,0:05:44.04,Default,,0000,0000,0000,,actually printed the way they were\Nenvisioning it but the name has stuck.
Dialogue: 0,0:05:44.04,0:05:47.90,Default,,0000,0000,0000,,So, that's the rather idiosyncratic reason\Nwhy these data structures got the name
Dialogue: 0,0:05:48.06,0:05:51.94,Default,,0000,0000,0000,,that they did, red black trees.\NSo, secondly we're going to maintain the
Dialogue: 0,0:05:51.94,0:05:56.06,Default,,0000,0000,0000,,invariant that the roots of the search\Ntree is always black, it can never be red.
Dialogue: 0,0:05:56.06,0:05:58.09,Default,,0000,0000,0000,,Okay.\NSo, with the superficial pair of
Dialogue: 0,0:05:58.09,0:06:02.04,Default,,0000,0000,0000,,invariants out of the way, let's go to the\Ntwo main ones.
Dialogue: 0,0:06:02.04,0:06:06.02,Default,,0000,0000,0000,,So, first of all, we're never going to\Nallow two reds in a row.
Dialogue: 0,0:06:06.02,0:06:12.82,Default,,0000,0000,0000,,By which, I mean, if you have a red node\Nin the search tree, then its children must
Dialogue: 0,0:06:12.82,0:06:16.01,Default,,0000,0000,0000,,be black.\NIf you think about for a second, you
Dialogue: 0,0:06:16.01,0:06:20.02,Default,,0000,0000,0000,,realize this also implies that if a notice\Nred, and it has a parent, then that
Dialogue: 0,0:06:20.02,0:06:24.08,Default,,0000,0000,0000,,parent has to be a black node.\NSo, in that sense, there are no two red
Dialogue: 0,0:06:24.08,0:06:30.08,Default,,0000,0000,0000,,nodes in a row anywhere in the tree.\NAnd the final invariant which is also
Dialogue: 0,0:06:30.08,0:06:37.05,Default,,0000,0000,0000,,rather severe is that every path you might\Ntake from a root to a null pointer, passes
Dialogue: 0,0:06:37.05,0:06:41.02,Default,,0000,0000,0000,,through exactly the same number of black\Nnodes.
Dialogue: 0,0:06:41.02,0:06:45.96,Default,,0000,0000,0000,,So, to be clear on what I mean by a root\Nnull path, what you should think about is an
Dialogue: 0,0:06:45.96,0:06:49.37,Default,,0000,0000,0000,,unsuccessful search, right?\NSo, what happens in an unsuccessful
Dialogue: 0,0:06:49.37,0:06:53.22,Default,,0000,0000,0000,,search, you start at the root depending on\Nwhether you need to go smaller or bigger,
Dialogue: 0,0:06:53.22,0:06:57.15,Default,,0000,0000,0000,,you go left or right respectably.\NYou keep going left right as appropriate
Dialogue: 0,0:06:57.15,0:07:01.05,Default,,0000,0000,0000,,until eventually you hit a null pointer.\NSo, I want you to think about the process
Dialogue: 0,0:07:01.05,0:07:04.94,Default,,0000,0000,0000,,that which you start at the root and then,\Neventually, fall off the end of the tree.
Dialogue: 0,0:07:04.94,0:07:07.10,Default,,0000,0000,0000,,In doing so, you traverse some number of\Nnodes.
Dialogue: 0,0:07:07.10,0:07:11.03,Default,,0000,0000,0000,,Some of those nodes will be black some of\Nthose nodes will be red.
Dialogue: 0,0:07:11.03,0:07:15.36,Default,,0000,0000,0000,,And I want you to keep track of the number\Nof black nodes and the constraints that a
Dialogue: 0,0:07:15.36,0:07:19.53,Default,,0000,0000,0000,,red black tree, by definition, must\Nsatisfy, is that no matter what path you
Dialogue: 0,0:07:19.53,0:07:24.10,Default,,0000,0000,0000,,take through the tree starting from the\Nroot terminating at a null pointer, the
Dialogue: 0,0:07:24.10,0:07:27.28,Default,,0000,0000,0000,,number of black nodes traversed, has to be\Nexactly the same.
Dialogue: 0,0:07:27.28,0:07:31.79,Default,,0000,0000,0000,,It cannot depend on the path, it has to be\Nexactly the same on every single root null path.
Dialogue: 0,0:07:31.79,0:07:34.56,Default,,0000,0000,0000,,\NLet's move on to some examples.
Dialogue: 0,0:07:34.56,0:07:38.41,Default,,0000,0000,0000,,So, here's a claim.\NAnd this is meant to, kind of, whet your
Dialogue: 0,0:07:38.41,0:07:42.67,Default,,0000,0000,0000,,appetite for the idea that red black trees\Nmust be pretty balanced.
Dialogue: 0,0:07:42.67,0:07:45.74,Default,,0000,0000,0000,,They have to have height, basically\Nlogarithmic.
Dialogue: 0,0:07:45.74,0:07:49.02,Default,,0000,0000,0000,,So, remember, what's the most unbalanced\Nsearch tree?
Dialogue: 0,0:07:49.02,0:07:54.12,Default,,0000,0000,0000,,Well, that's these chains.\NSo, the claim is, even a chain with three
Dialogue: 0,0:07:54.12,0:07:58.39,Default,,0000,0000,0000,,nodes can not be a red black tree.\NSo, what's the proof?
Dialogue: 0,0:07:58.39,0:08:04.96,Default,,0000,0000,0000,,Well, consider such a search tree.\NSo, maybe, with the key values one, two and three.
Dialogue: 0,0:08:04.96,0:08:08.46,Default,,0000,0000,0000,,So, the question that we're asking is, is
Dialogue: 0,0:08:08.46,0:08:13.38,Default,,0000,0000,0000,,there a way to color the node, these three\Nnodes, red and black so that all four of
Dialogue: 0,0:08:13.38,0:08:17.06,Default,,0000,0000,0000,,the invariants are satisfied.\NSo, we need to color each red or black.
Dialogue: 0,0:08:17.06,0:08:20.38,Default,,0000,0000,0000,,Remember, variant two says, the root, the\None has to be black.
Dialogue: 0,0:08:20.38,0:08:24.41,Default,,0000,0000,0000,,So, we have four possibilities for how to\Nuse the color two and three.
Dialogue: 0,0:08:24.41,0:08:27.45,Default,,0000,0000,0000,,But really, because of the third\Ninvariant, we only have three possibilities.
Dialogue: 0,0:08:27.45,0:08:30.25,Default,,0000,0000,0000,,We can't color two and three both red, cuz
Dialogue: 0,0:08:30.25,0:08:34.02,Default,,0000,0000,0000,,then we'd have two reds in a row.\NSo, we can either make two red, three
Dialogue: 0,0:08:34.02,0:08:37.01,Default,,0000,0000,0000,,black, two black, three red, or both two\Nand three black.
Dialogue: 0,0:08:37.01,0:08:41.07,Default,,0000,0000,0000,,And all of the cases are the same.\NJust to give one example, suppose that we
Dialogue: 0,0:08:41.07,0:08:44.08,Default,,0000,0000,0000,,colored the node two, red, and one and\Nthree are black.
Dialogue: 0,0:08:44.08,0:08:48.49,Default,,0000,0000,0000,,The claim is invariant four has been\Nbroken and invariant four is going to be
Dialogue: 0,0:08:48.49,0:08:53.00,Default,,0000,0000,0000,,broken no matter how we try to color two\Nand three red and black.
Dialogue: 0,0:08:53.00,0:08:56.62,Default,,0000,0000,0000,,What is invariant four says?\NIt says, really on any unsuccessful
Dialogue: 0,0:08:56.62,0:09:00.01,Default,,0000,0000,0000,,search, you pass through the same number\Nof black nodes.
Dialogue: 0,0:09:00.01,0:09:03.06,Default,,0000,0000,0000,,And so, one unsuccessful search would be,\Nyou search for zero.
Dialogue: 0,0:09:03.06,0:09:07.08,Default,,0000,0000,0000,,And if you search for a zero, you go to\Nthe root, you immediately go left to hit a
Dialogue: 0,0:09:07.08,0:09:10.03,Default,,0000,0000,0000,,null pointer.\NSo, you see exactly one black node.
Dialogue: 0,0:09:10.03,0:09:12.06,Default,,0000,0000,0000,,Namely one.\NOn the other hand, suppose you searched
Dialogue: 0,0:09:12.06,0:09:15.28,Default,,0000,0000,0000,,for four, then you'd start at the root,\Nand you'd go right, and you go to two,
Dialogue: 0,0:09:15.28,0:09:19.40,Default,,0000,0000,0000,,you'd go right, and you go to three, you'd\Ngo right again, and only then will you get
Dialogue: 0,0:09:19.40,0:09:22.02,Default,,0000,0000,0000,,a null pointer.\NAnd on that, unsuccessful search, you'd
Dialogue: 0,0:09:22.02,0:09:24.06,Default,,0000,0000,0000,,encounter two black nodes, both the one\Nand the three.
Dialogue: 0,0:09:24.06,0:09:28.01,Default,,0000,0000,0000,,So, it's a violation of the fourth\Ninvariant, therefore, this would not be a
Dialogue: 0,0:09:28.01,0:09:30.06,Default,,0000,0000,0000,,red black tree.\NI'll leave that for you to check, that no
Dialogue: 0,0:09:30.06,0:09:34.04,Default,,0000,0000,0000,,matter how you try to code two and three\Nred or black, you're going to break one of
Dialogue: 0,0:09:34.04,0:09:37.00,Default,,0000,0000,0000,,the invariants.\NIf they're both red, you'd break the third
Dialogue: 0,0:09:37.00,0:09:39.02,Default,,0000,0000,0000,,invariant.\NIf at most one is red, you'd break the
Dialogue: 0,0:09:39.02,0:09:42.04,Default,,0000,0000,0000,,fourth invariant.\NSo, that's a non-example of a red-black tree.
Dialogue: 0,0:09:42.04,0:09:44.41,Default,,0000,0000,0000,,So, let's look at an example of a red-black tree.
Dialogue: 0,0:09:44.41,0:09:48.01,Default,,0000,0000,0000,,One, a search tree where you can actually
Dialogue: 0,0:09:48.01,0:09:52.02,Default,,0000,0000,0000,,color the nodes red or black so that all\Nfour invariants are maintained.
Dialogue: 0,0:09:52.02,0:09:56.06,Default,,0000,0000,0000,,So, one search tree which is very easy to\Nmake red black is a perfectly balanced one.
Dialogue: 0,0:09:56.06,0:09:59.01,Default,,0000,0000,0000,,So, for example, let's consider this three
Dialogue: 0,0:09:59.01,0:10:03.05,Default,,0000,0000,0000,,nodes search tree has the keys three,\Nfive, and seven and let's suppose the five
Dialogue: 0,0:10:03.05,0:10:06.02,Default,,0000,0000,0000,,is the root.\NSo, it has one child on each side, the
Dialogue: 0,0:10:06.02,0:10:09.04,Default,,0000,0000,0000,,three and the seven.\NSo, can this be made a red black tree?
Dialogue: 0,0:10:09.04,0:10:11.10,Default,,0000,0000,0000,,So, remember what that question really\Nmeans.
Dialogue: 0,0:10:11.10,0:10:16.05,Default,,0000,0000,0000,,It's asking can we color theses three\Nnodes some combination of red and black so
Dialogue: 0,0:10:16.05,0:10:19.00,Default,,0000,0000,0000,,that all four of the invariants are\Nsatisfied?
Dialogue: 0,0:10:19.08,0:10:24.01,Default,,0000,0000,0000,,If you think about it a little bit, you\Nrealize, yeah, you can definitely color
Dialogue: 0,0:10:24.01,0:10:27.06,Default,,0000,0000,0000,,these nodes red or black to make and\Nsatisfy for the invariants.
Dialogue: 0,0:10:27.06,0:10:31.00,Default,,0000,0000,0000,,In particular, suppose we color all three\Nof the nodes, black.
Dialogue: 0,0:10:31.04,0:10:34.05,Default,,0000,0000,0000,,We've satisfied variant number one, we've\Ncolored all the nodes.
Dialogue: 0,0:10:34.05,0:10:37.10,Default,,0000,0000,0000,,We've satisfied variant number two, and\Nparticularly, the root is black.
Dialogue: 0,0:10:37.10,0:10:41.08,Default,,0000,0000,0000,,We've satisfied invariant number three.\NThere's no reds at all, so there's
Dialogue: 0,0:10:41.08,0:10:45.02,Default,,0000,0000,0000,,certainly no two reds in a row.\NAnd, if you think about it, we've
Dialogue: 0,0:10:45.02,0:10:48.07,Default,,0000,0000,0000,,satisfied invariant four because this tree\Nis perfectly balanced.
Dialogue: 0,0:10:48.07,0:10:52.10,Default,,0000,0000,0000,,No matter what you unsuccessfully search\Nfor, you're going to encounter two black
Dialogue: 0,0:10:52.10,0:10:55.04,Default,,0000,0000,0000,,nodes.\NIf you search for, say, one, you're going
Dialogue: 0,0:10:55.04,0:10:59.00,Default,,0000,0000,0000,,to encounter three and five.\NIf you search for, say, six, you're going
Dialogue: 0,0:10:59.00,0:11:01.91,Default,,0000,0000,0000,,to encounter five and seven.\NSo, all root null paths have exactly
Dialogue: 0,0:11:01.91,0:11:05.08,Default,,0000,0000,0000,,two black nodes and variant number four is\Nalso satisfied.
Dialogue: 0,0:11:05.08,0:11:08.05,Default,,0000,0000,0000,,So, that's great.\NBut, of course, the whole point of having
Dialogue: 0,0:11:08.05,0:11:11.03,Default,,0000,0000,0000,,a binary search tree data structure is you\Nwant to be dynamic.
Dialogue: 0,0:11:11.03,0:11:13.07,Default,,0000,0000,0000,,You want to accommodate insertions and\Ndeletions.
Dialogue: 0,0:11:13.07,0:11:17.05,Default,,0000,0000,0000,,Every time you have an insertion or a\Ndeletion into a red black tree, you get a
Dialogue: 0,0:11:17.05,0:11:19.29,Default,,0000,0000,0000,,new node.\NLet's say, an insertion, you get a new
Dialogue: 0,0:11:19.29,0:11:23.28,Default,,0000,0000,0000,,node, you have to color it something.\NAnd now, all of a sudden, you got to worry
Dialogue: 0,0:11:23.28,0:11:25.48,Default,,0000,0000,0000,,about breaking one of these four\Ninvariants.
Dialogue: 0,0:11:25.48,0:11:28.95,Default,,0000,0000,0000,,So, let me just show you some easy cases\Nwhere you can accommodate insertions
Dialogue: 0,0:11:28.95,0:11:32.06,Default,,0000,0000,0000,,without too much work.\NTime permitting we will include some
Dialogue: 0,0:11:32.06,0:11:35.100,Default,,0000,0000,0000,,optional videos with the notion of\Nrotations which do more fundamental
Dialogue: 0,0:11:35.100,0:11:40.54,Default,,0000,0000,0000,,restructuring of search trees so that they\Ncan maintain the four invariants, and stay
Dialogue: 0,0:11:40.70,0:11:44.16,Default,,0000,0000,0000,,nearly perfectly balanced.\NSo, if we have this red black tree where
Dialogue: 0,0:11:44.16,0:11:48.37,Default,,0000,0000,0000,,everything's black, and we insert, say,\Nsix, that's going to get inserted down
Dialogue: 0,0:11:48.37,0:11:51.05,Default,,0000,0000,0000,,here.\NNow, if we try to color it black, it's no
Dialogue: 0,0:11:51.05,0:11:55.03,Default,,0000,0000,0000,,longer going to be a red black tree.\NAnd that's because, if we do an
Dialogue: 0,0:11:55.03,0:11:59.62,Default,,0000,0000,0000,,unsuccessful search now for, say, 5.5,\Nwe're going to encounter three black
Dialogue: 0,0:11:59.62,0:12:03.46,Default,,0000,0000,0000,,nodes, where if we do an unsuccessful\Nsearch for one, we only encounter two
Dialogue: 0,0:12:03.46,0:12:05.71,Default,,0000,0000,0000,,black nodes.\NSo, that's not going to work.
Dialogue: 0,0:12:05.71,0:12:09.97,Default,,0000,0000,0000,,But the way we can fix it is instead of\Ncoloring the six black, we color it red.
Dialogue: 0,0:12:09.97,0:12:13.54,Default,,0000,0000,0000,,And now, this six is basically invisible\Nto invariant number four.
Dialogue: 0,0:12:13.54,0:12:16.41,Default,,0000,0000,0000,,It doesn't show up in any root null\Npaths.
Dialogue: 0,0:12:16.41,0:12:20.86,Default,,0000,0000,0000,,So, because you have two black nodes in\Nall roots in all paths before, before the
Dialogue: 0,0:12:20.86,0:12:24.28,Default,,0000,0000,0000,,six was there, that's still true now that\Nyou have this red six.
Dialogue: 0,0:12:24.28,0:12:28.99,Default,,0000,0000,0000,,So, all four invariants are satisfied once\Nyou insert the six and color it red.
Dialogue: 0,0:12:28.99,0:12:33.21,Default,,0000,0000,0000,,If we then insert, say, an eight, we can\Npull exactly the same trick, we can call
Dialogue: 0,0:12:33.21,0:12:37.14,Default,,0000,0000,0000,,it an eight red.\NAgain, it doesn't participate in invariant
Dialogue: 0,0:12:37.14,0:12:42.02,Default,,0000,0000,0000,,four at all so we haven't broken it.\NMoreover, we still don't have two reds in
Dialogue: 0,0:12:42.02,0:12:45.07,Default,,0000,0000,0000,,a row, so we haven't broken invariant\Nnumber three either.
Dialogue: 0,0:12:45.07,0:12:50.04,Default,,0000,0000,0000,,So, this is yet another red black tree.\NIn fact, this is not the unique way to
Dialogue: 0,0:12:50.04,0:12:54.09,Default,,0000,0000,0000,,color the nodes of this search tree, so\Nthat it satisfies all four of the
Dialogue: 0,0:12:54.09,0:12:57.08,Default,,0000,0000,0000,,invariants.\NIf we, instead, recolor six and eight
Dialogue: 0,0:12:57.08,0:13:02.00,Default,,0000,0000,0000,,black, but at the same time, recolor the\Nnode seven, red, we're also golden.
Dialogue: 0,0:13:02.00,0:13:05.00,Default,,0000,0000,0000,,Clearly, the first three invariants are\Nall satisfied.
Dialogue: 0,0:13:05.00,0:13:09.01,Default,,0000,0000,0000,,But also, in pushing the red upward,\Nconsolidating the red at six and eight,
Dialogue: 0,0:13:09.01,0:13:13.04,Default,,0000,0000,0000,,and putting it at seven instead, we\Nhaven't changed the number of black nodes
Dialogue: 0,0:13:13.04,0:13:16.04,Default,,0000,0000,0000,,on any given path.\NAny black, any path that previously went
Dialogue: 0,0:13:16.04,0:13:20.07,Default,,0000,0000,0000,,through six, went through seven, anything\Nthat went through eight, went through
Dialogue: 0,0:13:20.07,0:13:24.92,Default,,0000,0000,0000,,seven so there's exactly the same number\Nof red and black nodes on each such path
Dialogue: 0,0:13:24.92,0:13:28.08,Default,,0000,0000,0000,,as there was before.\NSo, all paths still have equal number of
Dialogue: 0,0:13:28.08,0:13:30.84,Default,,0000,0000,0000,,black nodes and invariant four remains\Nsatisfied.
Dialogue: 0,0:13:30.84,0:13:36.60,Default,,0000,0000,0000,,As I said, I've shown you here only simple\Nexamples, where you don't have to do much
Dialogue: 0,0:13:36.60,0:13:39.90,Default,,0000,0000,0000,,work on an insertion to retain the red\Nblack properties.
Dialogue: 0,0:13:39.90,0:13:44.46,Default,,0000,0000,0000,,In general, if you keep inserting more and\Nmore stuff and certainly if you do the
Dialogue: 0,0:13:44.46,0:13:48.77,Default,,0000,0000,0000,,deletions, you have to work much harder to\Nmaintain those four invariants.
Dialogue: 0,0:13:48.77,0:13:52.81,Default,,0000,0000,0000,,Time permitting, we'll cover just a taste\Nof it in some optional videos.
Dialogue: 0,0:13:52.81,0:13:57.75,Default,,0000,0000,0000,,So, what's the point of these seemingly\Narbitrary four invariants of a red black
Dialogue: 0,0:13:57.75,0:14:00.48,Default,,0000,0000,0000,,tree?\NWell, the whole point is that if you
Dialogue: 0,0:14:00.48,0:14:05.48,Default,,0000,0000,0000,,satisfy these four invariants in your\Nsearch tree, then your height is going to
Dialogue: 0,0:14:05.48,0:14:07.84,Default,,0000,0000,0000,,be small.\NAnd because your height's going to be
Dialogue: 0,0:14:07.84,0:14:10.10,Default,,0000,0000,0000,,small, all your operations are going to be\Nfast.
Dialogue: 0,0:14:10.10,0:14:15.70,Default,,0000,0000,0000,,So, let me give you a proof that if a\Nsearch tree satisfies the four invariants,
Dialogue: 0,0:14:15.70,0:14:20.03,Default,,0000,0000,0000,,then it has super small height.\NIn fact, no more than double the absolute
Dialogue: 0,0:14:20.03,0:14:24.04,Default,,0000,0000,0000,,minimum that we conceivably have, almost\Ntwo times log base two of N.
Dialogue: 0,0:14:24.04,0:14:31.00,Default,,0000,0000,0000,,So, the formal claim, is that every\Nred-black tree with N nodes, has height O
Dialogue: 0,0:14:31.00,0:14:36.88,Default,,0000,0000,0000,,of log N, were precisely in those two\Ntimes log base two of N + 1.
Dialogue: 0,0:14:36.89,0:14:41.72,Default,,0000,0000,0000,,So, here's the proof.\NAnd what's clear about this proof is it's
Dialogue: 0,0:14:41.72,0:14:46.09,Default,,0000,0000,0000,,very obvious the role played by this\Ninvariants three and four.
Dialogue: 0,0:14:46.09,0:14:51.91,Default,,0000,0000,0000,,Essentially, what the invariants guarantee\Nis that, a red black tree has to look like
Dialogue: 0,0:14:51.91,0:14:57.01,Default,,0000,0000,0000,,a perfectly balanced tree with at most a\Nsort of factor two inflation.
Dialogue: 0,0:14:57.01,0:15:01.01,Default,,0000,0000,0000,,So, let's see exactly what I mean.\NSo, let's begin with an observation.
Dialogue: 0,0:15:01.01,0:15:03.08,Default,,0000,0000,0000,,And this, this has nothing to do with red\Nblack trees.
Dialogue: 0,0:15:03.08,0:15:08.01,Default,,0000,0000,0000,,Forget about the colors for a moment, and\Njust think about the structure of binary
Dialogue: 0,0:15:08.01,0:15:10.06,Default,,0000,0000,0000,,trees.\NAnd let's suppose we have a lower bound on
Dialogue: 0,0:15:10.06,0:15:14.08,Default,,0000,0000,0000,,how long root null paths are in the tree.\NSo, for some parameter k, and go ahead and
Dialogue: 0,0:15:14.08,0:15:18.08,Default,,0000,0000,0000,,think of k as, like, ten if you want.\NSuppose we have a tree where if you start
Dialogue: 0,0:15:18.08,0:15:22.10,Default,,0000,0000,0000,,from the root, and no matter how it is you\Nnavigate left and right, child pointers
Dialogue: 0,0:15:22.10,0:15:26.08,Default,,0000,0000,0000,,until you terminate in a null pointer.\NNo matter how you do it, you have no
Dialogue: 0,0:15:26.08,0:15:29.03,Default,,0000,0000,0000,,choice but to see at least k nodes along\Nthe way.
Dialogue: 0,0:15:29.03,0:15:34.07,Default,,0000,0000,0000,,If that hypothesis is satisfied, then if\Nyou think about it, the top of this tree
Dialogue: 0,0:15:34.07,0:15:39.03,Default,,0000,0000,0000,,has to be totally filled in.\NSo, the top of this tree has to include a
Dialogue: 0,0:15:39.03,0:15:43.06,Default,,0000,0000,0000,,perfectly balanced search tree, binary\Ntree of depth k - 1.
Dialogue: 0,0:15:43.06,0:15:46.03,Default,,0000,0000,0000,,So, let me draw a picture here of the case\Nof k = three.
Dialogue: 0,0:15:46.03,0:15:50.08,Default,,0000,0000,0000,,So, if no matter how you go from the root\Nto a null pointer, you have to see at
Dialogue: 0,0:15:50.08,0:15:54.10,Default,,0000,0000,0000,,least three nodes along the way.\NThat means the top three levels of this
Dialogue: 0,0:15:54.10,0:15:57.09,Default,,0000,0000,0000,,tree have to be full.\NSo, you have to have the root.
Dialogue: 0,0:15:57.09,0:16:01.07,Default,,0000,0000,0000,,It has to have both of its children.\NIt has to have all four of its
Dialogue: 0,0:16:01.07,0:16:04.08,Default,,0000,0000,0000,,grandchildren.\NThe proof of this observation is by
Dialogue: 0,0:16:04.08,0:16:08.02,Default,,0000,0000,0000,,contradiction.\NIf, in fact, you were missing some nodes
Dialogue: 0,0:16:08.02,0:16:13.02,Default,,0000,0000,0000,,in any of these top k levels.\NWe'll that would give you a way of hitting
Dialogue: 0,0:16:13.02,0:16:18.04,Default,,0000,0000,0000,,a null pointer seeing less then k nodes.\NSo, what's the point is, the point is this
Dialogue: 0,0:16:18.04,0:16:23.09,Default,,0000,0000,0000,,gives us a lower bound on the population\Nof a search tree as a function of the
Dialogue: 0,0:16:23.09,0:16:28.09,Default,,0000,0000,0000,,lengths of its root null paths.\NSo, the size N of the tree must include at
Dialogue: 0,0:16:28.09,0:16:34.32,Default,,0000,0000,0000,,least the number of nodes in a perfectly\Nbalanced tree of depth k - 1 which is
Dialogue: 0,0:16:34.32,0:16:40.09,Default,,0000,0000,0000,,2^k - 1, So, for example,\Nwhen k = 3, it's 2^3 (two cubed) - 1,
Dialogue: 0,0:16:40.09,0:16:45.35,Default,,0000,0000,0000,,or 7 that's just a basic fact about trees,
Dialogue: 0,0:16:45.35,0:16:49.55,Default,,0000,0000,0000,,nothing about red black trees.\NSo, let's now combine that with a red
Dialogue: 0,0:16:49.55,0:16:54.74,Default,,0000,0000,0000,,black tree invariant to see why red black\Ntrees have to have small height.
Dialogue: 0,0:16:54.74,0:16:58.83,Default,,0000,0000,0000,,So again, to recap where we got to on the\Nprevious slide.
Dialogue: 0,0:16:58.83,0:17:04.41,Default,,0000,0000,0000,,The size N, the number of nodes in a tree,\Nis at least 2^k - 1, where k is
Dialogue: 0,0:17:04.41,0:17:08.93,Default,,0000,0000,0000,,the fewest number of nodes you will ever\Nsee on a root null path.
Dialogue: 0,0:17:08.93,0:17:13.50,Default,,0000,0000,0000,,So, let's rewrite this a little bit and\Nlet's actually say, instead of having a
Dialogue: 0,0:17:13.50,0:17:18.37,Default,,0000,0000,0000,,lower bound on N in terms of k, let's have\Nan upper bound on k in terms of N.
Dialogue: 0,0:17:18.37,0:17:23.48,Default,,0000,0000,0000,,So, the length of every root null path,\Nthe minimum length of every root null
Dialogue: 0,0:17:23.48,0:17:26.80,Default,,0000,0000,0000,,path is bounded above by log base two of\Nquantity N + 1.
Dialogue: 0,0:17:26.80,0:17:31.24,Default,,0000,0000,0000,,This is just adding one to both sides and\Ntaking the logarithm base two.
Dialogue: 0,0:17:31.24,0:17:35.36,Default,,0000,0000,0000,,So, what does this buy us?\NWell, now, let's start thinking about red
Dialogue: 0,0:17:35.36,0:17:38.02,Default,,0000,0000,0000,,black trees.\NSo now, red black tree with N nodes.
Dialogue: 0,0:17:38.02,0:17:42.21,Default,,0000,0000,0000,,What does this say?\NThis says that the number of nodes, forget
Dialogue: 0,0:17:42.21,0:17:48.16,Default,,0000,0000,0000,,about red or black, just the number of\Nnodes on some root null path has to be the
Dialogue: 0,0:17:48.16,0:17:52.62,Default,,0000,0000,0000,,most log base two of N + 1.\NIn the best case, all of those are black.
Dialogue: 0,0:17:52.62,0:17:57.24,Default,,0000,0000,0000,,Maybe some of them are red, but in the,\Nin, the maximum case, all of them are
Dialogue: 0,0:17:57.24,0:18:00.06,Default,,0000,0000,0000,,black.\NSo, we can write in a red black tree with
Dialogue: 0,0:18:00.06,0:18:06.18,Default,,0000,0000,0000,,N nodes, there is a root null path with at\Nmost log base two of N + 1, black nodes.
Dialogue: 0,0:18:06.18,0:18:10.75,Default,,0000,0000,0000,,This is an even weaker statement than what\Nwe just proved.
Dialogue: 0,0:18:10.75,0:18:15.50,Default,,0000,0000,0000,,We proved that it have some, somehow must\Nhave at most log based two, n + 1 total
Dialogue: 0,0:18:15.50,0:18:18.34,Default,,0000,0000,0000,,nodes.\NSo, certainly, that path has the most log
Dialogue: 0,0:18:18.34,0:18:21.88,Default,,0000,0000,0000,,base two of N + 1 black nodes.\NNow, let's, now let's apply the two
Dialogue: 0,0:18:21.88,0:18:25.74,Default,,0000,0000,0000,,knockout punches of our two invariants.\NAlright, so fundamentally, what is the
Dialogue: 0,0:18:25.74,0:18:29.17,Default,,0000,0000,0000,,fourth invariant telling us?\NIt's telling us that if we look at a path
Dialogue: 0,0:18:29.17,0:18:33.01,Default,,0000,0000,0000,,in our red black tree, we go from the\Nroot, we think about, let's say, that's an
Dialogue: 0,0:18:33.01,0:18:35.38,Default,,0000,0000,0000,,unsuccessful search, we go down to a null\Npointer.
Dialogue: 0,0:18:35.38,0:18:39.09,Default,,0000,0000,0000,,It says, if we think of the red nodes as\Ninvisible, if we don't count them in our
Dialogue: 0,0:18:39.09,0:18:43.03,Default,,0000,0000,0000,,tally, then we're only going to see log,\Nbasically a logarithmic number of nodes.
Dialogue: 0,0:18:43.03,0:18:47.05,Default,,0000,0000,0000,,But when we care about the height of the\Nred black tree, of course, we care about
Dialogue: 0,0:18:47.05,0:18:49.73,Default,,0000,0000,0000,,all of the nodes, the red nodes and the\Nblack nodes.
Dialogue: 0,0:18:49.73,0:18:54.17,Default,,0000,0000,0000,,So, so far we know, that if we only count\Nblack nodes then we're good, We only have
Dialogue: 0,0:18:54.17,0:18:56.73,Default,,0000,0000,0000,,log base two of N + 1 nodes that we need\Nto count.
Dialogue: 0,0:18:56.73,0:18:59.05,Default,,0000,0000,0000,,So, here's where the third invariant comes\Nin.
Dialogue: 0,0:18:59.05,0:19:04.02,Default,,0000,0000,0000,,It says, well actually, black nodes are a\Nmajority of nodes in the tree.
Dialogue: 0,0:19:04.02,0:19:08.03,Default,,0000,0000,0000,,In a strong sense, there are no two reds\Nin a row, on any path.
Dialogue: 0,0:19:08.03,0:19:12.10,Default,,0000,0000,0000,,So, if we know the number of black nodes\Nis small, then because you can't have two
Dialogue: 0,0:19:12.10,0:19:17.04,Default,,0000,0000,0000,,reds in a row, the number of total nodes\Non the path is at most twice as large.
Dialogue: 0,0:19:17.04,0:19:21.07,Default,,0000,0000,0000,,In the worst case, you have a black route,\Nthen red, then black, then red, then
Dialogue: 0,0:19:21.07,0:19:26.02,Default,,0000,0000,0000,,black, then red, then black, et cetera.\NAt the worst case, the number of red nodes
Dialogue: 0,0:19:26.02,0:19:30.09,Default,,0000,0000,0000,,is equal to the number of black nodes,\Nwhich doubles the length of the path once
Dialogue: 0,0:19:30.09,0:19:35.04,Default,,0000,0000,0000,,you start counting the red nodes as well.\NAnd this is exactly what it means for a
Dialogue: 0,0:19:35.04,0:19:39.00,Default,,0000,0000,0000,,tree to have a logarithmic depth.\NSo, this, in fact, proves the claim, if
Dialogue: 0,0:19:39.00,0:19:43.05,Default,,0000,0000,0000,,the search trees satisfies the invariants\None through four, in particular if there's
Dialogue: 0,0:19:43.05,0:19:47.08,Default,,0000,0000,0000,,no two reds in a row and all root null\Npaths have an equal number of black nodes,
Dialogue: 0,0:19:47.08,0:19:51.06,Default,,0000,0000,0000,,then, knowing nothing else about this\Nsearch tree, it's got to be almost
Dialogue: 0,0:19:51.06,0:19:54.03,Default,,0000,0000,0000,,balanced.\NIt's perfectly balanced up to a factor of
Dialogue: 0,0:19:54.03,0:19:56.02,Default,,0000,0000,0000,,two.\NAnd again, the point then is that
Dialogue: 0,0:19:56.02,0:19:59.83,Default,,0000,0000,0000,,operations in a search tree and the search\Ntrees are going to run in logarithmic
Dialogue: 0,0:19:59.83,0:20:04.04,Default,,0000,0000,0000,,time, because the height is what governs\Nthe running time of those operations.
Dialogue: 0,0:20:04.08,0:20:08.63,Default,,0000,0000,0000,,Now, in some sense, I've only told you the\Neasy part which is if it just so happens
Dialogue: 0,0:20:08.63,0:20:12.19,Default,,0000,0000,0000,,that your search tree satisfies these\Nfour invariants, then you're good.
Dialogue: 0,0:20:12.19,0:20:15.99,Default,,0000,0000,0000,,The height is guaranteed to be small so\Nthe operations are guaranteed to be fast.
Dialogue: 0,0:20:15.99,0:20:18.99,Default,,0000,0000,0000,,Clearly that's exactly what you want from\Nthis data structure.
Dialogue: 0,0:20:18.99,0:20:22.98,Default,,0000,0000,0000,,But for the poor soul who has to actually\Nimplement this data structure, the hard
Dialogue: 0,0:20:22.98,0:20:26.75,Default,,0000,0000,0000,,work is maintaining these invariants even\Nas the data structure changes.
Dialogue: 0,0:20:26.75,0:20:31.08,Default,,0000,0000,0000,,Remember, the point here is to be dynamic,\Nto accommodate insertions and deletions.
Dialogue: 0,0:20:31.08,0:20:35.66,Default,,0000,0000,0000,,And searches and deletions can disrupt\Nthese four invariants and then one has to
Dialogue: 0,0:20:35.66,0:20:40.02,Default,,0000,0000,0000,,actually change the code to make sure\Nthey're satisfied again, so that the tree
Dialogue: 0,0:20:40.02,0:20:44.38,Default,,0000,0000,0000,,stays balanced, has low height, even under\Narbitrary sequences of insertions and
Dialogue: 0,0:20:44.38,0:20:46.77,Default,,0000,0000,0000,,deletions.\NSo, we're not going to cover that in this
Dialogue: 0,0:20:46.77,0:20:49.02,Default,,0000,0000,0000,,video.\NIt can be done, without significantly
Dialogue: 0,0:20:49.02,0:20:53.05,Default,,0000,0000,0000,,slowing down any of the operations.\NIt's pretty tricky, takes some nice ideas.
Dialogue: 0,0:20:53.05,0:20:57.05,Default,,0000,0000,0000,,There's a couple well-known algorithms\Ntextbooks that cover those details.
Dialogue: 0,0:20:57.05,0:21:00.07,Default,,0000,0000,0000,,Or if you look at open source and\Nlimitations of balanced search trees, you
Dialogue: 0,0:21:00.07,0:21:02.61,Default,,0000,0000,0000,,can look at code that does that\Nimplementations.
Dialogue: 0,0:21:02.61,0:21:07.15,Default,,0000,0000,0000,,But, because it can be done in a practical\Nway and because Red Black Tree supports
Dialogue: 0,0:21:07.15,0:21:11.51,Default,,0000,0000,0000,,such an original array of operations,\Nthat's why you will find them used in a
Dialogue: 0,0:21:11.51,0:21:15.28,Default,,0000,0000,0000,,number practical applications.\NThat's why balanced search trees should be
Dialogue: 0,0:21:15.28,0:21:17.05,Default,,0000,0000,0000,,part of your programmer tool box.