[attachment=5097]
Binary Trees, an d Binary Search Trees and Binary Search Trees


Linear access time of linked lists is prohibitive
Does there exist any simple data structure for which the running time of most operations (search, insert, delete) is O(log N)?
Trees
Basic concepts
Tree traversal
Binary tree
Binary search tree and its operations

---

[attachment=8309]

Binary Search Trees


Binary Search Trees
One of the tree applications in Chapter 10 is binary search trees.
In Chapter 10, binary search trees are used to implement bags and sets.
This presentation illustrates how another data type called a dictionary is implemented with binary search trees.
The Dictionary Data Type
A dictionary is a collection of items, similar to a bag.
But unlike a bag, each item has a string attached to it, called the item's key.
The Dictionary Data Type
A dictionary is a collection of items, similar to a bag.
But unlike a bag, each item has a string attached to it, called the item's key.
The Dictionary Data Type
A dictionary is a collection of items, similar to a bag.
But unlike a bag, each item has a string attached to it, called the item's key.
The Dictionary Data Type
The insertion procedure for a dictionary has two parameters.
The Dictionary Data Type
When you want to retrieve an item, you specify the key...
The Dictionary Data Type
The Dictionary Data Type
We'll look at how a binary tree can be used as the internal storage mechanism for the dictionary.
A Binary Search Tree of States
The data in the dictionary will be stored in a binary tree, with each node containing an item and a key.
A Binary Search Tree of States
Storage rules:
Every key to the left of a node is alphabetically before the key of the node.
A Binary Search Tree of States
Storage rules:
Every key to the left of a node is alphabetically before the key of the node.
A Binary Search Tree of States
Storage rules:
Every key to the left of a node is alphabetically before the key of the node.
Every key to the right of a node is alphabetically after the key of the node.
A Binary Search Tree of States
Storage rules:
Every key to the left of a node is alphabetically before the key of the node.
Every key to the right of a node is alphabetically after the key of the node.
Retrieving Data
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Retrieve ' New Hampshire'
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Retrieve 'New Hampshire'
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Retrieve 'New Hampshire'
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Retrieve 'New Hampshire'
Start at the root.
If the current node has the key, then stop and retrieve the data.
If the current node's key is too large, move left and repeat 1-3.
If the current node's key is too small, move right and repeat 1-3.
Adding a New Item with aGiven Key
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Pretend that you are trying to find the key, but stop when there is no node to move to.
Add the new node at the spot where you would have moved to if there had been a node.
Adding
Adding
Removing an Item with a Given Key
Find the item.
If necessary, swap the item with one that is easier to remove.
Remove the item.
Removing 'Florida'
Find the item.
Removing 'Florida'
Removing 'Florida'
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
If necessary, do some rearranging.
Removing 'Florida'
Removing 'Florida'
Removing an Item with a Given Key
Find the item.
If the item has a right child, rearrange the tree:
Find smallest item in the right subtree
Copy that smallest item onto the one that you want to remove
Remove the extra copy of the smallest item (making sure that you keep the tree connected)
else just remove the item.
Summary
Binary search trees are a good implementation of data types such as sets, bags, and dictionaries.
Searching for an item is generally quick since you move from the root to the item, without looking at many other items.
Adding and deleting items is also quick.

---