[SOLVED] CS Topic 5-2: Binary Search Tree

Topic 5-2: Binary Search Tree
Data Structures

Copyright By Assignmentchef assignmentchef

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 youll 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!
Theyre 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

Heres 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:

Lets validate that this
is a valid BST

All nodes in Xs right sub-tree must be greater than X.

All nodes in Xs 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 nodes value, then found!
If V is less than current nodes value, go left
If V is greater than current nodes value, go right

If we hit a None object, not found.

Lets 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 != Noneif V == ptr.value:return trueelif V < cur.value: ptr = ptr.left ptr = ptr.rightreturn false // nopeLets trace through the recursive versionRecursive BST SearchLets search for 14.Search(int V, Node ptr)if (ptr == None) return(false)// nopeelse 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)// nopeelse 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)// nopeelse 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 SearchLets search for 14.Search(int V, Node ptr):if (ptr == None) return(false)// nopeelse 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)// nopeelse if (V == ptr.value)return(true)// found!!!else if (V < ptr.value)return(Search(V,ptr.left)) return(Search(V,ptr.right))Recursive BST SearchLets search for 14.bool Search(int V, Node ptr):if (ptr == None) return(false)// nopeelse 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 SearchIn 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) stepsInserting 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 insertStart at the root of the treeWhile were not doneIf V is greater than current nodes 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 nodes value, DONE! (nothing to do…)If V is less than current nodes value If there is a left child, then go left ELSE allocate a new node and put V into it, andset 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_nodecurrent = this.rootboolean done = falsewhile 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, whats the big-O of BST Insertion?
Its 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 weve 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.
Itd 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, lets learn how to delete an item from a BST.

Lets 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 Darrens old slot?

Is our tree still a valid binary search tree?
By simply moving an arbitrary node into Darrens slot, we violate our Binary Search Tree ordering requirement!
Carey is NOT less than Arissa!
Next well see how to do this properly.

Deleting a Node from a Binary Search Tree
Heres 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 were done.
If (V < cur.value)parent = curcur = cur.leftC. Else if (V > cur.value)
parent = cur
cur = cur.right
Lets delete Casey

Casey < Mel?Casey < Darren?Casey < Carey?When were 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 ArissaWed want our parent pointer to point to Careys node.Now cur points at the node we want to delete, and parent points to the node above it!BST Deletion: Step #2 Once weve found our target node, we have to delete it.There are 3 cases.Our node is a leaf.Our node has one childOur node has two children.Step #2, Case #1 Our Target Node is a Leaf Lets 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 parents 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 nodeIn this case, our target node (cur) is our parent nodes right childSo well set parent.right to None to unlink the parent and cur.Lets look at case #1 it has two sub-cases!Unlink the parent node from the target node (cur) by setting the parents appropriate link to None.Case 1, Sub-case #1: The target node is NOT the root nodeCase 1, Sub-case #2: The target node is the root nodeOur 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 childIt also has two sub-cases!Lets look at case #2 nowRelink the parent node to the target (cur) nodes only child.Case 2, Sub-case #1: The target node is NOT the root nodeOur target node (cur) that we want to delete is NOT the root node!only childStep #2, Case #2 Our Target Node has One Child Our node has one childIt also has two sub-cases!Lets look at case #2 now Relink the parent node to the target (cur) nodes only child.Case 2, Sub-case #1: The target node is NOT the root nodeCase 2, Sub-case #2: The target node is the root nodeSet the target (cur) nodes only child as the rootOur target node (cur) that we want to delete is the root node!only childStep #2, Case #2 Our Target Node has One ChildLets 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 ChildrenWe cant just pick some arbitrary node and move it up into the vacated slot!Ks left subtrees largest-valued childTo delete a node like k that has two children.2.Ks right subtrees smallest-valued childHow? We want to replace k with either:Step #2, Case #3 Our Target Node has Two ChildrenWe dont 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, lets use this nodes 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 lets 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 lets 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 ChildrenWe found the left subtrees maximum value by going all the way to the rightSo by definition, it cant have a right child!Either it has a left child or no children at allBy definition, it cant 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: DeletionExplain how you would go about deleting node k.Explain how you would go about deleting node i.Question: Whats the big-O to find the minimum or maximum element?Finding Min & Max of a BSTHow 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// emptywhile (Root.left != None) Root = Root.leftreturn Root.valueGetMax(node Root):if (Root == None)return -1// emptywhile (Root.right != None) Root = Root.rightreturn Root.valueBST Operations Searching for an itemInserting a new itemDeleting an item from BSTFinding Min & Max of a BSTComplexity analysis CS: assignmentchef QQ: 1823890830 Email: [email protected]