Binary Search Trees: Deletion
Chapter 19
Review
Binary Trees
A binary tree is empty or has these properties:
Has a root node.
Has a left subtree and right subtree, which are binary trees.
A node (called a vertex in graph theory):
Has at most two children.
Stores its own information.
Keeps track of its left subtree and right subtree using pointers
(e.g.,leftandright).
A pointer to the root node of the binary tree is stored outside the tree.
Leaf: a node that has no children.
A parent has a branch to a child node.
There is a unique path from the root to every node.
The Path Length is the number of branches on that path.
Node Level: number of branches from the root to the node.
- The root node is at level 0.
Height of a binary tree: number of edges on the longest path from the root to a leaf.
Binary Search Tree
Definition: A binary search tree is either empty or has these properties:
Has a root node.
Has two sets of nodes: the left and right subtrees.
The key in the root node is larger than every key in the left subtree and smaller than every key in the right subtree.
The left subtree and right subtree are binary search trees.
Performance of a Binary Search Tree
What is the average-case Big-O of the following operations on a binary search tree?
| Array | Linked List | Binary Search Tree | |
|---|---|---|---|
| Random Access | NA | ||
| Insert/Remove | |||
| Search | |||
| Sort | NA * |
* A binary-search tree is already sorted. To convert it to a sorted list, a inorder traversal will take
Deleting a Node
The four cases of delete depend on the node to be deleted:
Is a leaf (e.g., 77)
Has an empty left subtree (e.g., 53)
Has an empty right subtree (e.g., 80)
Has nonempty left and right subtrees (e.g., 50)
See the lecture video for examples of each case.
Example Tree
Example Tree: Remove 50
See the lecture video.
Example Tree: Remove 35
See the lecture video.
Performance of Delete
What is the average-case Big-