Binary Search Tree (chapter-15)

dineshkavitha

Download

Post to :

URL :

Related Presentations :

Add to Flag Embed

Views: 4970

Category: Education

Presentation Description

No description available.

Comments

By: fanaah (20 month(s) ago) Private Comment

plz send this ppt to gloryfanaah@gmail.com

By: laxkallur (21 month(s) ago) Private Comment

this is helpful for me plz send to mlhit5@gmail.com

By: koongkoong (22 month(s) ago) Private Comment

cool

By: cvv3cvv (31 month(s) ago) Private Comment

it is useful for me

By: anim.srms (31 month(s) ago) Private Comment

please send this ppt at my email..........anim.srms@gmail.com

See all

Presentation Transcript

Slide 1:

UNIT - IV CHAPTER – 15 BINARY SEARCH TREE CHAPTER – 16 BALANCED SEARCH TREE

Slide 2:

CHAPTER – 15 BINARY SEARCH TREE

1. DEFINITIONS :

1. DEFINITIONS 1.1. Binary Search Tree A Binary Search Tree is a binary tree that may be empty. A non-empty binary search tree satisfies the following properties: 1. Every node has a value and no two elements (nodes) have the same value, therefore all values are distinct. 2. The values in the left subtree of the root are smaller than the key in the root. 3. The values in the right subtree of the root are larger than the key in the root.

Slide 5:

4. The left and right subtrees of the root are also binary search trees. EXAMPLE: 20 12 15 25 18 22 It’s not a Binary search Tree, because the right subtree fails to satisfy property – 3 and 4 FIGURE- (a)

Slide 6:

30 The following are Binary Search Trees FIGURE- (b) 40 5 2 30 5 40 FIGURE- (c) 60 65 70 80 FIGURE- (d)

Another Definition :

Another Definition A Binary Search Tree (BST) is an ordered Binary Tree, either it’s an empty tree (or) - each data value in it’s left subtree is less than the root value - each data value in it’s right subtree is greater than the root value - Left and Right subtrees are again binary search tree All < K All > K K

2. ABSTRACT DATA TYPES :

2. ABSTRACT DATA TYPES Abstract Data Type BSTree { instance: binary trees, each node has an element with a key fields; all keys are distinct; keys in the left subtree of any node are smaller than the key in the node; those in the right subtree are larger. operations: Create( ): create an empty binary search tree

Slide 9:

Search (K, x): return x th – element with key (or) value K. return false if the operations fails. return true if it success. Insert (x): insert an element x into the search tree Delete (k, e) : delete the element with key (or) value k and return it in x Ascend ( ) : Output all element in ascending order of key (or) value. }

3. BINARY SEARCH TREE OPERATIONS :

3. BINARY SEARCH TREE OPERATIONS 3.1. SEARCHING * Suppose we wish to search an element with key (or) value (k), we begin at the Root. If the root is NULL, the search tree contains no elements, and the search is unsuccessful. * Otherwise, we compare K-with the key/value in the Root. If K – is less than the key/value in the root, then no element in the right subtree can have key/value (k) and only left subtree is to be searched.

Slide 11:

* If k – is larger than the key in the root, only the right subtree need to be searched. * If k – equals to the key/value in the root, then the search terminates successfully. The subtree may be searched similarly.

Algorithm for BST - searching :

Algorithm for BST - searching algorithm SearchBST search a binary search tree for a given value precondition: root is the root to a binary tree (or) subtree argument is the key value requested. Return: the node address, if the value is found null if the node is not in the tree. 1. if (root is null) 1. return null 2. end if

Slide 13:

3. if ( argument < root key) 1. return searchBST ( root left, argument) 4. elseif (argument > root key) 1. return searchBST (root right, argument) 5. else 1. return root 6. end if end if End searchBST

Example – BST SEARCH :

Example – BST SEARCH Find a given node in a binary search tree, let us consider the following figure: 23 12 18 44 20 52 35 Search Node : 20

Slide 15:

Suppose we are looking for node : 20, we begin by comparing the search argument 20, with the value in the tree “Root”. Because 20 is less than the Root value 23, and because we know that all values less than the Root lie in it’s Left subtree, we go Left. Now compare the search argument with the value in the subtree:18. This time the search argument is greater than the tree value:18 We know that values greater than the tree Root must lie in it’s Right Subtree, we go right and find our desired value.

The logic of BST – search work in the following ways: :

The logic of BST – search work in the following ways: To search a particular node in the BST, we use the procedure similar to “ Insertion”. Beginning at the root node, the current node & the entered node are compared. If the values are equal, SUCCESS is output. If the entered value is less than the value in the node then it must be in the left-child of subtree. If there’s no left child subtree, the value is not in the tree, (i.e. a failure is reported). If the entered value is greater than the value in the current node, the right child is searched.

LOGIC FOR BST-SEARCH :

LOGIC FOR BST-SEARCH find-key (key-value, node) { if ( two values are same) { print value stored in node; return (SUCCESS); } else if( key-value stored in current node) { if ( left child exists) { find-key ( key-value, left hand); } else

Slide 18:

{ there is no left subtree; return( string not found) } } else if ( key-value stored in current node) { if ( right child exists) { find-key( key-value, right child); } else { there is no right subtree; return (string not found) } } }

3.2.insertion :

3.2.insertion All BST-insertion take place at a Leaf (or) Leaf like node. Inserting a Node to the Tree: * To insert a node in a BST, we must check whether the tree already contains any nodes. * If the tree is empty, the node is placed in the Root node. If the tree is not empty, then the proper location is found and the added node becomes either a Left (or) a Right child of an existing node.

The logic of BST – insert work in the following ways: :

The logic of BST – insert work in the following ways: Add-node (node, value) { if (two values are same) { duplicate; return (FAILURE) } else if (value < value stored in current node) { if (left child exists) { add-node (left child, value); }

Slide 21:

else { allocate new node and make left child point to it; return (SUCCESS); } } else if (value > value stored in current node) { if (right child exists) { add-node (right child, value); }

Slide 22:

else { allocate new node and make right child point to it; return (SUCCESS); } }

Algorithm for BST - insertion :

Algorithm for BST - insertion Algorithm addBST insert node containing new data into BST using recursion Precondition : root is address of current node in a BST. new is address of node containing data to be inserted. Postcondition : new is address of node containing data to be inserted.

Slide 24:

1. if ( root is null) 1. root = new 2. else location for new node found 1. if (new key < root key) 1. addBST ( root left, new) 2. else 1. addBST ( root right, new) 3. end if 3. end if 4. return end addBST

Example – BST INSERTION :

Example – BST INSERTION Let us assume the following BST: 23 12 18 44 20 52 35 New node 19 is going to be added, to the existing BST

Slide 26:

Suppose if we want to insert the element 19, it will first compared to the Root node 23. The element 19 is less than the root node 23, so insertion will take place left child of the Root node 23 (19 < 23). The left side tree of root node 23 is: 23 12 18 20

Slide 27:

Again the new node 19 is compared with the left side tree root 18. Hence new node 19 is greater than the root 18. so node insertion is going to take place “Right side of the root 18”. ( 18 > 19). The right side of node 18 contains the element 20. Hence new node 19 is less than the node 20. (19 < 20). so the new node 19 is inserted into left side of the node 20. 18 20

Slide 28:

23 12 18 44 20 52 35 19

Slide 29:

Suppose if w want to insert the new node 38., it’s inserted right side of the existing node 35. 23 12 18 44 20 52 35 19 38

3.3.Deletion :

3.3.Deletion METHOD-I To delete a node from a binary search tree there are four possible cases when we delete a node: 1. If node is a leaf node (or) node has no children, it can be deleted by making it’s parent to null. EXAMPLE: Consider the following figure, to remove 35 from the tree, the left child field of its parent is set to null, and the node is discarded. The resulting tree will appear as follow 30 40 5 2 30 40 5 2 35 80 80

Slide 31:

2. If the node has one child, it’s parent pointer needs to be adjusted. EXAMPLE: consider the following tree: if node (1) is deleted, the right child of node(1) (that’s node (4)) become the left child of node (6). The new BST will be as follow: 8 9 6 1 7 4 8 9 6 4 7

Slide 32:

3. If the node to be deleted has two children, the node value is replaced by the (i) Smallest value in the Right subtree (or) (ii) Largest value in the Left subtree Example: consider the following tree: 10 12 6 5 9 7 4 11 8

Slide 33:

If the node(6) is to be deleted, then it’s value is replaced by smallest value in the right subtree (i.e. by 7). The new BST will be; 10 12 7 5 9 8 4 11

Algorithm for BST - deletion :

Algorithm for BST - deletion Algorithm deleteBST ( ref root < pointer>, val dltkey < key>) precondition: root is pointer to tree containing data to to be deleted. dltkey is key of node to be deleted. postcondition: node deleted & memory recycled, if dltkey not found, root unchanged. return : true if node deleted, false if not found 1. if ( root null) 1. return false

Slide 35:

2. end if 3. if (dltkey < root data.key) 1. return deleteBST (root left, dltkey) 4. elseif (dltkey > root data.key) 1. return deleteBST (root right,dltkey) 5. else delete node found, test for leaf node 1. if (root left null) 1. dltptr = root 2. root = root right 3. recycle (dltptr) 4. return true

Slide 36:

2. elseif (root right null) 1. dltptr = root 2. root = root left 3. recycle (dltptr) 4. return true 3. else node to be deleted not a leaf. Find largest node on left subtree 1. dltptr = root left 2. loop (dltptr right not null) 1. dltptr = dltptr right

Slide 37:

node found, move data and delete leaf node 3. root data = dltptr data 4. return deleteBST ( root left, dltptr data, key) 4. end if 6. end if End deleteBST

4. BINARY SERACH TREE WITH DUPLICATES :

4. BINARY SERACH TREE WITH DUPLICATES Definition The BST is permitted to contain two (or) more elements that have the same key is called “ Duplicate Binary Search Tree” (DBST). 6 3 6 1 2 20 5 1 1 8

Slide 39:

We can remove the requirement that all elements in a BST need “distinct keys”. Now we can make smaller changes in property-2 and property-3 (refer slide-4). Property-2: the value in the left subtree of the root are smaller than and equal to (<=) key in the root. propety-3: the value in the right subtree of the root are greater than and equal to(>=) the key in the root. The resulting tree is called “DBST”.

5. INDEXED BINARY SERACH TREE :

5. INDEXED BINARY SERACH TREE An Indexed BST, is derived from an ordinary BST-by adding the field “leftsize” to each tree node. This fields gives the number of elements in the nodes left subtree. 20 12 15 25 18 30 3 1 0 0 0 0 3- nodes

Slide 41:

30 40 5 2 2 1 0 0 2- nodes The above figures shows a Indexed BST. The number inside a node is the element key, the outside value of the node is the value of Leftside. Notice that the leftside also gives the index of an element with respect to the elements in its subtree. For (e.g.) from the above figures, the element (in sorted order) in the subtree with root 20 are (12,15,18,25,30). The index of the root is 3, which is equal to its Leftsize value.

Slide 42:

In the subtree with root 15, the elements (in sorted order) are 12,18. so the index of root element 15 is 1, and its leftsize value is also 1. ADT for Indexed Binary Search Tree Abstract Data Type Indexed BST { instances: same as for BST, except that each node has a leftsize field operations: get (k): return the element with key (k) get (index) : return the index th element

Slide 43:

put (k, x): put element ‘x’ with key (k) into the search tree. remove (k): remove the element with key (k) and return it. remove (index) : remove the index th element and return it. ascend ( ) : output all elements in ascending order of key }

6. APPLICATIONS :

6. APPLICATIONS 1. Histogramming 2. Best-fit Bin packing 3. Crossing Distribution

Algorithm to find the smallest node in a BST :

Algorithm to find the smallest node in a BST precondition : root is a pointer to a nonempty BST (or) subtree. Return : address of smallest node 1. if ( root left null) 1. return (root) 2. end if 3. return smallestBST( root left) end

Algorithm to find largest node in a BST :

Algorithm to find largest node in a BST precondition : root is a pointer to a nonempty BST (or) subtree. Return : address of largest node 1. if ( root right null) 1. return (root) 2. end if 3. return largestBST( root right) end

Slide 47:

Construction of Binary Search Tree

Slide 48:

Represent the following numbers in a BST form: 32,41,12,16,19,45,28,18,14 and parse the tree in (i) pre-order (ii) in-order (iii) post-order Step-1 Step-2 32 32 41

Slide 49:

Step-3 Step-4 32 41 12 32 41 12 16

Slide 50:

Step-5 Step-6 32 41 12 16 19 32 41 12 16 19 45

Slide 51:

Step-7 32 41 12 16 19 45 28

Slide 52:

Step-8 32 41 12 16 19 45 28 18

Slide 53:

Step-9 32 41 12 16 19 45 28 18 14

Slide 54:

(i) Pre-order (Root - Left - Right) 32, 12, 16, 14, 19, 18, 28, 41, 45 (ii) In-order (Left - Root - Right) 12, 14, 16, 18, 19, 28, 32, 41, 45 (iii) Post-order (Left – Right - Root ) 14, 18, 28, 19, 16, 12, 45, 41, 32