Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
學位
證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

2−3 Search Trees

Loading...

算法，第一部分

普林斯顿大学

4.9（5,337 個評分） | 410K 名學生已註冊

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free. It does not offer a certificate upon completion.

查看授課大綱

您將學習的技能

Data Structure, Algorithms, Java Programming

審閱

4.9（5,337 個評分）

5 stars
5,002 ratings
4 stars
287 ratings
3 stars
28 ratings
2 stars
7 ratings
1 star
13 ratings

RP

Jun 11, 2017

Incredible learning experience. Every programmer in industry should take this course if only to dispel the idea that with the advent of cloud computing exponential algorithms can still ruin your day!

GG

Nov 01, 2016

Extremely well designed course. The assignments touch all the concepts taught in the class. Lot of concepts get clarified when you try to reach 100% on each assignment. Highly recommend this course.

從本節課中

Balanced Search Trees

In this lecture, our goal is to develop a symbol table with guaranteed logarithmic performance for search and insert (and many other operations). We begin with 2−3 trees, which are easy to analyze but hard to implement. Next, we consider red−black binary search trees, which we view as a novel way to implement 2−3 trees as binary search trees. Finally, we introduce B-trees, a generalization of 2−3 trees that are widely used to implement file systems.

2−3 Search Trees16:55

Red-Black BSTs35:30

B-Trees (optional)10:37

教學方

Kevin Wayne
Phillip Y. Goldman '86 Senior Lecturer
Robert Sedgewick
William O. Baker *39 Professor of Computer Science

腳本

Welcome back, today we're going to talk about balance search trees,

Which will lead us to an ultimate symbol table implementation that can provide fast

performance for all the simulative options we've looked at, guaranteed.

So here's the review of where we were with single tables.

We took a look at the last time at the binary search tree,

Which if things are well modeled by random exertions, have a great performance.

They get search and insert on in time proportion for log base two of N and they

support ordered operations. But really our goal is to have these

operations be guaranteed to take time proportional to log N,

Because we don't have control over the order of operations and they may not be

random at all. And in fact, in many real applications,

they're not very random. So that's what were going to look at now

is try to find an implementation that can guarantee to be fast for all the symbol

table operations. .

That's our challenge. So what we're going to talk about to do

it, is an algorithm, that actually pretty old algorithm called 2-3 trees, and a

particular implementation that requires very little code, called left leaning red

black BSTs and then we'll talk about a generalization called B-trees. And these

methods are all widely used throughout our computational infrastructure.

To start, we'll talk about 2-3 search trees, which is a model that underlies the

concise and efficient implementation that we're going to look at.

So, the 2-3 tree is a way to generalize BSTs to provide the flexibility that we

need to guarantee fast performance. And the idea is very simple,

We allow one or two keys per node. That is, we allow for the possibility of

something called a 3-node that can hold two keys,

But then it has to have three children. In a regular BST node, the 2-node, we have

one link for the keys that are less than the key in the node, and one link for the

keys that are greater. In a 3-node, we need three links, one for

less, one for between and one for greater. Another property of these 2-3 trees is

that we are going to have perfect balance, That is every path from the route to a

null link is going to have the same link in the 2-3 tree.

So, as I mentioned, the symmetric order is part of the definition of a 2-3 tree.

Every 3-node has three links and two keys. The left link is for the keys that are,

points to a 2-3 tree with the keys that are smaller than the smaller of the two

keys in the 3-node. The middle link points to a 2-3 tree that

contains all the keys that are between the two keys.

And the right link points to all, 2-3 tree containing all the keys that are larger

than the larger of the two keys in the 3-node.

Okay, let's take a look at a demo of searching in a 2-3 tree.

So say we have this 2-3 tree here and we want to search for whether or not H is one

of the keys in the tree. So we start at the root,

Compare the search key against the key or keys in the node.

And follow the link corresponding to the interval that we know must contain the

search key by definition of the tree and then we recursively continue the search.

So, if we're looking for H, it's less than M, so the only place it could be in this

2-3 tree is in the 2-3 tree on the left link,

So we follow the left link. Now, we compare H with E and J, and in

this case it's between, so now we are going to take the middle link, that's the

only place that H possibly could be. In this case, that node, one node 2-3 tree

contains H, so that's a search hit. Let's take another example for

unsuccessful search, a key that's not in the tree.

As usual, we start at the root. It's less, so we go left.

And it's less than both keys, So, if it's in the tree, it would have to

be in the left link and it's between those two keys.

So if it's in the tree, it would have to be on the middle link.

And that link is null, so that's a search miss.

So the search is a natural generalization of the search in, binary search trees.

Now what about inserting? Well, it's a similar type of strategy as

with regular binary search trees, except that we manipulate the two and 3-node to

keep perfect balance in the tree. So the easy case is if the key winds up in

a 2-node at the bottom, like this one. Suppose we're inserting K. K is less than

M so we go left. K is greater than both the keys, so we go

right. K is less than L, so the search ends at

the left link of L. And to perform an insertion all we need to

do is replace that 2-node with a 3-node containing K.

Now, K is inserted into the 2-3 tree and it satisfies all the rules.

Now if we're inserting into a 3-node at the bottom, we have to do more work.

And specifically, the work we do is, we add the key to a 3-node to create a

temporary 4-node and then split up that four node and move it's middle key into

the parent. So, let's see an example.

If we are going to insert Z into this tree, it's greater than N, so we go to the

right. It's greater than R, so we go to the right. And now it's greater than x,

and that's a null link to the right of x, so the search ends there and are, what we

want to do is insert Z into that 3-node. And the way we do it is, first make a

temporary 4-node that replaces that 3-node.

And then that's not a 2-3 tree cuz it's got that one 4-node with three keys and

four links. But what we can do is split that 4-node

and pass the middle key up to its parent. So split into two 2-node and pass the

middle key to the parent. That's kind of a magical operation and

believe me, it's easier to get done in the implementation than the graphics.

But now you can see that, that local transformation on the 2-3 tree completes

the insertion. Now, if that parent were a 3-node, it

would become a temporary 4-node and would continue the process moving up the tree.

That's a demo of search and insertion in a 2-3 tree.

So, let's look at a double split like that.

So, say we're inserting L in, into this tree.

So, it goes down to the middle, and winds up needing to be inserted in the, 3-node

in the middle. So we're going to convert that into a

4-node. Now, L is the middle key of that one,

So we're going to split that 4-node into, two 2-nodes and move L to the parent.

The 4-node had four links, and the two 2-nodes have four lengths, so nothing has

to be changed below. And then this insertion into the parent

changed it from a two, a 3-node into a 4-node essentially adding a length cuz of

the split with the two 2-nodes where there was only one 3-node before.

But now, that's not a 2-3 tree, so we have to split again.

And in this case there is no paren, so we create a new one and the height of the

tree increases by one. That's the only time the height of a 2-3

tree changes, when the roots splits the height introduces increases by one.

So, that's a demo of insertion into a 3-node at the bottom, in a 2-3 tree that

percolates all the way to the top. Now let's look at constructing a 2-3 tree

from an initially empty tree. So if we start by just inserting a key,

well, that just creates a 2-node containing that key, and that's legal 2-3

tree, so we're fine. Now, inserting E into that well, it's

going to B if it's in the tree left of S, that's a null lin. So we need to convert

that 2-node into a 3-node. Okay? And that's the legal of 2-3 trees,

So we stop inserting A into that. We convert that 3-node into a temporary

4-node, but then we need to split that 4-node moving E to the parent and that

creates a new, root node and increases the size of the tree by one, But now that's a

legal 2-3 tree so we stop. Insert R into that, it goes to the right

of E. Convert into a 3-node,

Now insert C into that. it goes to the left of E, has to be joined with A into a

new 3-node. Again, that's a legal 2-3 tree and we

stop. Now we insert H, that kind of goes to the

right of E. That 3-node gets converted into a 4-node.

That's a temporary 4-node and we split and move R to the parent,

Now that parent's a legal and there's nothing more to be done.

We, have a legal three tree, 2-3 tree. Insert X,

It's bigger than R, Goes to the right.

There's a 2-node, there's room for the X. Insert P,

That goes between E and R. The 2-node containing H,

Right link is null, So we convert that 2-node into a 3-node

and now we have a legal 2-3 tree. Now, you, you can see this next insertion

is going to cause some splitting wherever it is.

So insert L, That's between E and R.

So it goes in the, 3-node containing H and P and we convert that into a temporary

4-node. Split that 4-node, moving L to the parent.

Now that parents of 4-node and that has to be split,

And we create a new root node. And then the height of the tree grows by

one. And that's a legal 2-3 tree, so we stop.

So, those local transformations, converting a 2-node to a 3-node or

converting a three to a four, and then splitting and passing a node up.

Those are the, only operations we need to consider to get balance in our search

trees. Alright.

So as I've mentioned and this diagram shows, the splitting of 4-node and a 2-3

tree is a local transformation. It only involves changing a constant

number of links. So, in this example, it shows the general

situation, when the 4-node to be split is the middle length,

But the same is true if it's a left or right.

And those six subtrees drawn could be huge.

They could contain millions of keys, But it doesn't matter what they contain.

We don't touch them at all, Nor do we touch anything above this node

in the tree until the split happens. So the transformation that splits that b,

c, d, node and inserts the C into the 3-node at the root, just involves, making

that 3-node into a temporary 4-node. And making that, 4-node into two 2-nodes

and adjusting the lengths appropriately. Just a constant number of operations and

that's why, this operation, is, in general, efficient. so let's look at the

just the global properties that these manipulations preserve.

The two things that are critical is that the, in a, in a 2-3 tree, we always have

symmetric order. That is the word that we defined, for

2-nodes and 3-nodes, and we also have the perfect balance.

The distance from the root to the bottom is always the same.

And to prove that, we just need to show that each transformation maintains

symmetric order and perfect balance, and these are all the possible transformations

that we could do. If we split the root, then, that's the,

what happens at the root, and if there was perfect balance before, there's perfect

balance after, with the height one bigger. If the parent was a 2-node then the

transformation is a local transformation and if you look at where the links are,

then it's easy to see by induction that if there was perfect balance before there's

perfect balance afterward, Because we didn't change anything about

the perfect balance in any of those subtrees.

And that's true in every case. If the 3-nodes at the right and this one

is one higher and those four are one lower and afterwards it's the same.

If there was perfect balance before there's perfect balance afterwards,

because we didn't change the height of any nodes.

We just moved things around locally within nodes.

And this is when this parent is a 3-node, then there's the tree cases,

If we split up the last split at the middle and split at the right,

And again, changing the four node to, to a 2-nodes and adding links.

If there was perfect balance before, there's perfect balance after, because we

didn't change the heights of anything else in the tree.

So our operations maintain symmetric order and perfect balance in a 2-3 tree.

So, that's going to give us, a very easy way to describe a performance.

The call, or operations have costs that's proportional to the path link from the,

height to the bottom, and every path from the root to a null link has the same

length. How long can those paths be?

Well, it's not hard to see that the, in the worst case, if they're all 2-nodes,

that's the longest they can be is log base two of N.

Now, and if they're all 3-nodes, it would be log base three of N, which is less,

It's about 0.63 log base two of N. So, all the paths in a 2-3 tree with N

nodes have to have length between those two bounds and those are pretty small

numbers. For a million nodes, that's between twelve

and twenty. And, if, if it's a billion nodes, that's

between eighteen and 30. Those are remarkably small numbers, so

we're going to have guaranteed performance, even for huge databases,

We're going to be able to guarantee that we can get search and insert them with

just eighteen to 30 operations and it's quite remarkable, really.

So, here's what our table, will look like, when we finish the implementation of 2-3

trees. Every operation is guaranteed to be a

constant times log n. Now, the constant depends on the

implementation, exactly what kind of manipulations we need to do to convert,

3-nodes to 4-nodes and so forth. But it's, easy to see from demo and from

the diagrams that those are going to be constant, guaranteed logarithmic

performance for all operations, which is certainly what we want in a symbol table

implementation Now what about the implementation?

Well, we're actually not going to talk about a direct implementation of 2-3

trees, because it's kind of complicated. It's cumbersome to maintain multiple node

types. You might need, a multiple compares to

move down the tree. If there's a two, a 3-node, it takes more

compares than a 2-node, So, it's complicated to analyze.

We have to take track, keep track the links as we go up and down the tree to

take, handle the splitting, And there's, and there's a lot of cases.

I drew all the cases and, and, there's a, whether you're splitting into the middle

of a 4-node or the right of a 2-node, there's just a lot of cases.

So, you could do it but we're not going to because there's a much easier way.

So that's 2-3 trees, A, a model for implementing balanced trees

in guaranteed logarithmic time.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司