Binary Search Tree

Binary Trees, Expression Trees, Tree Traversal

1. TREES

2. Trees
•Atreeisacollectionofnodes
–Thecollectioncanbeempty
–Ifnotempty,atreeconsistsofadistinguished
noder(theroot),andzeroormorenonempty
subtreesT
1,T
2,....,T
k,eachofwhoserootsare
connectedbyadirectededgefromr.

3. Terminologies
•Parent
–Immediate predecessor of a node
•Child
–Immediate successors of a node (left child,right
child)
•Leaves
–Leaves are nodes with no children
•Sibling
–nodes with same parent

4. Terminologies
•Level
–Rankinthehierarchy
•Lengthofapath
–numberofedgesonthepath
•Heightofanode(Depth)
–maxnoofnodesinapathstartingfromthe
rootnodetoaleafnode.
•Degree
–Maxnoofchildrenthatispossibleforanode
•Ancestoranddescendant
–Ifthereisapathfromn1ton2
–n1isanancestorofn2,n2isadescendantof
n1
–Properancestorandproperdescendant

5. Terminologies

6. Example: Expression Trees
•Leaves are operands (constants or variables)
•The internal nodes contain operators

7. Binary Trees
•Isafinitesetofnodes
–thatiseitheremptyor
–consistsofarootandtwodisjointtreesasleft
subtreeandrightsubtree.
–binarytreeofhthcanhave
atmost2^h-1nodes
–Fullbinarytree
–Completebinarytree
56
26 200
18 28 190 213
12 2427

8. Binary Tree Representation
•Linear Representation
–Parent (i)=[i/2]
–Lchild(i)= 2 * i
–Rchild(i)=(2*i) +1
•Linked Representation
–three fields
•leftchild
•data
•rightchild

9. Tree Traversal
•Used to print out the data in a tree in a certain
order
•Pre-order traversal
•Post-order traversal
•In-order traversal

10. Preorder Traversal
•Preorder traversal
–root, left, right
–prefix expression
++a*bc*+*defg

11. Postorder Traversal
•Postorder traversal
–left, right, root
–postfix expression
abc*+de*f+g*+

12. Inorder Traversal
•Inorder traversal
–left, root, right
–infix expression
a+b*c+d*e+f*g

13. Convert a Generic Tree to a Binary Tree

14. Binary Search Trees
•Binary search tree
–Every node has a unique key.
–The keys in a nonempty left subtreeare smaller
than the key in the root .
–The keys in a nonempty right subtreeare
greaterthan the key in the root .
–The left and right subtrees are also binary
search trees.

15. BST –Representation
•Represented by a linked data structure of nodes.
•root(T)points to the root of tree T.
•Each node contains fields:
–key
–left–pointer to left child: root of left subtree.
–right–pointer to right child : root of right subtree.
–p–pointer to parent. p[root[T]] = NIL (optional).

16. Binary Search Tree Property
•Stored keys must satisfy
the binary search tree
property.
–yin left subtree of
x, then key[y] 
key[x].
–yin right subtree
of x, then key[y] 
key[x].
56
26 200
18 28 190 213
12 2427

17. Binary Search Trees
A binary search tree
Not a binary search tree

18. Binary Search Trees
•Average depthof a node is O(log N)
•Maximum depthof a node is O(N)
The same set of keys may have different BSTs

19. Querying a Binary Search Tree
•Pseudocode
–ifthetreeisempty
returnNULL
–elseiftheiteminthenodeequalsthetarget
returnthenodevalue
–elseiftheiteminthenodeisgreaterthanthe
target
returntheresultofsearchingtheleftsubtree
–elseiftheiteminthenodeissmallerthanthe
target
returntheresultofsearchingtherightsubtree

20. Tree Search
Tree-Search(x, k)
1. ifx =NILor k = key[x]
2. thenreturn x
3. ifk <key[x]
4. thenreturn Tree-Search(left[x], k)
5. elsereturn Tree-Search(right[x], k)
Running time: O(h)
56
26 200
18 28190 213
122427

21. Iterative Tree Search
Iterative-Tree-Search(x, k)
1. whilex NILandk key[x]
2. doifk <key[x]
3. thenx left[x]
4. elsex right[x]
5. returnx
The iterative tree search is more efficient on most computers.
The recursive tree search is more straightforward.
56
26 200
18 28190 213
122427

23. Querying a Binary Search Tree
•Alldynamic-setsearchoperationscanbesupportedin
O(h)time.
•h=(lgn)forabalancedbinarytree(andforan
averagetreebuiltbyaddingnodesinrandomorder.)
•h=(n)foranunbalancedtreethatresemblesa
linearchainofnnodesintheworstcase.

24. Finding Min & Max
Tree-Minimum(x) Tree-Maximum(x)
1. whileleft[x]NIL 1. whileright[x]NIL
2. dox left[x] 2. dox right[x]
3. returnx 3. returnx
The binary-search-tree property guarantees that:
»The minimumis located at the left-mostnode.
»The maximumis located at the right-mostnode.

25. Predecessor and Successor
•Successorofnodexisthenodeysuchthatkey[y]isthe
smallestkeygreaterthankey[x].
•ThesuccessorofthelargestkeyisNIL.
•Twocases:
–Ifnodexhasanon-emptyrightsubtree,thenx’ssuccessoris
theminimumintherightsubtreeofx.
–Ifnodexhasanemptyrightsubtree,then:
•Aslongaswemovetotheleftupthetree(moveup
throughrightchildren),wearevisitingsmallerkeys.
•x’ssuccessoryisthenodethatxisthepredecessorof(xis
themaximuminy’sleftsubtree).
•Inotherwords,x’ssuccessory,isthelowestancestorofx
whoseleftchildisalsoanancestorofx.

26. Pseudo-code for Successor
Tree-Successor(x)
1. if right[x]NIL
2. thenreturn Tree-Minimum(right[x])
3. yp[x]
4. whiley NIL andx = right[y]
5. dox y
6. yp[y]
7. returny
Code for predecessor is symmetric.
Running time:O(h)
56
26 200
18 28190 213
12 2427

27. 27
Predecessor
Def:predecessor(x ) =y, such that key [y]is the
biggest key < key [x]
E.g.:predecessor (15) =
predecessor (9) =
predecessor (7) =
Case 1: left (x)is non empty
predecessor(x) = the maximum in left (x)
Case 2: left (x)is empty
go up the tree until the current node is a right child:
predecessor(x ) is the parent of the current node
if you cannot go further (and you reached the root):
xis the smallest element
3
2 4
6
7
13
15
18
17 20
9
13
7
6
x
y

28. iftreeisempty
createarootnodewiththenewkey
else
comparekeywiththetopnode
ifkey=nodekey
replacethenodewiththenewvalue
elseifkey>nodekey
comparekeywiththerightsubtree:
ifsubtreeisemptycreatealeafnode
elseaddkeyinrightsubtree
elsekey<nodekey
comparekeywiththeleftsubtree:
ifthesubtreeisemptycreatealeafnode
elseaddkeytotheleftsubtree
BST Insertion

29. 9
7
5
4 68
Case 1:The Tree is Empty
Set the root to a new node containing the item
Case 2:The Tree is Not Empty
Call a recursive helper method to insert the item
10
10 > 7
10 > 9
10
BST Insertion

30. BST Insertion –Pseudocode
Tree-Insert(T, z)
yNIL
x root[T]
whilexNIL
doy x
ifkey[z] < key[x]
thenx left[x]
elsex right[x]
p[z] y
if y = NIL
thenroot[t] z
elseifkey[z] < key[y]
then left[y] z
elseright[y] z
•Ensurethebinary-
search-treeproperty
holdsafterchange.
•Insertioniseasierthan
deletion.
56
26 200
18 28190 213
12 2427

31. Analysis of Insertion
•Initialization:O(1)
•While loop in lines 3-7
searches for place to
insert z, maintaining
parent y.
This takes O(h) time.
•Lines 8-13 insert the
value: O(1)
TOTAL: O(h) time to
insert a node.
Tree-Insert(T, z)
1.yNIL
2.x root[T]
3.whilexNIL
4. doy x
5. ifkey[z] < key[x]
6. then x left[x]
7. else x right[x]
8.p[z] y
9.if y = NIL
10. then root[t] z
11. else if key[z] < key[y]
12. then left[y] z
13. else right[y] z

32. I->ifthetreeisemptyreturnfalse
II->Attempttolocatethenodecontainingthetarget
usingthebinarysearchalgorithm
ifthetargetisnotfoundreturnfalse
elsethetargetisfound,soremoveitsnode:
Case1:ifthenodehas2emptysubtrees
-replacethelinkintheparentwithnull
Case2:ifthenodehasaleftandarightsubtree
-replacethenode'svaluewiththemaxvaluein
theleftsubtree
-deletethemaxnodeintheleftsubtree
BST Deletion

33. Case3:ifthenodehasnoleftchild
-linktheparentofthenodetotheright
(non-empty)subtree
Case4:ifthenodehasnorightchild
-linktheparentofthetargettotheleft
(non-empty)subtree
BST Deletion

34. 9
7
5
64 8 10
9
7
5
68 10
Case 1:removing a node with 2 EMPTY SUBTREES
parent
cursor
BST Deletion
Removing 4
replace the link in the
parent with null

35. Case 2:removing a node with 2 SUBTREES
9
7
5
68 10
9
6
5
8 10
cursor
cursor
-replace the node's value with the max value in the
left subtree
-delete the max node in the left subtree
44
Removing
7
BST Deletion

36. 9
7
5
68 10
9
7
5
68 10
cursor
cursor
parent
parent
-the node has no left child:
-link the parent of the node
to the right (non-empty) subtree
Case 3:removing a node with 1 EMPTY SUBTREE
BST Deletion

37. 9
7
5
8 10
9
7
5
8 10
cursor
cursor
parent
parent
-the node has no right child:
-link the parent of the node to the
left (non-empty) subtree
Case 4:removing a node with 1 EMPTY SUBTREE
Removing 5
4 4
BST Deletion

38. Deletion –Pseudocode
TREE-DELETE(T, z)
1.if left[z]= NIL or right[z]= NIL
2.then y ←z
3.else y ← TREE-SUCCESSOR(z)
4.if left[y]NIL
5.then x ←left[y]
6.else x ←right[y]
7.if x NIL
8.then p[x] ←p[y]
z has one child
z has 2 children
15
16
20
18 23
6
5
123
7
10 13
y
x

39. Deletion –Pseudocode
TREE-DELETE(T, z)
9.if p[y] = NIL
10.then root[T] ← x
11.else if y = left[p[y]]
12. then left[p[y]] ← x
13. else right[p[y]] ← x
14.if y z
15.then key[z] ← key[y]
16. copy y’s satellite data into z
17.return y
15
16
20
18 23
6
5
123
7
10 13
y
x
Running time: O(h)