IT 279: Algorithms and Data Structures, Week 4 Search Trees

Progress Check on AVL Search Trees

1. Which of the following is NOT true of Abstract Data Types (ADTs)? C

a. An ADT can be implemented using a class in C++.

b. ADTs describe both data and the operations on the data.

c. An ADT is always specific to a particular programming language.

d. Dynamic arrays and linked lists are two different ways to implement the LinearList ADT.

 

 

2. Which of the following will result from inserting 15 into the AVL tree pictured above?

double rotation; While the tree does not become imbalanced at 10, we do have issues further up the tree. We would have an imbalance at the 20, coming from 20's left and 10's right. That would lead to a double rotation.

 

3. Which of the following will result from inserting 26 into the AVL tree pictured above?

We would actually be rotating to the right. The imbalance would occur at the 30, and would come from the left of 30 and the left of 28. Since both are left, we do a single rotation toward the right.

 

Splay Trees

Insertion and deletion are the same as basic binary search trees

Search time will range from O(log n) to O(n) but when we search we will rearrange the tree

m searches will take O(m log n) time as long as m is reasonably large.

 

Splay Tree Search Process

Search to locate the item

Rotate the item to the root

-> Good for problems with frequent repetition of the same lookup

Locality of reference

Routing tables

Memory caching and allocation

Garbage collection

Data compression

 

1. Splay trees have an amortized search cost of O(log n). This means that:

If we do m searches, where m is sufficiently large, the average time to search will be O(log n) even though individual searches may take up to O(n) time.

 

2. True or false: Doing m searches in a splay tree will be O(m log n) only if the data in the tree exhibits the locality of reference.

 

 

AVL tree Rotations

 

Single Right Rotation (LL Rotation)

This rotation is applied when the imbalance is on the left child's left subtree.

 

Single Left Rotation (RR Rotation)

This rotation is applied when the imbalance is on the right child's right subtree.

 

Left-Right Rotation (LR Rotation)

This rotation is a combination of two rotations. It is applied when the imbalance is on the left child's right subtree.

 

Right-Left Rotation (RL Rotation)

This rotation is also a combination of two rotations. It is applied when the imbalance is on the right child's left subtree.

 

 

AVL tree properties:

1. Binary search property

2. The height of its left and right subtrees differ by at most 1.

insertion: we must check balance factors and rotate once if out of balance

deletion: we must check balance factors and may have to rotate up to O(log n) times.

 

 

BST Operations in AVL Search Trees

 

Search

- Time Complexity

 

Insertion

- May have to rotate

- Time Complexity

 

Deletion

- May have to rotate up to log(n) times

- Time Complexity

 

Evaluating AVL Trees

Good: Operations are O(log n)

Not so good: Deletion is quite complex and has high(constant) overhead

 

#include <iostream>
#include <algorithm>

struct AVLNode {
    int key;
    int height;
    AVLNode* left;
    AVLNode* right;

    AVLNode(int value) : key(value), height(1), left(nullptr), right(nullptr) {}
};

int getHeight(AVLNode* node) {
    if (!node) return 0;
    return node->height;
}

int getBalance(AVLNode* node) {
    if (!node) return 0;
    return getHeight(node->left) - getHeight(node->right);
}

AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;

    return x;  // Return new root
}

AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;

    return y;  // Return new root
}

 

 

Operations in Splay Tree

- Search, O(M log N)

- Insertion

- Delete

 

Cache Efficiency: Because splay trees reorganize themselves to bring frequently accessed elements closer to the root, they can be cache-friendly in environments where certain elements are accessed more frequently than others.

 

AVL Trees (A type of self-balancing BST)

Advantages:

• Guarantees O(logn) height, ensuring all BST operations are efficient.
• More balanced compared to other self-balancing trees.

Disadvantages:

• Requires overhead of maintaining height or balance factor with each node.
• Rotations during insertions and deletions can be more frequent compared to other self-balancing trees.

Splay Trees (Self-adjusting BST)

Advantages:

• Amortized O(logn) time for operations.
• Self-adjusts to bring frequently accessed elements closer to the root, potentially improving access time for certain use cases.
• Simple to implement compared to other self-balancing trees.

Disadvantages:

• Worst-case time for an individual operation can be O(n).
• No guarantee of being balanced; performance can be unpredictable.