2-3 Tree Insertion

distanceedjohn
6 Mar 200808:00

Summary

TLDR本视频脚本详细介绍了如何将一系列值插入一个新创建的空2-3树。首先插入的值成为树的根节点,随后的值根据大小插入相应的叶子节点或内部节点。当节点满时,会进行分裂操作,将中间值提升到父节点,并重新调整子节点。通过这个过程,始终保持树的有效性,最终形成一个完整的2-3树。

Takeaways

  • 🌟 插入序列值到一个新的空的2-3树中。
  • 📌 初始时,根节点为空,插入的第一个值50将成为树的根节点和唯一的叶子节点。
  • 🔄 插入第二个值60时,直接添加到现有节点中,因为它有空间。
  • 🌐 插入第三个值70时,由于节点已满,需要进行拆分,并创建新的根节点。
  • 🔢 插入值40和30时,它们都小于60,可以直接添加到左侧的叶子节点中。
  • 🔄 当插入值20和10时,由于节点已满,需要进行拆分,并将中间值推到父节点。
  • 🌳 插入值80和90时,它们都大于40且小于70,但插入90时需要再次拆分,并将80推到父节点。
  • 🏁 最后插入值100,由于有足够的空间,它可以直接添加到现有的节点中。
  • 📈 在整个插入过程中,始终保持2-3树的有效性。
  • 🔑 每个节点最多包含两个键值和一个指针,最少包含一个键值。
  • 🎯 插入操作始终在叶子节点进行,保持了2-3树的平衡性。

Q & A

  • 二三树的初始状态是什么?

    -二三树初始状态为空,根节点为null。

  • 插入第一个值50时,会发生什么?

    -插入第一个值50时,会创建一个新的节点,这个节点既是树的根节点也是唯一的叶子节点。

  • 插入第二个值60后,60会被添加到哪里?

    -插入第二个值60后,60会被添加到现有的节点中,因为该节点有空间容纳60。

  • 插入第三个值70导致什么操作?

    -插入第三个值70时,因为节点已满,需要进行分裂操作,并创建一个新的根节点。

  • 在插入过程中,如何保持二三树的有效性?

    -在插入过程中,每次插入后都会检查节点是否满足二三树的性质,即左子节点的值小于中间值,中间值小于右子节点的值。

  • 插入值40和30时,它们会被添加到哪里?

    -插入值40和30时,它们会被添加到包含60的节点的左侧,因为它们的值小于60。

  • 当插入值20和10时,它们会被添加到哪里?

    -插入值20和10时,它们会被添加到包含30的叶子节点中,因为它们的值小于30,且该节点有空间。

  • 插入值10后,为什么需要进行操作?

    -插入值10后,因为节点已满,需要将中间值20推上到父节点,并将10作为新的左孩子节点。

  • 插入值80和90后,为什么需要进行节点分裂?

    -插入值80和90后,因为节点已满,需要进行节点分裂,将中间值80推上到父节点,并创建新的节点来存放90。

  • 最后一个值100是如何被添加到树中的?

    -最后一个值100因为大于80,所以被添加到包含90的节点中,因为那里有空间。

  • 在插入过程中,如何确保二三树的平衡?

    -在插入过程中,每次插入新值或者进行节点分裂时,都会按照二三树的性质重新调整节点,确保树始终保持平衡。

Outlines

00:00

🌳 二三树插入过程概述

本段落介绍了二三树的基本概念和插入过程。首先,插入一个值为50的节点作为树的根节点。随后,按照二三树的性质,依次插入60和70,其中60成为叶子节点,而70由于无法放入现有节点,触发节点分裂,创建了一个新的根节点。接下来,继续插入40、30、20、10等值,每次插入都遵循二三树的规则,当节点满时进行分裂,将中间值提升到父节点。这个过程确保了在任何插入操作中,二三树始终保持有效状态。

05:06

📈 插入操作的详细步骤

此段落详细描述了插入操作的具体步骤。首先,插入80和90的值,80作为叶子节点的最后一个值,而90由于没有足够的空间,导致节点分裂,80被提升到父节点。最后,插入100的值,它直接插入到现有的节点中,完成了二三树的构建。整个过程中,每次插入都保持了二三树的性质,即左子节点的值小于中间值,中间值小于右子节点的值。

Mindmap

Keywords

💡二三树

二三树是一种特殊的平衡搜索树,每个节点最多包含两个键(或值)和三个子节点。在视频中,二三树用于展示数据的插入过程,如何保持树的平衡,以及在插入新值时如何进行节点的分裂和调整。

💡根节点

根节点是树的顶部节点,它是树的起始点。在二三树中,根节点可以包含一个或两个键,并且可以有两个或三个子节点。视频中提到,当插入第一个值50时,创建了一个新的节点,它既是根节点也是唯一的叶子节点。

💡叶子节点

叶子节点是没有子节点的节点,在二三树中,叶子节点可以包含一个或两个键。视频中提到,当插入60和70时,它们被添加为叶子节点,而插入40、30、20和10时,这些值则被插入到已有的叶子节点中。

💡节点分裂

当二三树中的节点满时(包含两个键和两个子节点),插入新值会导致节点分裂。分裂过程中,节点的中间值会被提升到父节点,同时创建新的子节点以保持树的平衡。视频中详细描述了插入70、40、30、20和10时的节点分裂过程。

💡插入

插入是指将新的键或值添加到二三树中的操作。插入操作需要遵循特定的规则,以保持树的有序性和平衡。视频中详细展示了如何将一系列值插入到二三树中,并在必要时进行节点分裂。

💡

在二三树中,键是存储在节点中的值,每个节点可以包含一个或两个键。键的顺序决定了树的结构和插入、分裂等操作的进行。

💡子节点

子节点是与父节点直接相连的节点。在二三树中,每个节点最多可以有三个子节点。子节点的存在和数量是维持树结构和平衡的关键。

💡平衡

平衡是指二三树在插入和删除操作后仍然保持的一种状态,其中所有叶子节点都在同一层,且除了根节点外,所有节点都恰好包含一个或两个键。视频中强调了在插入过程中始终保持树的平衡。

💡左孩子

左孩子是指节点的左侧子节点。在二三树中,左孩子的键小于其父节点的键。视频中提到,当进行节点分裂和键提升时,左孩子的相对位置保持不变。

💡右孩子

右孩子是指节点的右侧子节点。在二三树中,右孩子的键大于其父节点的键。视频中提到,在节点分裂或键提升时,右孩子的相对位置也会保持不变。

💡中值

中值是指在节点分裂过程中,节点中的中间键值。当节点满时,中值会被提升到父节点,而左右两个子节点的值则分别小于和大于中值。

Highlights

介绍了如何向一个空的2-3树中插入一系列值。

插入第一个值50时,会创建一个新的节点,它既是根节点也是唯一的叶子节点。

插入第二个值60时,它会成为现有节点的一部分,因为有足够的空间。

插入第三个值70时,由于节点已满,需要进行分裂,并创建一个新的根节点。

值60被提升为新根节点的一部分,而值50和70分别成为左右子节点。

插入值40时,它会被添加到左侧的叶子节点中,因为40小于60。

插入值30时,尽管它小于60,但当前叶子节点已满,需要进行节点分裂。

值40被提升到父节点,而值30成为新的左孩子节点。

每次插入操作后,2-3树都保持有效,左孩子小于T,右孩子大于T。

插入值20和10时,它们都小于40,并且可以被添加到现有的叶子节点中。

当插入值10时,由于没有更多空间,需要将中间值40提升到根节点,并创建两个新的节点。

值80和90的插入导致进一步的节点分裂,形成更复杂的树结构。

最后插入的值100很容易地被添加到现有的节点中,因为它大于40、80,且小于已存在的所有值。

整个插入过程中,始终保持了2-3树的特性,即每个节点最多有两个键值和一个子指针。

通过这个过程,展示了2-3树的动态插入和自我平衡的能力。

插入操作的每一步都详细说明了节点如何被创建、分裂和重新组织。

这个讲解提供了对2-3树数据结构的深入理解,特别是关于它的插入机制和维护树的平衡。

Transcripts

00:02

welcome to the comp 21:40 walkthrough on

00:05

two three tree insertion what we're

00:08

going to be doing is we're going to be

00:10

inserting a sequence of values into a

00:12

new empty two three tree

00:14

now since the tree is empty our initial

00:18

root node is going to be null so the

00:22

first value we insert 50 is going to

00:26

require a new node be created for it and

00:36

that's going to be both the root of our

00:39

tree and the only leaf node contained in

00:41

our tree now the second value we insert

00:44

60 is going to be inserted a leaf and

00:47

since there's already room for the value

00:49

60 inside of this node we're simply

00:51

going to add it to the existing node now

00:57

the third value we insert 70 is not

00:59

going to fit in this node so when we try

01:04

to insert it we're going to be required

01:05

to perform a split now in this case

01:08

because the node is also a root node a

01:10

split is going to require the creation

01:13

of a new root node for our tree now

01:17

we're going to take the middle of the

01:18

three values that we've inserted so in

01:24

this case 60 and push it up into the new

01:27

root node of the tree

01:34

the valley to the left of it is going to

01:37

in this case just stay where it is

01:39

because it's going to be the left child

01:40

and the value to the right of it is

01:43

going to be moved to the right child

02:00

the next value we insert 40 we're going

02:04

to look for the correct leaf node to

02:05

insert it into now since 40 is less than

02:08

60 it's going to be on the left of this

02:10

node which means that we're going to try

02:12

to insert it into this leaf node well as

02:17

it turns out there's room for it so all

02:19

we have to do is add the valley to that

02:27

node the next value we insert 30 is also

02:31

less than 60 so we're also going to try

02:34

to insert it into the same leaf node

02:37

however in this case there's not room

02:40

for it so what we're going to need to do

02:42

is we're going to need to take again the

02:44

middle of the three values and push it

02:50

up to the parent now in this case the

02:53

parent only contains one value so we

02:56

don't need to perform a split likely

02:58

like we did before

02:59

instead all we're going to need to do is

03:01

move the value 40 up into the parent

03:04

node now the value on the left the

03:07

smaller value again is going to be the

03:09

left child and the value on the right

03:12

the larger value is going to stay as the

03:15

right child so 40 gets moved up into the

03:23

parent just redraw this a little bit to

03:29

make it neater

03:40

and there we go now pause for a second

03:45

and take a look as you can see at any

03:48

point in this insertion process we're

03:50

always going to be left with a valid two

03:52

three tree so in other words here the

03:55

leftmost child 30 is less than the value

03:57

for T the value 50 is in between 40 and

04:00

60 and the value 70 the right child is

04:02

greater than 60 the next number we

04:06

insert 20 again is less than 40 so it's

04:09

going to be going in this child over

04:11

here since this is a leaf node and since

04:16

there is room for it we can simply add

04:18

the value 20 to this existing node for

04:28

the next value we insert 10 well once

04:32

again 10 is less than 40 so we're going

04:34

to be inserting it into this node as

04:36

well but once again in this case there's

04:38

no longer any room for it so we're going

04:40

to have to take the middle value of the

04:43

3 and try to push it up now as we can

04:47

see there's not going to be any room for

04:49

it in the parent so this is going to

04:50

require a little bit more work so let's

04:53

take a new node here that's going to be

04:55

the left child it's going to contain

05:05

10 the value 20 is going to get pushed

05:09

up into the parent in this case the root

05:14

but there's not going to be any room for

05:16

it now since this is a root node and

05:19

since we're splitting the root node it's

05:20

going to require the creation of two new

05:23

notes so the first of these two new

05:25

notes is going to contain the value

05:30

that's the smallest of these three

05:33

values in other words 20 and the middle

05:37

of these three values is going to get

05:38

pushed up into the new root node of our

05:41

tree so 40 is moved up into the new root

05:51

node of the tree its left child will be

06:00

20 hits right child will be this node

06:02

containing 60 and then 20 will have left

06:06

and right children 10 and 30 all right

06:13

the next value we insert 80 well 80 is

06:17

greater than 40 which means that it's

06:18

going to be on this side of the tree 80

06:20

is greater than 60 which means it's

06:22

going to be in this child and since

06:25

we're always inserting into a leaf node

06:26

well we found our way down to a leaf

06:28

node and there's room in this leaf node

06:30

so we can simply add 80 to this existing

06:33

node of the tree the next value we

06:36

insert 90 is also going to fit to this

06:39

same node

06:41

except of course there's no room for it

06:43

which means that we're going to have to

06:45

take the middle of three values once

06:46

again and push it up so 80 is going to

06:50

be pushed up into the parent the value

06:53

on the left will stay where it is the

06:55

value on the right the greater of the

06:57

three values 90 is going to be moved

07:00

into this new node that we create for it

07:03

and when 80 gets pushed up into the

07:06

parent well this node over here is now

07:09

going to have three children and let's

07:12

just redraw it to make it clearer then

07:15

in fact this is going to be less than 60

07:18

this value here is going to be between

07:22

60 and the value we pushed up which is

07:25

80 and this child over here contains

07:34

value greater than 80 which is 90 so the

07:37

last value we insert 100 is going to be

07:39

an easy one 100 is greater than 40 100

07:42

is greater than 80 and 100 fits neatly

07:46

into this existing node over here and

07:48

now our 2-3 tree is complete

Rate This

5.0 / 5 (0 votes)

Related Tags
数据结构2-3树插入操作树结构编程教程算法理解动态平衡技术教学计算机科学数据存储
Do you need a summary in English?