L4 Balance a Binary Search Tree

What is a binary search tree (BST)?

It is a data structure where each node has at most two children, and for any given node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

What is the main challenge in implementing a binary search tree?

It is to keep the tree balanced to ensure optimal performance for operations like insertion, deletion and search.

What is a rotation in the context of binary search trees?

A rotation is a local restructuring operation that helps maintain the balance of a binary search tree by changing the parent-child relationships between nodes.

What are the two types of rotations?

Right rotation and Left rotation.

How does a right rotation work?

A right rotation about an edge x, y moves y up to the position of x, and x becomes the right child of y.

What is the height balance property in AVL trees?

The height balance property states that for any node in the tree, the heights of its two subtrees must differ by at most one.

What is an AVL tree?

It is a type of self-balancing binary search tree where the height balance property is maintained after every insertion and deletion.

What is the time complexity for insertion and deletion in an AVL tree?

The time complexity for both insertion and deletion in an AVL tree is O(log n).

What is a red-black tree?

A red-black tree is a type of self-balancing binary search tree where each node is colored either red or black, and it follows specific properties to maintain balance.

What are the properties of red-black tree?

The properties include: - Every node is either red or black. - The root is always black. - Red nodes cannot have red children (no two adjacent red nodes) - Every path form a node to its descendant leaves must have the same number of black nodes.

What is the worst-case height of a balanced binary search tree?

O(log n)

What is the difference between worst-case and amortized balancing mechanisms?

Worst-case mechanisms maintain a strict height limit (O(log n)), while amortized mechanisms may exceed this limit temporarily but average out to O(log n) over a sequence of operations.

What is the significance of Fibonacci Numbers in AVL trees?

The number of nodes in a height-balanced tree is related to Fibonacci numbers, which helps prove that the height of the tree is logarithmic in relation to the number of nodes.

How do you restore the height balance property after an insertion in an AVL tree?

You can restore the height balance property using carefully chosen rotations after identifying the first node that violates the height balance property.

What is the main advantage of randomized balancing mechanisms?

It maintains a balanced state with high probability by simulating a random insertion order.

What is the in-order traversal of a binary search tree?

The in-order traversal of a binary search tree visits nodes in ascending order, processing the left subtree, then the node itself, and finally the right subtree.

What is the purpose of balancing mechanisms in binary search trees?

It is to ensure that the tree remains approximately balanced, which optimizes the time complexity for search, insertion and deletion operations.

What is the average-case time complexity for searching in a binary search tree?

It is O(log n) when the tree is balanced.

What happens if a binary search tree becomes unbalanced?

If binary search tree becomes unbalanced. The complexity for operations like search, insertion, and deletion can degrade to O(n) in the worst case.

What is a B-tree, how does it relate to binary search trees?

It is a self balancing tree data structure that maintains sorted data allow searches, sequential access, insertions, and deletions in logarithmic time. It generalizes binary search trees to allow more than two children per node, making it efficient for disk-based storage systems.

What is a randomized binary search tree (RBST)?

A RBST is a data structure that maintains a balanced binary search tree by injecting randomness during insertions and deletions.

Why are randomly built binary search trees likely to be balance?

They are built by inserting elements in random order, which leads to balanced structure with high probability.

What is the key property of a tree that satisfies the RBST property?

Every element within any subtree has an equal chance of being the root, ensuring balance.

How do you insert a new element into an RBST property?

When adding a new element, a biased coin is flipped. With a probability of 1/n, the new element becomes the root; otherwise, it is placed in the appropriate position while maintain the tree structure.

What happens to the probability of being the root when a new element is inserted?

After insertion, every element has a 1/n chance of being the root.

What are the two methods to install an element at the root of a binary search tree?

1. Insert it normally and rotate it up. 2. Split the tree and make the new element the root with its subtrees.

How is deletion handled in an RBST?

Replace the deleted element with the join of its two subtrees, ensuring the RBST property is maintained.

What is the join operation in the context of binary search trees?

The join operation merges two binary search trees while maintaining their properties.

How do you decide which subtree to keep as the root during the join operation?

Flip a coin with probabilities proportional to the sizes of the two subtrees.

What is the significance of maintaining the RBST property during the insertions and deletions?

It ensures that every element has an equal chance of being the root, keeping the tree balanced.

What is the base case in the join operation?

Merging a non-empty tree with an empty tree.

What analogy is used to describe the join operation?

It is sometimes referred to as "zip", as it resembles zipping two trees together.

What is the probability of choosing the left or right case during the join operation?

It is proportional to the size of the respective subtrees.

What is the main goal of the RBST structure?

To maintain a balanced tree structure with high probability through randomization.

How does the RBST property guide the insert and delete functions?

It ensures that the randomness is injected appropriately to maintain balance.

What is a splay tree?

It is a self-adjusting binary search tree that performs a splay operation to move accessed elements closer to the root, improving access times for frequently accessed elements.

What is the main idea behind amortized analysis in splay trees?

Amortized analysis provides an average performance gurantee over a sequence of operations, ensuring that the total time for (k) operations is O(k log n), even if individual operations may take longer.

What is a splay operation?

It is a process that rotates an accessed element up to the root of the tree, potentially using double rotations if the parent and grandparent are aligned.

How does a splay tree handle insertions?

To insert an element, it is added as a leaf in the tree, and then a splay operation is performed to move it to the root.

What happens during the deletion of an element in a splay tree?

The element is first splayed to the root, and then it is removed, replacing it with the join of its two children.

What is the significance of the "static optimality theorem" in relation to splay trees?

The theorem states that splay trees can match the performance of an optimal static binary search tree for a known access sequence, even without prior knowledge of the sequence.

What is the "dynamic optimality conjecture"?

It conjectures that splay tree are competitive with any binary search tree that can adapt its shape based on future access sequences, maintaining a constant factor in performance.

What are advantages of using splay trees over the binary search trees?

Splay trees are flexible, self-adjusting and can provide good performance for access patterns where certain elements are accessed more frequently.

How do splay trees, perform splits and joins?

The split a splay tree, the target value is splayed to the root, and one child subtree is detached. To join two trees, the max of one tree or the min of the other is splayed to the root, allowing for easy attachments.

What is the expected time complexity for major operations in a splay tree?

The expected time complexity for major operations (insert, delete, find) in a splay tree is O(log n) amortized time.

Why might a splay tree not always be balanced?

Splay trees do not maintain strict balance, instead they rely on the heuristic of moving frequently accessed elements closer to the root, which can lead to temporary imbalances.

What is the role of access patterns in the performance of the splay trees?

Access patterns influence the structure of the tree, frequently accessed elements becomes more accessible over time due to the splay operation.

What is the purpose of the "look ahead" mechanism in splay operations?

The look ahead mechanism allows the splay operation to perform double rotations when the parent and grandparent of the accessed node are aligned, leading to a flatter tree structure.

How does the splay tree's self-adjusting nature benefit frequently accessed elements?

Frequently accessed elements are moved closer to the root through splay operations, reducing the time needed for future access to those elements.

What is the relationship between splay trees and the concept of "local restructuring"?

Splay trees use local restructuring through splay operations to adjust the tree based on recent access patterns without global balancing, which can lead to efficient average performance.

Can splay trees be used for all types of data?

Yes, splay trees can be used for any type of data that can be organized in a binary search tree format, making them versatile for various applications.

What is the impact of degenerate cases on splay tree performance?

In degenerate cases, where the tree becomes unbalanced (ex. Resembling a linked list), individual operations may take longer but the amortized performance over a sequence of operations remains efficient.