Self-Balancing Trees: AVL and B-Trees

BST Performance Recap

• BSTs offer efficient performance for average-case scenarios
• The number of steps to reach any node is logarithmically related to the number of nodes i.e. 𝒪(log 𝑛)
• Average-case performance is superior to linked lists, as linked lists require a linear number of steps i.e. 𝒪(𝑛)
• Degenerate BSTs lead to worst-case performance, which, like linked lists, become linearly related i.e. 𝒪(𝑛)

Self-Balancing Trees

• Self-balancing trees address the issues of degenerate trees
• Two well-known types of self-balancing trees include AVL trees and B-Trees
• Self-balancing trees use special logic during insert and delete to ensure the tree remains broad and triangular, avoiding degeneration
• This optimization keeps the steps to reach a node logarithmically related to the number of nodes, denoted as 𝑛, even in the worst-case scenario

AVL Trees

• The "Adelson-Velsky Landis" tree was the first self-balancing tree
• AVL trees were introduced in 1962
• They are named after Georgy Maximovich Adelson-Velskii and Evgenii Mikhailovich Landis, two Soviet computer scientists

AVL Tree Rules

• An AVL tree is a BST where the height difference between the left and right subtrees for all nodes is ≤ 1
• Expressed as |ℎ(subtreeright) − ℎ(subtreeleft)| ≤ 𝑘, where ℎ represents the height of a tree
• For AVL trees, 𝑘 = 1, where k is called the order of the tree
• Every node in an AVL tree has a balance factor, along with its key and data
• The balance factor is ∈ ℤ: −2 ≤ 𝑥 ≤ 2, contingent on whether the right subtree's height is >, =, or than the left subtree

AVL Tree Advantages

• AVL trees are better than BSTs
• The worst-case number of hops needed to reach any node in a search are logarithmically related to total nodes
• Alterations to the tree's structure following insertions or deletions are made on-the-fly
• Once the node position is determined, insertions and deletions maintain a constant computing cost, regardless of the tree's size

Subtree Heights & Balance Factors

• Subtree heights are used to determine the balance factors of each node
• balance factor = ℎ subtreeright − ℎ(subtreeleft )
• A balance factor of -1: the height of the left subtree is greater than the right subtree by 1
• A balance factor of 0: the height of the left subtree is equal to the height of the right subtree
• A balance factor of +1: the height of the left subtree is less than the height of the right subtree by 1

Imbalance Scenarios

• There are four imbalance scenarios that can occur in AVL trees
• These scenarios are Left-Left (LL) case, Right-Right (RR) case, Left-Right (LR) case and Right-Left (RL) case.

Performance Summary of AVL Trees

• AVL trees have 𝒪(log 𝑛) time complexity for search, insert and delete
• Time complexity applies to both the average and the worst case
• Degenerate trees cannot occur in AVL trees
• Since costly total tree re-balancing isn't needed, re-balancing takes a constant time

Summary Table of AVL Tree Performance

• Successful insert, delete and search operations all have a complexity of 𝒪(log 𝑛) for best, average, and worst cases
• Successful search operations have a best case complexity of 𝒪(1)
• Unsuccessful insert operations have a complexity of N/A for best, average, and worst cases
• Unsuccessful delete and search operations all have a complexity of 𝒪(log 𝑛) for best, average, and worst cases

B-Trees

• B-Trees were introduced in 1972 by Bayer and McCreight, both working at Boeing
• They are commonly used in databases, file systems, and search engines

B-Tree Rules

• The maximum out degree of the B-Tree is defined as 𝑚
• The root node can have between 1 and 𝑚 − 1 number of data items
• Interior and leaf nodes must be at least half full, holding up to 𝑚 − 1 items
• All leaf nodes reside on the same level
• B-Tree nodes can have a range of 0 to 𝑚 children, This makes them a 𝑘-ary tree
• Data items are internally sorted with the B-Tree node, which is managed during the insert process

B-Tree Properties

• B-Trees’ height is minimize through the increased items held in each node
• Widely used for searching large datasets, especially within databases, and with secondary disk storage
• Exhibit high locality of reference, where similar data is stored nearby, often inside the same node

B-Tree Node Structure

• Each B-Tree node holds approximately 𝑚 − 1 data items
• Each B-Tree node holds a counter to keep track of how many data items the node currently holds
• Each B-Tree node uses flag if the node is a leaf or not
• Each B-Tree node uses holds 𝑚 pointers to point towards up to 𝑚 child nodes

B-Tree Nodes

• With 𝑚 = 6, the maximum data items each node can hold is 5
• Given 𝑚 = 6, the maximum child nodes for an interior node is 6

B-Tree Search Operation

• Start at the root node to initialize the search
• Sequentially search for items in the current node until the target key is found
• If the current node is a leaf, and after failing to locate key, return -1, thus indicating search failure
• Set the current node to the child node to the left of the item that surpasses the sought item based on the key

Successful Search Operation

• The target key of 41 is being searched for in the example B-Tree
• Since 30 is less than the search target 41, the next key is advanced to in the array of keys
• Key 38 is also less than the target, advancing the key again
• The next key 42 is larger than the search, so the child pointer is trailed between 38 and 42, since the root node is not a leaf
• Advancing again, the process is preformed on the current node, where key of 40 is smaller than the search target
• The next key in the current node matches the target, so the stop is a successful event

Unsuccessful Search Operation

• The target is a search of 36 in the example B-Tree
• The second position of the root is larger, at 38, so the child node is followed, since it is not a leaf
• Since 32 is smaller, proceed to key 34, where the process is repeated, and it determined that there is a failure to locate the target
• Having now reached the array’s end, since the node is marked as the process is ended

B-Tree Insert Operation

• A B-Tree insert operation is demonstrated for new data, assuming that 𝑚 = 5
• Perform the initial inserts: 20, 40, 10
• Inserting 30 and 50 splits the root into two siblings
• Push the middle key up into the new root after sorted-order
• Continue by filling the child nodes by inserting 25, 42, and 44
• The next insert of a target of 41 ends up splitting the existing full node into two siblings
• Ensure the parent node is not full, such that the median key is pushed up into the parent

B-Tree Insert Routine

• Perform Insertion by the means of searching to determine to correct value position
• Add a value into a list in the correct position, after array shuffling as required
• Handle a value entry overflow, by preforming the sequence: Split the current node towards two siblings. Assign smaller values assign to the left sibling, and assign the higher numbers into the right sibling
• With the above nodes in the case were they a root node, after splitting, make an additional root node push the previous element into the new root
• If not a root node during splitting, assign the middle value, in this case, push it to the parent node, and follow to step B to continue or create an extra root node if vacant space if needed

B-Tree Delete Scenarios

• After deleting 56 and 7, the tree removes and shuffles remaining items
• If possible, you can borrow an item from either sibling with the goal of having the node stay approximately half full
• Then the node gets borrowed from it's left sibling
• With the target of deleting 34, there is no way borrow a respective sibling, so both the left and right siblings are then combined, and then 38 can be pulled from original parent