COMP 2140 Lecture 15: 10_31_23tree_heap.pdf
13 Aug 2014
School
Department
Course
Professor
Document Summary
For 2-node (recursive) left subtree (recursive) right subtree. For 3-node (recursive) left subtree subtree subtree st value nd. If key is the value a 2-node subtree. If key is smaller value of a 3-node subtree. If key is larger value of a 3-node subtree. When reaching a leaf, the successor is the value of the leaf if it is a 2 node the smaller value of the leaf if it is a 3 node. If the root ends up having 3 values, split the root node and create a new level this is the only case that increases the tree height. Need to go further up the tree to resolve overcrowding. To delete x, we search for a node in 2-3 tree containing x. If it is an interior node, swap x with its in- order successor deletion always begins at a leaf node l. If l contains a value in addition to x, delete x from l.
