Topic 5-2: Binary Search Tree
Data Structures
Copyright By PowCoder代写 加微信 powcoder
Binary Search Tree
BST Operations
Searching for an item
Inserting a new item
Deleting an item from BST
Finding Min & Max of a BST
Binary Search Trees
Why should you care?
So pay attention!
And because you’ll be asked about them in job interviews and on exams.
Binary Search Trees are an extremely efficient way to store/search for data!
You can search a BST with billions of items in just microseconds!
They’re used in databases, operating systems, search engines, etc.
Binary Search Trees
Binary Search Trees are a type of binary tree with specific properties that make them very efficient to search for a value in the tree.
Like regular Binary Trees, we store and search for values in Binary Search Trees…
Here’s an example BST…
Binary Search Trees
BST Definition: A Binary Search Tree is a binary tree with the following property:
For every node X in the tree:
Let’s validate that this
is a valid BST…
All nodes in X’s right sub-tree must be greater than X.
All nodes in X’s left sub-tree must be less than X.
What about duplicates?
Many algorithms will specify that duplicates are excluded.
Most specify left children as <= and right children as >.
A BST which allows either of the right or left children to be equal to the root node, will require extra computational steps to finish a search.
Now: Quick Test
Question: Which of the following are valid BSTs?
InOrder(Node cur):
if cur == None // if empty, return…
InOrder(cur.left) // Process nodes in left sub-tree.
print (cur.value ) // Process the current node.
InOrder(cur.right) // Process nodes in right sub-tree.
Printing In Alphabetical Order
What algorithm we use to print out data in alphabetical order?
Operations on a Binary Search Tree
Search the binary search tree for a value
Insert an item in the binary search tree
Delete an item from the binary search tree
Traverse the binary search tree
Searching a BST
Input: A value V to search for
Output: TRUE if found, FALSE otherwise
Start at the root of the tree
Keep going until we hit the None object
If V is equal to current node’s value, then found!
If V is less than current node’s value, go left
If V is greater than current node’s value, go right
If we hit a None object, not found.
Let’s search for Gary.
Gary == Larry??
Gary < Larry?? Gary == Fran?? Gary < Fran?? Gary > Fran??
Gary == Gary??
Searching a BST
Here are two different BST search algorithms, one recursive and one iterative:
Search(int V, Node ptr):
if root == None:
return false // nope
elif V == ptr.value:
return true // found!!!
elif V < ptr.value:
return Search(V, ptr.left))
return Search(V, ptr.right))
Search(int V,Node ptr):
while ptr != None
if V == ptr.value:
return true
elif V < cur.value:
ptr = ptr.left
ptr = ptr.right
return false // nope
Let’s trace through the recursive version…
Recursive BST Search
Lets search for 14.
Search(int V, Node ptr)
if (ptr == None)
return(false) // nope
else if (V == ptr.value)
return(true) // found!!!
else if (V < ptr.value)
return(Search(V,ptr.left))
return(Search(V,ptr.right))
bFnd = Search(14,Root)
14 == 13??
Search(int V, Node ptr):
if (ptr == None)
return(false) // nope
else if (V == ptr.value)
return(true) // found!!!
else if (V < ptr.value)
return(Search(V,ptr.left))
return(Search(V,ptr.right))
14 == 17??
Search(int V, Node ptr):
if (ptr == None)
return(false) // nope
else if (V == ptr.value)
return(true) // found!!!
else if (V < ptr.value)
return(Search(V,ptr.left))
return(Search(V,ptr.right))
14 == 14??
Recursive BST Search
Lets search for 14.
Search(int V, Node ptr):
if (ptr == None)
return(false) // nope
else if (V == ptr.value)
return(true) // found!!!
else if (V < ptr.value)
return(Search(V,ptr.left))
return(Search(V,ptr.right))
bFnd = Search(14,pRoot)
Search(int V, Node ptr):
if (ptr == None)
return(false) // nope
else if (V == ptr.value)
return(true) // found!!!
else if (V < ptr.value)
return(Search(V,ptr.left))
return(Search(V,ptr.right))
Recursive BST Search
Lets search for 14.
bool Search(int V, Node ptr):
if (ptr == None)
return(false) // nope
else if (V == ptr.value)
return(true) // found!!!
else if (V < ptr.value)
return(Search(V,ptr.left))
return(Search(V,ptr.right))
bFnd = Search(14,pRoot)
Which of the two is better?
The recursive version is marginally more elegant, easier to prove its correctness.
The iterative version is probably a bit more efficient - this is because a function call, in real life, takes longer to execute than an iteration of a loop.
I encourage you to conduct some experiments to explore this question for yourself.
Big O of BST Search
In the average BST with N values, how many steps are required to find our value?
In the worst case BST with
N values, how many steps are required find our value?
50% eliminated!
50% eliminated!
50% eliminated!
50% eliminated!
log2(N) steps
Inserting A Into A BST
To insert a new node in our BST, we must place the new node so that the resulting tree is still a valid BST!
Where would the following new values go?
Inserting A Into A BST
If the tree is empty
Allocate a new node and put V into it
set the new node as the root. DONE!
Input: A value V to insert
Start at the root of the tree
While we’re not done…
If V is greater than current node’s value
If there is a right child, then go right
ELSE allocate a new node and put V into it,
set new node as the right child of the current node. DONE!
If V is equal to current node’s value, DONE! (nothing to do...)
If V is less than current node’s value
If there is a left child, then go left
ELSE allocate a new node and put V into it, and
set new node as the left child of current node. DONE!
def BST_Insert(x):
new_node = new Binary_TreeNode(x)
if this.root == nil:
this.root = new_node
current = this.root
boolean done = false
while not done:
if x > current.value:
if current.right == nil:
current.right = new_node
done = true
current = current.right
if current.left_child == nil:
current.left_child = new_node
done = true
current = current.left
Code (iterative)
# this creates a new node, stores the value x
Is this an empty tree?
Left or right subtree?
Insert if has empty space
Otherwise, move to right/left
Inserting A Into A BST
As with BST Search, there is a recursive version of the Insertion algorithm too.
def BST_Insert(x):
self.root = rec_BST_Insert(self.root,x)
def rec_BST_Insert(current,x):
if current == none:
return new Binary_TreeNode(x)
elif x > current.value:
current.right = rec_BST_insert(current.right,x)
current.left = rec_BST_insert(current.left,x)
return current
Code (recursive)
Big O of BST Insertion
So, what’s the big-O of BST Insertion?
It’s also O(log2n)
Why? Because we have to first use a binary search to find where to insert our node and binary search is O(log2n).
Once we’ve found the right spot, we can insert our new node in O(1) time.
Inserting A Into A BST
Given a random array of numbers if you insert them one at a time into a BST, what will the BST look like?
Given an ordered array of numbers if you insert them one at a time into a BST, what will the BST look like?
Question: What happens if we insert the following values into a binary search tree?
5, 10, 7, 9, 8, 20, 18, 17, 16, 15, 14, 13, 12, 11
Balanced Search Trees
Question: What happens if we insert the following values into a binary search tree?
5, 10, 7, 9, 8, 20, 18, 17, 16, 15, 14, 13, 12, 11
We get an unbalanced tree!
In real life, BSTs often end up looking just like our example, especially after repeated insertions and deletions.
It’d be nice if we could come up with an improved BST ADT that always maintains its balance.
This would ensure that all insertions, searches and deletions would be O(log n).
Balanced Search Trees
What is the approximate big-oh cost of searching
for a value in this tree?
Balanced Search Trees
Numerous improved binary search tree ADTs:
Red- , and AVL Trees, etc.
These BST variations work (mostly)
just like a regular binary search tree…
but every time you add/delete a value, they shift the nodes around to make the tree balanced!
named after inventors
Deleting a Node from a Binary Search Tree
Now, let’s learn how to delete an item from a BST.
Let’s say we want to delete Darren from our tree…
Now how do I re-link the nodes back together?
Can I just move Arissa into Darren’s old slot?
Is our tree still a valid binary search tree?
By simply moving an arbitrary node into Darren’s slot, we violate our Binary Search Tree ordering requirement!
Carey is NOT less than Arissa!
Next we’ll see how to do this properly….
Deleting a Node from a Binary Search Tree
Here’s a high-level algorithm to delete a node
from a Binary Search Tree:
Given a value V to delete from the tree:
Find the value V in the tree, with a slightly-modified BST search.
Use two variables: a cur pointer & a parent pointer
If the node was found, delete it from the tree, making sure to preserve its ordering!
There are three cases, so be careful!
BST Deletion: Step #1
Step 1: Searching for value V
parent = None
cur = root
While (cur != None)
If (V == cur.value) then we’re done.
If (V < cur.value)
parent = cur
cur = cur.left
C. Else if (V > cur.value)
parent = cur
cur = cur.right
Let’s delete Casey
Casey < Mel? Casey < Darren? Casey < Carey? When we’re done with our loop below, we want the parent pointer to point to the node just above the target node we want to delete. This algorithm is very similar to our traditional BST searching algorithm… Except it also has a parent pointer. Every time we move down left or right, we advance the parent pointer as well! So if we were deleting Arissa… We’d want our parent pointer to point to Carey’s node. Now cur points at the node we want to delete, and parent points to the node above it! BST Deletion: Step #2 Once we’ve found our target node, we have to delete it. There are 3 cases. Our node is a leaf. Our node has one child Our node has two children. Step #2, Case #1 – Our Target Node is a Leaf Let’s look at case #1 – it has two sub-cases! Our node is a leaf. Unlink the parent node from the target node (cur) by setting the parent’s appropriate link to None. Our target node (cur) that we want to delete is NOT the root node! Case 1, Sub-case #1: The target node is NOT the root node In this case, our target node (cur) is our parent node’s right child… So we’ll set parent.right to None to unlink the parent and cur. Let’s look at case #1 – it has two sub-cases! Unlink the parent node from the target node (cur) by setting the parent’s appropriate link to None. Case 1, Sub-case #1: The target node is NOT the root node Case 1, Sub-case #2: The target node is the root node Our node is a leaf. Set the root value to None. Our target node (cur) that we want to delete is the root node! Step #2, Case #1 – Our Target Node is a Leaf Our node has one child It also has two sub-cases! Let’s look at case #2 now… Relink the parent node to the target (cur) node’s only child. Case 2, Sub-case #1: The target node is NOT the root node Our target node (cur) that we want to delete is NOT the root node! only child Step #2, Case #2 – Our Target Node has One Child Our node has one child It also has two sub-cases! Let’s look at case #2 now… Relink the parent node to the target (cur) node’s only child. Case 2, Sub-case #1: The target node is NOT the root node Case 2, Sub-case #2: The target node is the root node Set the target (cur) node’s only child as the root Our target node (cur) that we want to delete is the root node! only child Step #2, Case #2 – Our Target Node has One Child Let’s look at case #3 now. The hard one! Our node has two children. We need to find a replacement for our target node that still leaves the BST consistent. So, when deleting a node with two children, we have to be very careful! Has two children! Step #2, Case #3 – Our Target Node has Two Children We can’t just pick some arbitrary node and move it up into the vacated slot! K’s left subtree’s largest-valued child To delete a node like k that has two children…. 2. K’s right subtree’s smallest-valued child How? We want to replace k with either: Step #2, Case #3 – Our Target Node has Two Children We don’t actually delete the node itself! Instead, we replace its value with one from another node! These two values are the only suitable replacements for node k – so pick either one and copy it up. These two values are the only suitable replacements for node k. For example, let’s use this node’s value. So we pick one, copy its value up, then delete that node! Notice that our BST is still correct! Finally, we delete this node! How? Notice that both of them are either a leaf or have just one child! We use technique #1 or #2! Why? Our replacement node is guaranteed to have either zero or one child! In this case, our node is a leaf, so we use Case 1. OK, now let’s try the other replacement node and see if it works! Step #2, Case #3 – Our Target Node has Two Children In this case, our node has one child, so we use Case 2. And now let’s delete the replacement node… Which Case should we use? Notice that our BST is still correct! Why is it guaranteed that our two replacement nodes have either zero or one child? Step #2, Case #3 – Our Target Node has Two Children We found the left subtree’s maximum value by going all the way to the right… So by definition, it can’t have a right child! Either it has a left child or no children at all… By definition, it can’t have a left child! The same holds true for the smallest value in our right subtree! No right child! So this ensures we can use one of our simpler deletion algorithms for the replacement! No left child! Practice: Deletion Explain how you would go about deleting node k. Explain how you would go about deleting node i. Question: What’s the big-O to find the minimum or maximum element? Finding Min & Max of a BST How do we find the minimum and maximum values in a BST? The minimum value is located at the left-most node. The maximum value is located at the right-most node. GetMin(node Root): if (Root == None) return -1 // empty while (Root.left != None) Root = Root.left return Root.value GetMax(node Root): if (Root == None) return -1 // empty while (Root.right != None) Root = Root.right return Root.value BST Operations Searching for an item Inserting a new item Deleting an item from BST Finding Min & Max of a BST Complexity analysis 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com