University:
Amherst College
Course:
COSC 211 | Data Structures
Academic year:

2022
Views:

326

Pages:

4
Author:

ilikemyicons0y5

AVL Trees Can a Binary Search Tree (BST) be used as an index for a flat, unsorted file? Yes – however, a BST is not guaranteed to be balanced. The O(log(n)) time complexity for searching only applies when the tree is balanced (meaning its height remains O(log(n))). Note that a tree's time complexity is always equal to its height, so a time complexity of O(log(n))directly reflects the tree's height. Using a self-balancing BST (like an AVL Tree or Red-Black Tree) solves this problem by keeping the tree balanced and maintaining O(log₂n) search time throughout additions, changes, and deletions. What is the time complexity of all BST operations? The time complexity of all BST operations are O(h)where his the three height. What is the best case BST height? When does this occur? Best Case: Perfectly balanced tree → height = O(log₂n). What is the worst case BST height? When does this occur? AVL Trees 1 Worst Case: Skewed tree (e.g., inserting sorted elements) → height = O(n). Example: Inserting 2, 4, 6, 8, 10, 12 in order creates a linear chain. What do we mean by a “balanced tree”? BSTs can be balanced to different degrees. A perfectly balanced tree has: all levels (except possibly the last) filled with the maximum number of child nodes all leaf nodes at the same level However, maintaining perfect balance is computationally expensive since it requires frequent rebuilding. AVL trees maintain efficient balance by ensuring the height difference between subtrees never exceeds 1. – they are still considered balanced. An unbalanced tree is one where the height difference between subtrees is extreme, typically exceeding 1. AVL Trees 2 Examples and non-examples of balanced trees Is this balanced? While it is fairly balanced, it is not perfectly balanced. It’s imperfections are: Imbalance: The left subtree has a height of 2, while the right subtree has a height of 1, creating an uneven structure. Incomplete levels: The lowest level is not filled from left to right as it would be in a complete tree—node 5 has no children, while in the left subtree at the same level, nodes 1 and 3 are children of 2. Is this balanced? Yes this is perfectly balanced. AVL Trees 3 The leaf nodes are all on the exact same level All the levels are complete, with each non-leaf node having exactly two children and all internal nodes filled from left to right Is this balanced? No, this represents the worst case of a BST. The tree is extremely skewed and functions essentially as a linked list. All operations on this tree have linear time complexity. Continued… What is the worst case running time? Linear time O(n) What happens when you insert elements in ascending order into a BST? AVL Trees 4

Description

Related Documents

Almost There!

Free up your schedule!

Take 5 seconds to unlock