Chapter 8: Binary Trees Flashcards
Why use binary trees?
Benefits of an ordered array and linked list: search is fast like an array and insertion and deletion is fast like a linked list.
How do you implement search for a binary tree?
Call sval the value to be found in the tree. Start at the root node, root = current. While current != sval, look at each of current’s children: child_right and child_left. If sval > child_left, current = child_right else current = child_left. If current == null return null. Finally return current.
What is the complexity of searching a binary tree?
O(log n)
How do you implement inorder binary tree traversal?
Create a recursive function which takes a node as an argument. In the outer call this node will be the root. The traverse function does 3 things in order: visits the left child, executes the traversal function (e.g. print node) and calls traverse on the right node.
How are pre- and post-order traversal implemented
The same, just with the inorder operations swapped: preorder is visit, call left, call right. postorder is call left, call right, visit.
Why should we study how to delete a node?
Deletion is important in many tree applications, and studying the details builds character.
How to delete a node which has no children?
Parent’s pointer is moved to null, Java’s garbage collection will take care of the data cleanup
How to delete a node which one child?
Connect it’s parent to it’s child
How do you find the in-order successor of a node (e.g. the node with the next highest value)
We are looking for the smallest the set which is larger than the current node. Starting at the current node visit the right node, which is greater than the current node. Then visit left children until there are no more left children to visit.
How do some programmer’s sidestep deletion?
An extra isDeleted field?
How do you delete a node with 2 children
- replace successor with it’s right subtree, 2. Keep the right child of the to be deleted node n it’s proper place by making it the right child of the successor, 3. make the successor the right node of the to be deleted’s parent
