Gsp 290 - Data Structures

Data Structures

By Melissa Perez

GSP- 290

3/2/11

In artificial intelligence and computer games data structures are used many times. A data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. There are different types of data structures. They are also used for different situations. Data structures are used in almost every program or software system. Data structures provide a way to manage huge amounts of data efficiently, such as large databases and internet indexing services. Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory. Some of the types of data structures are array, linked list, hash-table, heap, B-tree, red-black tree, trie , stack, and queue. The most popular ones are linked list, stack, tree and graph.

A stack is similar to a linked list except that all insertions and deletions are performed at the same end, called the top of the stack. The insertion operation for a stack is called a push and the deletion operation is called a pop. A queue is similar to a linked list except that insertions and deletions are performed at opposite ends of the queue. An insertion into the queue is called enqueue and a removal from the queue is called dequeue. A graph is a more generic data structure only defined by being a collection of objects connected by a collection of links or edges. Linked lists and trees are special types of graphs.

A tree is a data structure where each object has zero or one parent objects and one or more child objects. If an object in a tree has no parent, it is the beginning of the tree, called the root node. Objects in trees with no children are called leaf nodes.

A sample of a binary tree:

There are many types of data structure trees. Some are rooted binary tree, full binary tree, perfect binary tree, complete binary tree, infinite complete binary tree, and also a balanced binary tree. A rooted binary tree is a tree with a root node in which every node has at most two children. A full binary tree is a tree in which every node other than the leaves has two children. A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

An infinite complete binary tree is a tree with levels, where for each level d the number of existing nodes at level d is equal to 2d. The infinite complete binary tree essentially describes the structure of the Cantor set; the unit interval on the real line is the continuous image of the Cantor set;