ppt
The following are some codes and notes taken from the ppt.
Tree¶
inorder¶
/*Iterative*/
void inorder ( tree_ptr tree )
{ if ( tree ) {
inorder ( tree->Left );
visit ( tree->Element );
inorder ( tree->Right );
}
}
Thread Binary Tree¶
- Rule 1: If Tree->Left is null, replace it with a pointer to the inorder predecessor of Tree.
- Rule 2: If Tree->Right is null, replace it with a pointer to the inorder successor of Tree.
- Rule 3: There must not be any loose threads. Therefore a threaded binary tree must have a head node of which the left child points to the first node.
Binary Search Tree¶
Delete¶
- Delete a leaf node : Reset its parent link to NULL.
- Delete a degree 1 node : Replace the node by its single child.
- Delete a degree 2 node :
- Replace the node by the largest one in its left subtree or the smallest one in its right subtree.
- Delete the replacing node from the subtree.
Position Find( ElementType X, SearchTree T ) { if ( T == NULL ) return NULL; /* not found in an empty tree */ if ( X < T->Element ) /* if smaller than root */ return Find( X, T->Left ); /* search left subtree */ else if ( X > T->Element ) /* if larger than root */ return Find( X, T->Right ); /* search right subtree */ else /* if X == root */ return T; /* found */ } /*Iterative*/ Position Iter_Find( ElementType X, SearchTree T ) { /* iterative version of Find */ while( T ){ if ( X == T->Element ) return T ; /* found */ if ( X < T->Element ) T = T->Left ; /*move down along left path */ else T = T-> Right ; /* move down along right path */ } /* end while-loop */ return NULL ; /* not found */ } Position FindMin( SearchTree T ) { if ( T == NULL ) return NULL; /* not found in an empty tree */ else if ( T->Left == NULL ) return T; /* found left most */ else return FindMin( T->Left ); /* keep moving to left */ } Position FindMax( SearchTree T ) { if ( T != NULL ) while ( T->Right != NULL ) T = T->Right; /* keep moving to find right most */ return T; /* return NULL or the right most */ } /*indsert*/ SearchTree Insert( ElementType X, SearchTree T ) { if ( T == NULL ) { /* Create and return a one-node tree */ T = malloc( sizeof( struct TreeNode ) ); if ( T == NULL ) FatalError( "Out of space!!!" ); else { T->Element = X; T->Left = T->Right = NULL; } } /* End creating a one-node tree */ else /* If there is a tree */ if ( X < T->Element ) T->Left = Insert( X, T->Left ); else if ( X > T->Element ) T->Right = Insert( X, T->Right ); /* Else X is in the tree already; we'll do nothing */ return T; /* Do not forget this line!! */ } /*delete*/ SearchTree Delete( ElementType X, SearchTree T ) { Position TmpCell; if ( T == NULL ) Error( "Element not found" ); else if ( X < T->Element ) /* Go left */ T->Left = Delete( X, T->Left ); else if ( X > T->Element ) /* Go right */ T->Right = Delete( X, T->Right ); else /* Found element to be deleted */ if ( T->Left && T->Right ) { /* Two children */ /* Replace with smallest in right subtree */ TmpCell = FindMin( T->Right ); T->Element = TmpCell->Element; T->Right = Delete( T->Element, T->Right ); } /* End if */ else { /* One or zero child */ TmpCell = T; if ( T->Left == NULL ) /* Also handles 0 child */ T = T->Right; else if ( T->Right == NULL ) T = T->Left; free( TmpCell ); } /* End else 1 or 0 child */ return T; }
Heaps¶
/*initialize*/
PriorityQueue Initialize( int MaxElements )
{
PriorityQueue H;
if ( MaxElements < MinPQSize )
return Error( "Priority queue size is too small" );
H = malloc( sizeof ( struct HeapStruct ) );
if ( H ==NULL ) return FatalError( "Out of space!!!" );
/* Allocate the array plus one extra for sentinel */
H->Elements = malloc(( MaxElements + 1 ) * sizeof( ElementType ));
if ( H->Elements == NULL ) return FatalError( "Out of space!!!" );
H->Capacity = MaxElements;
H->Size = 0;
H->Elements[ 0 ] = MinData; /* set the sentinel */
return H;
}
/* H->Element[ 0 ] is a sentinel */
void Insert( ElementType X, PriorityQueue H )
{
int i;
if ( IsFull( H ) ) {
Error( "Priority queue is full" );
return;
}
for ( i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2 ){
H->Elements[ i ] = H->Elements[ i / 2 ];
H->Elements[ i ] = X;
}
}
T (N) = O ( log N )
ElementType DeleteMin( PriorityQueue H )
{
int i, Child;
ElementType MinElement, LastElement;
if ( IsEmpty( H ) ) {
Error( "Priority queue is empty" );
return H->Elements[ 0 ]; }
MinElement = H->Elements[ 1 ]; /* save the min element */
LastElement = H->Elements[ H->Size-- ]; /* take last and reset size */
for ( i = 1; i * 2 <= H->Size; i = Child ) { /* Find smaller child */
Child = i * 2;
if (Child != H->Size && H->Elements[Child+1] < H->Elements[Child])
Child++;
if ( LastElement > H->Elements[ Child ] ) /* Percolate one level */
H->Elements[ i ] = H->Elements[ Child ];
else break; /* find the proper position */
}
H->Elements[ i ] = LastElement;
return MinElement;
}
T (N) = O ( log N )
The Disjoint Set¶
S [ element ] = the element’s parent.
union by size: -- Always change the smaller tree¶
- S [ Root ] = – size
- Let T be a tree created by union-by-size with N nodes, then \(height(T) < ⌊log_2(n)⌋ + 1\)
- Time complexity of N Union and M Find operations is now O( N + M log2 N ).
union by height：-- Always change the shallow tree¶
Algorithm:
{ /* step 1: read the relations in */
Initialize N disjoint sets;
while ( read in a ~ b ) {
if ( ! (Find(a) == Find(b)) )
Union the two sets;
} /* end-while */
/* step 2: decide if a ~ b */
while ( read in a and b ){
if ( Find(a) == Find(b) ) output( true );
else output( false );
}
}
void SetUnion ( DisjSet S, SetType Rt1, SetType Rt2 )
{
S [ Rt2 ] = Rt1 ;
}
SetType Find ( ElementType X, DisjSet S )
{
for ( ; S[X] > 0; X = S[X] ) ;
return X ;
}
/*Algorithm using union-find operations*/
{ Initialize Si = { i } for i = 1, ..., 12 ;
for ( k = 1; k <= 9; k++ ) { /* for each pair i j */
if ( Find( i ) != Find( j ) )
SetUnion( Find( i ), Find( j ) );
}
}
/*path compression*/
SetType Find ( ElementType X, DisjSet S )
{
if ( S[ X ] <= 0 ) return X;
else return S[ X ] = Find( S[ X ], S );
}
SetType Find ( ElementType X, DisjSet S )
{ ElementType root, trail, lead;
for ( root = X; S[ root ] > 0; root = S[ root ] )
; /* find the root */
for ( trail = X; trail != root; trail = lead ) {
lead = S[ trail ] ;
S[ trail ] = root ;
} /* collapsing */
return root ;
}