Using python Write Short notes describing the following data

Using python: Write Short notes describing the following data structures, your notes shoud include their definitions , most of their use in real world’s applications,main operations and their pseudocodes. (from 3-5 pages per each Data Structure)

a. Stacks

b. Queues

c. AVL Trees

d. B Trees

e. Graphs

Solution

a. Stacks: Stack is a data structure which is applicable for the individual program which represents the real meaning of the stack. Stack can store the value in fix length that is if one memory is allocated that is considered to be as final. Stack gets cleared only in the end of the programs execution and it is monitered by the operating system. It access the data like Last In First(LIFO) method that means we can take out the stack in order. There are basically three operations that will perform by this. 1) push 2) pop 3) pip.

In the code we include this to use them

top():item-type

is-empty():Boolean

is-full():Boolean

b) Queues: It is another data structure which is used through out the programming. It implements same as in the form of queue that means one after another. It is mainly useful for the urgent requirement because it can take out the information quickly because it was stored in the queuee. It is First in First(FIFO).

some operation which are used with the help of queues are

enqueue(new-item:item-type)

front():item-type

dequeue()

is-empty():Boolean

c. AVL trees: AVL tree is a binary search tree which is a data structure. The operation of the AVL tree is read only operation and it is mainly based on the binary search tree which it searches according to the binary that is stored and it is named. It is different from the other data structures in their height. It is mainly used in the applications where we use mostly insertion and deletion of the data. These are used in the applications where we use complexity of the program.

code which is used AVL tree is

adjustHeight ( root : Node ) is

if root null then

root . height 1 + max ( height ( root . left )

, height ( root . right ) )

end

end

d. B trees: The generalization of binary search tree was described as B Tree.Generally the binary tree has 2 node B Tree.Whereas the classical B Tree has N internal nodes and 2 nodes are empty as leaf nodes.The B Tree are most commonly used in the database because only values are stored in the leaf node whereas internal nodes only stores keys and pointer to other nodes.A B Tree has bigger internal nodes so it is wider.Mostly the B tree are used for the large data bases.

Code which is used B Tree is:

B-Tree-Split-Child (x, i, y)

z = allocate-node ()

leaf[z] = leaf[y]

n[z] = t - 1

for j in 1..t-1 do

keyj[z] = keyj+t[y]

end for

if not leaf[y] then

for j in 1..t do

cj[z] = cj+t[y]

end for

end if

n[y] = t - 1

for j in n[x]+1 downto i+1 do

cj+1[x] = cj[x]

end for

ci+1 = z

for j in n[x] downto i do

keyj+1[x] = keyj[x]

end for

keyi[x] = keyt[y]

n[x]++

Disk-Write (y)

Disk-Write (z)

Disk-Write (x)

E.Graphs: A graph is also called as dimensions which consists of set of arrays and a set of edges. Generally there are two types of graphs Directed graph and un-directed graph The directed graph is a one way connection whereas the un-directed graph is two way connection.When we are adding any information to the graph it is called as weighed graph. In this weighed graph also consists of both directed and un-directed graphs.

Code which is used by Graphs:

GraphNode depth_first_search(GraphNode node, Predicate criteria, VisitedSet visited) {

if (visited.contains(node)) {

return null;

}

visited.insert(node);

if (criteria.apply(node.value)) {

return node;

}

for (adjacent in node.adjacentnodes()) {

GraphNode ret = depth_first_search(adjacent, criteria, visited);

if (ret != null) {

return ret;

}

}

return null;

}