This lab will focus on the Adelson-Velsky and Landis (AVL) tree data structure.
We will learn about the implementation you will be working with as well as going
over the benefits of using an AVL tree.
Task 1: Learn about the implementation you will be working with.
Task 2 (2 marks): Write the code for the
– leftRotate and
methods of the AVL tree implementation found in AVLTree.java. All items are
assessable (this lab does not contain non-assessable items).
You are allowed to add any additional helper methods, fields, etc, in the
AVLTree.java. Do not change existing methods signatures and make sure you
genuinely pass the provided test cases. If you are unsure about the changes you
have made, ask your tutor.
Task 1: Immutability 1
There are many benefits to immutable data structures. Just a few that you will
possibly learn about later either in this course or at ANU include:
– Less side effects and strange bugs.
– Greater persistent data safety.
– Protection against null pointer reference errors.
– The greater thread safety provided in concurrent environments.
These benefits often make immutable data structures preferred in many
Task 1: Immutability 2
Our implementation of a tree data structure is ‘immutable’. That is, the object state cannot be
modified (or at least should not be) after it is created.
To change or set values then, we must change our reference to a new object. For example, if we
Tree<Integer> bst = new BinarySearchTree<>(1);
We will print a tree with only the value ‘1’. Our insert did not change the original data structure.
In order to change the original data structure we would need to change our reference:
bst = bst.insert(2);
This will be important to note when you write the AVL tree insertion method.
Task 1: Our AVL Tree
We assume you know what AVL trees are. Encase online resources you have used differ from our
implementation though, the specifics of our implementation are included in a markdown file called
readme.md within the lab 4 folder (for example: our implementation will ignore duplicate values).
To help you get an overview our implementation, you can find a diagram in the next slide (which is the
same as your ‘Lab 4 Diagram’.png file in the lab 4 folder).
Lastly, if you are having a hard time visualising how insertion would work, our friends at the University
of San Francisco have you covered!
You can visualise AVL trees using the link:
You can visualise Binary Search Trees (BSTs) using the link:
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx