[go: up one dir, main page]
Scribd
Upload
34 views2 pages

FCP Tasks Binary Search Trees

The document describes functions for common binary search tree operations: 1) Mirroring a binary search tree so that greater values are in the left subtree and lesser in the right. 2) Performing a breadth-first search to print values. 3) Finding the successor of a given node. 4) Removing a node by handling cases if it has 0, 1, or 2 children. 5) Implementing left and right rotation functions for balance operations.

Uploaded by

JuliaZiębińska
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
34 views2 pages

FCP Tasks Binary Search Trees

The document describes functions for common binary search tree operations: 1) Mirroring a binary search tree so that greater values are in the left subtree and lesser in the right. 2) Performing a breadth-first search to print values. 3) Finding the successor of a given node. 4) Removing a node by handling cases if it has 0, 1, or 2 children. 5) Implementing left and right rotation functions for balance operations.

Uploaded by

JuliaZiębińska
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Fundamentals of Computer Programming

Binary search trees

t y p e d e f i n t T;

/∗ ∗ node o f a b i n a r y s e a r c h t r e e ∗/
s t r u c t node
{
/∗ ∗ v a l u e s t o r e d i n a b i n a r y s e a r c h t r e e ∗/
T value ;
/∗ ∗ p o i n t e r t o a l e f t c h i l d ∗/
node ∗ pLeft ;
/∗ ∗ p o i n t e r t o a r i g h t c h i l d ∗/
node ∗ pRight ;
};

Implement functions:
1.
/∗ ∗ The f u n c t i o n m i r r o r s a b i n a r y s e a r c h t r e e : g r e a t e r v a l u e s a r e now
s t o r e d i n a l e f t s u b s t r e e , l e s s v a l u e s −− i n a r i g h t s u b t r e e .
@param pRoot r o o t o f a t r e e ∗/
v o i d mirror ( node ∗ pRoot ) ;

2.
/∗ ∗ The f u n c t i o n s p r i n t s v a l u e s s t o r e d i n a t r e e w i t h b r e a d t h − f i r s t
s e a r c h . The f u n c t i o n s u s e s a ( s i n g l y or d o u b l e l i n k e d ) l i s t as a
FIFO queue .
@param pRoot r o o t o f a t r e e
∗/
v o i d breadth_first_search ( node ∗ pRoot ) ;

3.
/∗ ∗ The f u n c t i o n s e a r c h e s f o r a s u c c e s s o r o f a node . A s u c c e s s o r i s a
node t h a t h o l d s a n e x t v a l u e o f a key .
@param pRoot r o o t o f a t r e e
@param p P r e d e c e s s o r a node whose s u c c e s s o r i s s e a r c h e d f o r
@return s u c c e s s o r ' s a d d r e s s ( i f e x i s t s , o t h e r w i s e n u l l p t r )
∗/
node ∗ findSuccessor ( node ∗ pRoot , node ∗ pPredecessor ) ;

4.
/∗ ∗ The f u n c t i o n removes a node from a b i n a r y s e a r c h t r e e .
@warning The t a s k has f o u r c a s e s :
( 0 ) A node has no c h i l d r e n .
(1L) A node has o n l y a l e f t c h i l d .
(1R) A node has o n l y a r i g h t c h i l d .
( 2 ) A node has two c h i l d r e n . Hint : f i r s t f i n d a s u c c e s s o r , move t h e
v a l u e s t o r e d i n t h e s u c c e s s o r t o a node t o d e l e t e and d e l e t e t h e
s u c c e s s o r ( t h a t has no or one c h i l d ) .
@param pRoot r o o t o f a t r e e

1
@param pToDelete a node t o d e l e t e
∗/
v o i d removeNode ( node ∗ & pRoot , node ∗ pToDelete ) ;

5. Implement functions for left and right rotation in a binary search tree.

p p

B A
right rotation

A B
γ α

α β β γ
left rotation

The triangles (α, β, γ) represent subtrees (also empty trees – nullptr).

right_rotation(pRoot, p);

pRoot pRoot

p 12 q 12

8 4

4 9 15 1 8 15

1 7 11 7 9

11

left_rotation(pRoot, q);

(a)
/∗ ∗ The f u n c t i o n r o t a t e s a s u b t r e e l e f t .
@param pRoot r o o t o f a t r e e
@param q a p o i n t e r t o a s u b t r e e t o r o t a t e ∗/
v o i d left_rotation ( node ∗ & pRoot , node ∗ q ) ;
(b)
/∗ ∗ The f u n c t i o n r o t a t e s a s u b t r e e r i g h t .
@param pRoot r o o t o f a t r e e
@param pa p o i n t e r t o a s u b t r e e t o r o t a t e ∗/
v o i d right_rotation ( node ∗ & pRoot , node ∗ p ) ;

You might also like