: ( Data structure CS242 ) .! ( )



: 1 2 [3] 4 5

lolitta
08-08-11, 09:18 PM
2.3 - COLLISION RESOLUTION





:
1- open address :
2-key offset
3- linked list
4-bucket hashing


1- open address
.. prime area

:
1)linear probr
2)quadratic probe
.

linear probr
+1

:
12 12
+1
13 ..
14 ..


http://im9.gulfup.com/2011-08-08/1312827189451.jpg








2-key offset
double hashingh ..

:
offset = [ key \ listSize ]
address = [ ( offset + oldAddress) MOD listSize ]

:

http://im9.gulfup.com/2011-08-08/1312827431951.jpg





offset = [ 166702 \ 307 ] = 543
address = [ ( 543 + 001) MOD 307 ] = 237

237
237


offset = [ 166702 \ 307 ] = 543
address = [ ( 543 + 237) MOD 307 ] = 166

166

probe
237 probe1
166 probe2

probe





3- linked list

:

http://im9.gulfup.com/2011-08-08/1312827248291.jpg

1 ..
overflew area



stack
LIFO







4-bucket hashing
( )



:

http://im9.gulfup.com/2011-08-08/1312827339291.jpg
1 .. 1 1 2
1 2
1 1 .. 2
..

:
1-
2- ..





SUMMARY ( VERY IMPRTANT )

1- searching is the process of finding the location of the target among list of objects.
2- there are teo bacis searching methods for arrys : sequential search and binary search.
3- the sequential search is normally used when a list is not sorted , it start at the begining of the list and searches until find the the data or hits the end of the list.
4- the sequential search can also search a sorted list, in this case we can terminate the search when the target is less than the current element.
5- if ann arry is sorted we can use a more effeicient algorithem called the binarry search.
6- the efficincy of the sequential search list is O(n).
7- the efficincy of the binary search list is O(log2n).
8- in direct hashing the key is the address without any algorithemc manuplation.
9- in subtraction hashing the key is transformed to an address by subtracting a fixed number from it.
10- in modulo-division hashing the key is divided by the list size, recommended to be a prime number, and the remainder pluse 1 is used as the address.
11- in digit extraction hashing , selected digit are extracted from the key and used as an address.

lolitta
08-08-11, 10:02 PM

sorting





fahad777
08-08-11, 10:08 PM

sorting







Quadratic Sort
1/ Bubble Sort
2/ Selection sort
3 / Insertion Sort

Divide and Conquer sorting

1/ Merge sort
2/ Quick sort




fahad777
08-08-11, 10:24 PM

BST
http://up.top4top.net/downloadf-top4top_509b3c156f1-pdf.html

B_TREE
http://up.top4top.net/downloadf-top4top_509b3c156f2-pdf.html

Queue
http://up.top4top.net/downloadf-top4top_509b3c156f3-pdf.html

STACK
http://up.top4top.net/downloadf-top4top_509b3c156f4-pdf.html

LinkedList
http://up.top4top.net/downloadf-top4top_509b3c156f5-pdf.html

Sorting
http://up.top4top.net/downloadf-top4top_509b3c156f6-pdf.html



lolitta
08-08-11, 11:28 PM



OuTLoW
08-08-11, 11:49 PM

:)






.
09-08-11, 12:12 AM
=$
=)


<3

fahad777
09-08-11, 12:31 AM
=$
=)


<3




OuTLoW
09-08-11, 12:38 AM

fahad777
09-08-11, 12:41 AM



NVIDIA
09-08-11, 01:38 AM


ɿ

My story
09-08-11, 02:12 AM
..
..

fahad777
09-08-11, 02:34 AM


ɿ



09-08-11, 03:17 AM

..W..
09-08-11, 03:32 AM
6- an abstract data type(ADT) is a data declarayion packaged togather with the operations that are meaningful for the data type

!! ..
+
!!

lolitta
09-08-11, 04:51 AM
chapter 11 : Advanced sorting concepts

..





11.1 - GENERAL SORT CONCEPTION

6 .. 5


NOTE :
- Sorting is one of the most common data-processing applications.
- Sorting algorithms are classified as either internal or external .




11.2 - INSERTION SORTS

:
1- straight insertion sort
2- ΩΩΩΩl sort
((( .. )))



1- straight insertion sort

:
..
sorted and unsorted

http://im9.gulfup.com/2011-08-09/1312853112431.jpg


23
http://im9.gulfup.com/2011-08-09/1312853112962.jpg

78
23 .. 23 23
http://im9.gulfup.com/2011-08-09/1312853112403.jpg

45
23 78
http://im9.gulfup.com/2011-08-09/1312853112624.jpg

8

http://im9.gulfup.com/2011-08-09/1312853112725.jpg

32
http://im9.gulfup.com/2011-08-09/1312853113866.jpg

56
http://im9.gulfup.com/2011-08-09/1312853113317.jpg





:
pass


NOTE:
-in the stright insertion sort the list at any moment is divided into sorted and unsorted sublists, in each pass the first element of the unsorted sublist is inserted into the sorted sublist.
- the sright insertion sort efficincy is O(n^2)




11.3 - SELECTION SORT


1- stright selection sort
2- heap sort .
((( .. )))


1- stright selection sort
sorted and unsorted
http://im9.gulfup.com/2011-08-09/1312853618421.jpg




NOTE :
in each pass of the selection sort , the smallest element is selected from the unsorted sublist and exchanged with the element at the beginning of the unsorted list







http://im9.gulfup.com/2011-08-09/1312854101781.jpg




8 23 .. 8
http://im9.gulfup.com/2011-08-09/1312854101482.jpg

23 78
http://im9.gulfup.com/2011-08-09/1312854101353.jpg

32 45
http://im9.gulfup.com/2011-08-09/131285410174.jpg

56 78
http://im9.gulfup.com/2011-08-09/1312854101385.jpg



http://im9.gulfup.com/2011-08-09/1312854101616.jpg

NOTE :
the stright selection sort efficincy is O(n^2)



11.4 - EXCHANGE SORTS

:
1- bubble sort
2- quick sort
((( )))


1- bubble sort

..



:

75321



75321
57321
53721
53271
53217 ..... pass1
7

53217
35217
32517
32157 .... pass2
5

32157
23157
21357 ..... pass3
3

21357
12357 .... pass4
12357







11.5 - EXTERNAL SORTS
:
1- Merge sort .

..
..

:

http://im9.gulfup.com/2011-08-09/1312854591241.jpg

lolitta
09-08-11, 04:55 AM




pdf

..






..W..
09-08-11, 05:04 AM
~~>



,,,^_^

09-08-11, 06:15 AM






lolitta
09-08-11, 08:13 AM
chapter 3 : linked list



http://sub5.rofof.com/08pzqko8/Linked_List.html


Sweet gilr
09-08-11, 01:32 PM











sosita
09-08-11, 02:29 PM

Sweet gilr
09-08-11, 03:04 PM


~

akay
09-08-11, 03:52 PM


...

..

.
09-08-11, 08:08 PM

:cry(1)::cry(1):

nonnaSaleh
09-08-11, 08:22 PM
@@

s.r.w
09-08-11, 08:32 PM
<<

:(

:"(


:(

Sweet gilr
09-08-11, 09:21 PM
.





hot
09-08-11, 09:23 PM




.. Give the inorder,
preorder and postorder
traversal of the binary
search tree.

:)

Sweet gilr
09-08-11, 10:40 PM
^^^



Sweet gilr
09-08-11, 10:48 PM
inorder +pre +pos





3
inorder
preorder
postorder

>>

( inorder )


LNR
Left >NODE>Right

+ +

2\ preorder
N>L>R


3\ postorder
L>R>N

-------





----



subtree







Sweet gilr
09-08-11, 11:01 PM




.. Give the inorder,
preorder and postorder
traversal of the binary
search tree.

:)




:) : :smile4:

:cry(1):


inorder (LNR) : B -E- K- L- N- O- P -S -T


preorder (NLR) : K- E- B- P- L- N- O- T- S

postorder (LRN) : B- E- O- N- L- S- T- P- K


I hope it's right

good luck

OuTLoW
09-08-11, 11:15 PM

ʿ

akay
09-08-11, 11:21 PM


..

fahad777
09-08-11, 11:45 PM
:) : :smile4:

:cry(1):


inorder (LNR) : B -E- K- L- N- O- P -S -T


preorder (NLR) : K- E- B- P- L- N- O- T- S

postorder (LRN) : B- E- O- N- L- S- T- P- K


I hope it's right

good luck



Sweet gilr
10-08-11, 12:10 AM
Yhoooo



s.r.w
10-08-11, 12:43 AM





HASHED LIST SEARCH

Key
Address












OuTLoW
10-08-11, 12:46 AM

s.r.w
10-08-11, 12:47 AM








s.r.w
10-08-11, 12:47 AM





nonnaSaleh
10-08-11, 12:50 AM
..

s.r.w
10-08-11, 12:56 AM





:D

"" Introduction to Data
Structures & Algorithm "

:D

!!

lolitta
10-08-11, 01:35 AM
s.r.w

<<








:)





4


:)


:)

OuTLoW
10-08-11, 01:40 AM




lolitta
10-08-11, 01:59 AM
chapter 4 : stacks

..



stack of books





:
a stack is a linear list in wich data can be inserted an deleted from one end, called top.it's a last-in-first-out (LIFO) data structure

top

:
1- search
2- ..
3- sorting
4-
5- retreve copy
6- traverce





4.1 - BASIC STACK OPERATION

1- push
2- pop
3- stack top





1- push

..
..



overflow

...

.... ....






2- pop






underflow

.... ....






3- stack top




.... ....


NOTE:
the three basic stack operations are push,pop and stack top




4.2 - STACK LINKED LIST IMP;EMENTATION





http://im9.gulfup.com/2011-08-10/1312930428151.jpg


1-create stack

..
.. null


http://im9.gulfup.com/2011-08-10/1312930428652.jpg


2- push stack

:
1-
2-
3-

http://im9.gulfup.com/2011-08-10/1312930428133.jpg


3-pop stack

:
1-
2-

http://im9.gulfup.com/2011-08-10/1312930428224.jpg


4- stack top


http://im9.gulfup.com/2011-08-10/1312930428675.jpg




5- empty stack

http://im9.gulfup.com/2011-08-10/1312930428236.jpg



6-full stack

http://im9.gulfup.com/2011-08-10/1312930428977.jpg


7- stack count

http://im9.gulfup.com/2011-08-10/1312930428178.jpg


8- destroy stack

http://im9.gulfup.com/2011-08-10/1312930428499.jpg


ADT
ADT
ADT ..

the ADT will be :
createStack(stack)
pushStack(stack,e)
popStack(stack,e)
stacktop(stack,e)
emptyStack(stack)
fullStack(stack)
stackcount(stack)
destroyStack(stack)




Sweet gilr
10-08-11, 02:03 AM


( )

Sweet gilr
10-08-11, 02:05 AM

/

OuTLoW
10-08-11, 02:10 AM










lolitta
10-08-11, 02:23 AM
stack applications
1-reversing data
2-parsing data
3-postponement
4- back tracking




lolitta
10-08-11, 02:26 AM



















OuTLoW
10-08-11, 03:17 AM
STACK APPLICATIONS
PARANTHESES BALANCE
ALGEBRAIC EXPRESSION/ INFIX/PREFIX/POSTFIX


QUEUE
TREE

Sweet gilr
10-08-11, 03:31 AM
ǿ




Sweet gilr
10-08-11, 03:35 AM
 .




s.r.w
10-08-11, 04:07 AM




.. " "



:@



!!

s.r.w
10-08-11, 04:09 AM









:)

http://sites.google.com/site/rkamjad/system/app/pages/recentChanges


.
10-08-11, 04:15 AM
..

NVIDIA
10-08-11, 04:21 AM


NVIDIA
10-08-11, 04:29 AM
:) : :smile4:

:cry(1):


inorder (LNR) : B -E- K- L- N- O- P -S -T


preorder (NLR) : K- E- B- P- L- N- O- T- S

postorder (LRN) : B- E- O- N- L- S- T- P- K


I hope it's right

good luck

inorder :
B-E-K-O-N-L-P

...


~~~~
10-08-11, 05:29 AM
inorder (LNR) : B -E- K- L- N- O- P -S -T

: inorder abc.... 123...


..W..
10-08-11, 05:41 AM
efficincy
Best Case !!

..W..
10-08-11, 05:43 AM
inorder (LNR) : B -E- K- L- N- O- P -S -T

: inorder abc.... 123...




!!!

,,, :@

10-08-11, 06:27 AM
,
:( ,
=\

qazqazzzz
10-08-11, 06:32 AM
4. Write a function that checks parentheses on a mathematic equation. (use a stack of character) (8 points)
Answer:


bool Stack::checkParen(char * s)
{
Stack temp;
int i=0;
while (s[i]!='\0')
{
if (s[i]=='(')
temp.push('(');
else if (s[i]==')') {
if (temp.isEmpty())
return false;
else
temp.pop();
}
i++;
}

if (temp.isEmpty())
return true;
return false;
}

5. Write a function that compresses a string by deleting all space characters in the string. (use a queue of character) (8 points)

void deleteSpaces(char *s)
{
int i=0;
Queue T;
while(s[i]!='\0')
{
if(s[i] != ' ')
T.Enqueue(s[i]);
i++;
}
i=0;
while(!T.isEmpty())
{
s[i]=T.Dequeue();
i++;
}
s[i]='\0';
}




:(




....



qazqazzzz
10-08-11, 07:57 AM
:$


2

:(

Sweet gilr
10-08-11, 02:32 PM








!!






fahad777
10-08-11, 03:07 PM
:038:

:9:

:7890:

3



o(n) :D

60

!!!!!!!!!!!!!!!



:033102bigangry_1_pr




fahad777
10-08-11, 03:08 PM








!!








hot
10-08-11, 03:17 PM
:) : :smile4:

:cry(1):


inorder (LNR) : B -E- K- L- N- O- P -S -T


preorder (NLR) : K- E- B- P- L- N- O- T- S

postorder (LRN) : B- E- O- N- L- S- T- P- K


I hope it's right

good luck



inorder (LNR) : B -E- K- L- N- O- P -S -T


LinkedList









...!!!

============




OuTLoW
10-08-11, 03:38 PM
.




NVIDIA
10-08-11, 03:43 PM
.. ..
..

..

Sweet gilr
10-08-11, 04:25 PM


...





Sweet gilr
10-08-11, 04:34 PM
inorder :
B-E-K-O-N-L-P

...





^^
inorder




( )






<<<

akay
10-08-11, 04:39 PM


!!

..

....

:(

lolitta
10-08-11, 04:46 PM







80 % 90%










NVIDIA
10-08-11, 05:02 PM
^^
inorder




( )






<<<

:)

lolitta
10-08-11, 05:07 PM

<<



39

<<




mahawy
10-08-11, 05:17 PM





!!!



.........


akay
10-08-11, 05:58 PM

s.r.w
10-08-11, 06:03 PM

akay
10-08-11, 06:06 PM
:033102bigangry_1_pr

NVIDIA
10-08-11, 06:16 PM


.. ..



60 47

:)

Sweet gilr
10-08-11, 06:26 PM
:)








8
5 9

8
5
4





inorder









10-08-11, 06:27 PM
40

Sweet gilr
10-08-11, 06:34 PM

10-08-11, 06:43 PM

Sweet gilr
10-08-11, 06:49 PM










Sweet gilr
10-08-11, 07:11 PM


http://arabsh.com/c5crd3rwmdl6.html



Sweet gilr
10-08-11, 07:12 PM






http://www.algorithmist.com/index.php/Stable_Sort


************

hot
10-08-11, 07:13 PM


31 60






mahawy
10-08-11, 08:00 PM


...........

Sweet gilr
10-08-11, 08:52 PM

10-08-11, 09:02 PM
!!!!

.
10-08-11, 09:14 PM











- -


!!!!!!!


"(

hot
10-08-11, 09:26 PM
^^^^



17 12 12



,,

10-08-11, 09:29 PM
^^






10-08-11, 09:33 PM

nonnaSaleh
10-08-11, 09:57 PM

:/

10-08-11, 10:01 PM
http://www.youtube.com/watch?v=9DyhmGQNAhA
^^



>>> :(:(:(

.
10-08-11, 10:04 PM
hot
"(
..
..



"( ..


..
=)

Sweet gilr
10-08-11, 10:41 PM


15










Sweet gilr
10-08-11, 10:43 PM










10-08-11, 10:53 PM


SIMPLE GIRL
10-08-11, 11:28 PM
:( :(

s.r.w
10-08-11, 11:56 PM
:(

:(

:(

Sweet gilr
11-08-11, 12:16 AM
<




<




wwwwwwwwww
11-08-11, 12:18 AM
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^




( )




(( ))
















lolitta
11-08-11, 01:23 AM
4.3 - STACK APPLICATIONS



4
1-reversing
2- parsing
3-postponing
4-back tracking



1-reversing


1 2 3 .. 3 2 1

2

.. ..





2- parsing

parsing is any logic that breaks data into independent pieces for further processing
.. ..


( ( A + B ) / C





( A + B ) / C )



..
..

... ...


( (A + B ) * C)

.. ..
( A + B ) * C)


A + B) * C)

..
..
.. ..






3-postponing

3 :
post & pre & in

postfix : a b + <<
infix : a + b
pre : + a b <<




( ( ( A + B) * C) / D)




prefix :



: = ( ( ( + A B ) * C) / D) : = ( ( *( + A B ) C) / D)

: = ( /( *( + A B ) C) D)
.. : / * + A B C D





postfix :


( ( ( /A B + ) C * ) D )
= A B + C * D / <<<<

..


.. 57


:
A + B * C - D / E

3






: + * - /
: A B C D E

..
..



..

:

:

http://store2.up-00.com/Jun11/Kzz14120.jpg

A ..
http://store2.up-00.com/Jun11/K3114120.jpg

+ ..
http://store2.up-00.com/Jun11/GLZ14120.jpg

B A
http://store2.up-00.com/Jun11/pKn14120.jpg

* .. .. +
http://store2.up-00.com/Jun11/VjP14120.jpg

C
http://store2.up-00.com/Jun11/RKT14122.jpg

- * .. + -
http://store2.up-00.com/Jun11/9iV14421.jpg

D
http://store2.up-00.com/Jun11/Gso14421.jpg


/ -
http://store2.up-00.com/Jun11/GBJ14421.jpg

E
http://store2.up-00.com/Jun11/bo314421.jpg

.. / -
/
http://store2.up-00.com/Jun11/fBV14421.jpg

-
http://store2.up-00.com/Jun11/LRZ14421.jpg


http://store2.up-00.com/Jun11/Zze14647.jpg


..




61

2 4 6 + *


http://store2.up-00.com/Jun11/Vfi14848.jpg

+
http://store2.up-00.com/Jun11/cwa14848.jpg

*
http://store2.up-00.com/Jun11/ewp14848.jpg


http://store2.up-00.com/Jun11/Qh214848.jpg


4-back tracking ..



4

s.r.w
11-08-11, 01:25 AM
:(


<3

.
11-08-11, 01:46 AM
...

badr0
11-08-11, 02:07 AM
, ^^

hero060
11-08-11, 02:18 AM
.........
prefix postfix infix ....
........

postfix infix ...

Sweet gilr
11-08-11, 03:02 AM
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^




( )




(( ))

















^^^^^^^^^^



<




OuTLoW
11-08-11, 03:15 AM
ӿ

11-08-11, 03:19 AM

,,,,

:8:

:)

,,,,

. Mz .
11-08-11, 03:19 AM
.........
prefix postfix infix ....
........

postfix infix ...


.
11-08-11, 03:47 AM
hero060
=)

11-08-11, 04:36 AM



hot
11-08-11, 07:44 AM
^^^^^^



30%



+


11-08-11, 07:44 AM
http://www.kutub.info/library/book/1564

Tree traverses

mahawy
11-08-11, 04:16 PM




Sweet gilr
11-08-11, 04:46 PM






Sweet gilr
11-08-11, 04:52 PM
^^^^^^



30%










+









fahad777
11-08-11, 05:12 PM
^^^^^^



30%



+




Sweet gilr
11-08-11, 05:19 PM
/ !
...... : ( )

11-08-11, 05:34 PM

akay
11-08-11, 07:54 PM
30% + ...


Sweet gilr
11-08-11, 07:55 PM
What happend ^^^^^^^^

s.r.w
11-08-11, 08:02 PM





:(

11-08-11, 08:11 PM
^
,
=$

s.r.w
11-08-11, 08:36 PM




Sweet gilr
11-08-11, 09:00 PM
.
.

hot
11-08-11, 09:29 PM


LinkedList Single <~

DoubleLinkeddList Ciclue LinkedList

heap
Inorder
Preorder
Postorder

..



infix postfix



..

,,,

..W..
11-08-11, 10:14 PM
!!

^_^

b.g
11-08-11, 10:15 PM


LinkedList Single <~

DoubleLinkeddList Ciclue LinkedList

heap
Inorder
Preorder
Postorder

..



infix postfix



..

,,,

heap site

11-08-11, 10:19 PM
heap

link list
tree :cry(1):

akay
11-08-11, 10:24 PM

Inorder
Preorder
Postorder


Sweet gilr
11-08-11, 10:25 PM






Inorder or preorder or. Postorder



Sweet gilr
11-08-11, 10:26 PM
^^^^^^^^




.

akay
11-08-11, 11:36 PM
Sibling

30

..Identify the siblings of B.

..

My story
11-08-11, 11:39 PM
*** ***

b.g
11-08-11, 11:43 PM
Sibling

30
..Identify the siblings of B.

..


siblings " root"

badr0
11-08-11, 11:44 PM
siblings ,,
nodes with same parent =sibling
f

akay
11-08-11, 11:48 PM
..


Sweet gilr
11-08-11, 11:51 PM


ʿ!









Merge sort is an extremaly fast algoritham

And he write in (Quicksort)
is usually extremely fast in practice.
>>>>>>






11-08-11, 11:55 PM

Postorder , preorder , inorder


:D

akay
11-08-11, 11:58 PM





12-08-11, 12:06 AM
,,
:)

http://dc13.arabsh.com/i/03276/kv6s2mrbknh9.jpg (http://arabsh.com/kv6s2mrbknh9.html)

http://dc13.arabsh.com/i/03276/f1ir69beanse.jpg (http://arabsh.com/f1ir69beanse.html)


:8:

12-08-11, 12:09 AM
,,,
,,

,,,,

12-08-11, 12:21 AM

Changing general tree
To
Binary tree


SIMRAN
12-08-11, 12:29 AM
postfix prefix

12-08-11, 12:58 AM
function

12-08-11, 01:14 AM
postfix prefix

...

http://www.kutub.info/library/book/1564

,,,
Postorder
,,

Preorder
,, ,,

,,,


,,,,

s.r.w
12-08-11, 01:14 AM
:D

:D

s.r.w
12-08-11, 01:15 AM
...

http://www.kutub.info/library/book/1564

,,,
Postorder
,,

Preorder
,, ,,

,,,


,,,,


s.r.w
12-08-11, 01:19 AM
:(



2 7 * 18 -6 +
<< 62 :(

s.r.w
12-08-11, 01:20 AM
postfix prefix

:)

.
12-08-11, 01:26 AM
postfix prefix
41

.
12-08-11, 01:31 AM

"(

s.r.w
12-08-11, 01:42 AM

"(

:(









:(

12-08-11, 02:22 AM
full complete

s.r.w
12-08-11, 02:38 AM

Ex 5.1

Yes
No
J
D,Q
4
3
A,F,L,T A
J
A

:(

..W..
12-08-11, 02:47 AM
full complete


2 23

24 5
27 3

2 3 2 ,,,,


..W..
12-08-11, 03:02 AM
:(



(( 忿
2
3 ~~~ (( ))
4 D
5 j
6 =4 1
7 (()) A 0
8
9
10 SIbling B B




12-08-11, 03:06 AM
:(

..

.
12-08-11, 03:08 AM
^
=$

Sweet gilr
12-08-11, 03:09 AM
^^






<<





<<<




12-08-11, 03:24 AM
w :a2:

badr0
12-08-11, 03:29 AM

(( 忿
2
3 ~~~ (( ))
4 D
5 j
6 =4 1
7 (()) A 0
8
9
10 SIbling B B





10 B B D ^^

NVIDIA
12-08-11, 04:17 AM

Ex 5.1

Yes
No
J
D,Q
4
3
A,F,L,T A
J
A



Is the tree balances? Yes/No




yes

.. 28 :

Complete binary trees are balanced


NVIDIA
12-08-11, 04:33 AM

.. 3 .. .. : ) .. ..
:
-----------------------------------------------------
With respect to big - O notation , order the following rates of growth from fastest rate of growth to slowest rate of growth:
log n , 1000 , n log n , n^3 , 2n , n
:
n^3 , n log n , 2n , n , log n , 1000

-------------------------------------------------------
Draw the binary search tree created by inserting these values in this order:
6 8 2 4 3 0 1 9 5 7
a) Give a pre-order traversal of your tree shown above.
b) Give a post-order traversal of your tree shown above.
------------------------------------------------
What is the maximum number of nodes on a given level of a binary tree?
answer is: 2*2^level
--------------------------------------------
What is the maximum number of nodes in a binary tree of depth D?
tree level 2*2^level
7
--------------------------------------------


Sweet gilr
12-08-11, 04:37 AM
^^^^^
!
blanced

12-08-11, 04:38 AM


:(



.
12-08-11, 05:16 AM
balances :
lift subtree-right subtree
( zero OR 1 OR -1 )
balances

akay
12-08-11, 05:21 AM


2

2

.



..

.
12-08-11, 05:34 AM
ancestor

d j
b dj

;)

s.r.w
12-08-11, 05:48 AM

(( 忿
2
3 ~~~ (( ))
4 D
5 j
6 =4 1
7 (()) A 0
8
9
10 SIbling B B







<3

s.r.w
12-08-11, 05:51 AM



24



:)

NVIDIA
12-08-11, 05:57 AM
Tree




Trees:
1- : Nodes and levels in a Full Binary Tree
2*2^M-1

2- : Some Terminologies
: Height of node Level

---------------------------------------

big O
trees
>>>>




..W..
12-08-11, 06:11 AM
8888




SIMPLE GIRL
12-08-11, 10:12 AM


54 ,10,12.15,9,5




Sweet gilr
12-08-11, 12:04 PM




( )








54



NVIDIA
12-08-11, 04:39 PM

.. .. 6 .. 8 .. 2 ..


.. 3 .. .. : ) .. ..
:
-----------------------------------------------------
With respect to big - O notation , order the following rates of growth from fastest rate of growth to slowest rate of growth:
log n , 1000 , n log n , n^3 , 2n , n
:
n^3 , n log n , 2n , n , log n , 1000

-------------------------------------------------------
Draw the binary search tree created by inserting these values in this order:
6 8 2 4 3 0 1 9 5 7
(( ))
a) Give a pre-order traversal of your tree shown above.
b) Give a post-order traversal of your tree shown above.
------------------------------------------------
What is the maximum number of nodes on a given level of a binary tree?
answer is: 2*2^level
--------------------------------------------
What is the maximum number of nodes in a binary tree of depth D?
tree level 2*2^level
7
--------------------------------------------


akay
12-08-11, 05:02 PM
^^^^^
2 4 ؿ

:(

OuTLoW
12-08-11, 05:30 PM
Nvidia


With respect to big - O notation , order the following rates of growth from fastest rate of growth to slowest rate of growth:
log n , 1000 , n log n , n^3 , 2n , n
:
n^3 , n log n , 2n , n , log n , 1000








2*2^level -

akay
12-08-11, 05:53 PM


..

...

NVIDIA
12-08-11, 06:00 PM
Nvidia


With respect to big - O notation , order the following rates of growth from fastest rate of growth to slowest rate of growth:
log n , 1000 , n log n , n^3 , 2n , n
:
n^3 , n log n , 2n , n , log n , 1000








2*2^level -

-1
:
1-(2*2^ level)


.. ... 1 log n n ...
1000 .. .. 1000 n^3

wwwwwwwwww
12-08-11, 06:27 PM




12-08-11, 08:03 PM


Trees:
1- : Nodes and levels in a Full Binary Tree
2*2^M-1

^^
,

OuTLoW
12-08-11, 08:27 PM
Navidia
full

12-08-11, 08:28 PM
balanced

qazqazzzz
12-08-11, 08:48 PM






%



1

\

OuTLoW
12-08-11, 08:59 PM


12-08-11, 09:23 PM

hero060
12-08-11, 09:38 PM

www.m5zn.com/files-081211110836lz0p8uv0bt7yikdb2-op.rar
http://www.m5zn.com/files-081211110836urj70mjiex2bzbwi66j-finalExam.zip

NVIDIA
12-08-11, 09:55 PM
^^
...

akay
12-08-11, 10:04 PM

.. .. 6 .. 8 .. 2 ..



:(


Sweet gilr
12-08-11, 10:08 PM



Linked List Implementation of Queue




fahad777
12-08-11, 10:12 PM


:(




akay
12-08-11, 10:16 PM
Draw the binary search tree created by inserting these values in this order:
6 8 2 4 3 0 1 9 5 7


fahad777
12-08-11, 10:43 PM
Draw the binary search tree created by inserting these values in this order:
6 8 2 4 3 0 1 9 5 7




12-08-11, 10:43 PM
^^

http://www.m5zn.com/uploads2/2011/8/12/photo/0812111208509vwxqs85r.jpg (http://create-avatar.m5zn.com/)
7

3 4

Pre
7 5 4 3 6 9 8 10
Post
3 4 6 5 810 9 7

OuTLoW
12-08-11, 10:48 PM


------------------------------------------------
What is the maximum number of nodes on a given level of a binary tree?

--------------------------------------------
What is the maximum number of nodes in a binary tree of depth D?

fahad777
12-08-11, 10:49 PM


http://www13.0zz0.com/2011/08/12/19/508972331.jpg

12-08-11, 10:51 PM
^
,

fahad777
12-08-11, 10:53 PM
^
,


fahad777
12-08-11, 11:00 PM

akay
12-08-11, 11:01 PM


http://www13.0zz0.com/2011/08/12/19/508972331.jpg



..


OuTLoW
12-08-11, 11:04 PM

fahad777
12-08-11, 11:04 PM


..







NVIDIA
12-08-11, 11:06 PM




12-08-11, 11:12 PM
NVIDIA
------------------------------------------------
What is the maximum number of nodes on a given level of a binary tree?
answer is: 2*2^level
--------------------------------------------
What is the maximum number of nodes in a binary tree of depth D?
tree level 2*2^level -1
(2*2 )-1
7
--------------------------------------------


fahad777
12-08-11, 11:13 PM


------------------------------------------------
What is the maximum number of nodes on a given level of a binary tree?

--------------------------------------------
What is the maximum number of nodes in a binary tree of depth D?



2 -1 = 15

2 3 -1 = 7

OuTLoW
12-08-11, 11:17 PM

12-08-11, 11:20 PM
^
,
2 -1

12-08-11, 11:21 PM
^^
NVIDIA

15 8


fahad777
12-08-11, 11:22 PM







http://www13.0zz0.com/2011/08/12/19/508972331.jpg

:

: leaf 8 , 6 , 4, 2 , 0

: 9

: 7 8 6



12-08-11, 11:25 PM




2
2*2^2 -1 =7

fahad777
12-08-11, 11:25 PM


full tree

:)

12-08-11, 11:29 PM
1
2 0

NVIDIA
12-08-11, 11:31 PM


fahad777
12-08-11, 11:31 PM
1
2 0

:)

fahad777
12-08-11, 11:34 PM






12-08-11, 11:34 PM
^
,


,
:s

12-08-11, 11:34 PM
>>> " ..
>>
"fahad777">>
>>

fahad777
12-08-11, 11:34 PM
5 5

12-08-11, 11:37 PM
^
2

fahad777
12-08-11, 11:38 PM
>>> " ..
>>
"fahad777">>
>>


12-08-11, 11:38 PM
4

12-08-11, 11:39 PM
6
5

12-08-11, 11:39 PM

fahad777
12-08-11, 11:40 PM
^
2

2 6 5
4


fahad777
12-08-11, 11:42 PM


b-tree

:)

s.r.w
12-08-11, 11:45 PM


Level
􀁺 the number of edges between this node and the
root
􀁺 Level of a node n in a tree T
􀁺 If n is the root of T, it is at level 0
􀁺 If n is not the root of T, its level is 1 greater than the
level of its parent
􀁺 Height of a tree T defined in terms of the levels of its
nodes
􀁺 If T is empty, its height is 0
􀁺 If T is not empty, its height is equal to the maximum
level of its nodes plus 1

12-08-11, 11:45 PM
>>
...

A+

s.r.w
12-08-11, 11:49 PM



13-08-11, 12:01 AM
^
,
,

lolitta
13-08-11, 12:09 AM

..
..




:(

s.r.w
13-08-11, 12:12 AM
:(



:)

Sweet gilr
13-08-11, 12:17 AM

BST
http://up.top4top.net/downloadf-top4top_509b3c156f1-pdf.html

B_TREE
http://up.top4top.net/downloadf-top4top_509b3c156f2-pdf.html

Queue
http://up.top4top.net/downloadf-top4top_509b3c156f3-pdf.html

STACK
http://up.top4top.net/downloadf-top4top_509b3c156f4-pdf.html

LinkedList
http://up.top4top.net/downloadf-top4top_509b3c156f5-pdf.html

Sorting
http://up.top4top.net/downloadf-top4top_509b3c156f6-pdf.html



^^^^^^^^^^^^^^^^^^^








Nodes and Levels in full binary tree ,


lolitta
13-08-11, 12:18 AM
:(



2 7 * 18 -6 +
<< 62 :(








2
7
.. 2 7
2 7 14 ..
18
14 18

14 18

18
18-14
-4
6
-4 6
2

.... :)




:)

hero060
13-08-11, 12:22 AM
2^(+1)-1 ( 2*2^)-1

fahad777
13-08-11, 12:25 AM
>>
...

A+



b-tree

hero060
13-08-11, 12:25 AM
prefix and postfixe and infix

13-08-11, 12:26 AM
full &complete & balance

fahad777
13-08-11, 12:26 AM
2^(+1)-1 ( 2*2^)-1

:)

lolitta
13-08-11, 12:28 AM






hero060
13-08-11, 12:28 AM

fahad777
13-08-11, 12:31 AM
full &complete & balance

full tree


complete


balance

13-08-11, 12:37 AM
prefix and postfixe and infix
4

3. a. Prefix:
D - B + C
((D - B) + C)
(+(-D B) C)
+ - D B C
Postfix:
D - B + C
((D - B) + C)
((D B -) C +)
D B - C +

b. Prefix:
A * B + C * D
((A * B) + (C * D))
(+ (*A B) (* C D))
+ * A B * C D
Postfix:
A * B + C * D
((A * B) + (C * D))
((A B *) (C D *) +)
A B * C D * +
c. Prefix:
(A + B) * C - D * F + C
((((A + B) * C) - (D * F)) + C)
(+ (- (* (+ A B) C) (* D F)) C)
+ - * + A B C * D F C
Postfix:
(A + B) * C - D * F + C
((((A + B) * C) - (D * F)) + C)
((((A B +) C *) (D F *) -) C +)
A B + C * D F * - C +
d. Prefix:
(A - 2 * (B + C) - D * E) * F
(((A - (2 * (B + C))) - (D * E)) * F)
(* (- (- A (* 2 (+ B C))) (* D E)) F)
* - - A * 2 + B C * D E F
Postfix:
(A - 2 * (B + C) - D * E) * F
(((A - (2 * (B + C))) - (D * E)) * F)
(((A (2 (B C +) *) -) (D E *) -) F *)
A 2 B C + * - D E * - F *

Sweet gilr
13-08-11, 12:45 AM
full tree


complete


balance



^^




<



!