[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 04:24:09 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

Tables:   2-3-, 2-3-4- & B-Trees:   Introduction

Yet more tree structures for implementing lookup tables:

Height balanced, operations have O(log(n))-time complexity.

B-trees are very important for large (disc) collections (data-bases).

Binary search tree (and AVL tree) have

2-3-trees have

NB. Ordered left-right like a BST.
NB. Two kinds of 2-3-tree:
  1.   elements proper go in fork nodes or
  2.   fork nodes form an index to "real" elements (elsewhere).
©
L
.
A
l
l
i
s
o
n

2-3-tree,   insert an element:

[lecturer: do insertion examples; class: take notes!]

2-3-tree:

©
L
.
A
l
l
i
s
o
n

2-3-4-tree:

2-3-4-tree

This is done by:

[lecturer: draw diagram; class: take notes!]

B-tree of order-k is the logical generalisation of 2-X-trees.

The B-tree structure is popular for very large data sets

Tables:   2-3-, 2-3-4- & B-Trees:   Summary


Prepare

© L.Allison, Sunday, 28-Nov-2021 04:24:09 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/12.234B.shtml
Computer Science, Software Engineering, Science (Computer Science).