- First, familiar yourself with the
implementation of
the 2,4-tree ---
you will need to know every detail
to do this project.
The implmentation of the 2,4-tree are found in these files:
- The Tree24.java Prog file: click here
- The Node.java Prog file: click here
- The Entry.java
Prog file:
click here
- A test program for 2,4-tree TestProg24.java Prog file: click here
The above files implement the 2,4-tree
- Your assignment (if you choose to accept it) is
to implement the a,b-tree
where a and
b can be any value
(provided that:
2 ≤ a ≤ (b+1)/2).
- An a,b-tree is a
multiway tree where each
internal node has
between a and
b subtrees:
(I.e., the number of entries stored in a node is between a−1 and b−1)
The a,b-tree is a generalization of the 2,4-tree
The same techniques used to maintain the 2,4-tree canbe generalized to maintain a a,b-tree.
- An a,b-tree is a
multiway tree where each
internal node has
between a and
b subtrees:
- This webpage explains it very briefly:
click here
- You don't need to modify Entry.java
- You need to modify (and turn in)
Node.java
and create an a,b-node
- You need to write the (empty) methods in
TreeAB.java:
click here
- I have a test program for 3,7-tree TestProgAB1.java Prog file: click here
- And a test program for 3,8-tree
TestProgAB2.java
Prog file:
click here
(I will expand the test suit later in the semester - down load a new copy toward the end of the semester)
- Use these commands to turn in:
/home/cs323000/turnin TreeAB.java pjX /home/cs323000/turnin Node.java pjXa
- I will not offer any help in the bonus assignment - except explaining concepts.