# Aaron Gadberry

• ## Subscribe

Was this site helpful?
My Amazon.com Wishlist

# Archive for January, 2006

## Searching: Hash Table

24th January 2006 - By Paradochs

### Information

• Order: O(n)
• Best Case: O(1)
• Average: O(1)

### Description (from wikipedia)

In computer science, a hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person’s name), find the corresponding value (e.g. that person’s telephone number). It works by transforming the key using a hash function into a hash, a number that the hash table uses to locate the desired value.

Hash tables are often used to implement associative arrays, sets and caches. Like arrays, hash tables provide constant-time O(1) lookup on average, regardless of the number of items in the table. However, the rare worst-case lookup time can be as bad as O(n). Compared to other associative array data structures, hash tables are most useful when large numbers of records of data are to be stored.

Hash tables store data in pseudo-random locations, so accessing the data in a sorted manner is a very time consuming operation. Other data structures such as self-balancing binary search trees generally operate more slowly (since their lookup time is O(log n)) and are rather more complex to implement than hash tables but maintain a sorted data structure at all times. See a comparison of hash tables and self-balancing binary search trees.

Posted in Computers, Programming | 1 Comment »

## Searching: Binary Search

24th January 2006 - By Paradochs

### Information

• Order: O(log2(n))
• Best Case: O(1)
• Average: O(log2(n))

### Description (from wikipedia)

A binary search algorithm (or or binary chop) is a computer science technique for finding a particular value in a linear array, by “ruling out” half of the data at each step. A binary search finds the median, makes a comparison to determine whether the desired value comes before or after it, and then searches the remaining half in the same manner. A binary search is an example of a divide and conquer algorithm(more specifically a decrease and conquer algorithm) and a dichotomic search (more at Search algorithm).

Posted in Computers, Programming | 2 Comments »

## Searching: Binary Tree (Unbalanced)

24th January 2006 - By Paradochs

### Information

• Order: O(n)
• Best Case: O(1)
• Average: O(n/2)

### Description (from wikipedia)

In computer science, a binary search tree (BST) is a binary tree where every node has a value, every node’s left subtree contains only values less than or equal to the node’s value, and every node’s right subtree contains only values that are greater than or equal. This requires that the values have a linear order. New nodes are added as leaves. Sort algorithms and search algorithms exist for binary search trees. The values of a binary search tree can be retrieved in ascending order using an in-order traversal.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. We may or may not choose to allow duplicate values in a BST; if we do, it represents a multiset, and inequalities for the left and right subtrees above are non-strict (they have or equal to). If we do not, the inequalities can be taken as strict, and insertion operations must be modified to fail if the value being inserted is already present; in this case the BST represents a set with unique values, like the mathematical set.

Searching a binary tree for a specific value is a recursive process that we can perform due to the ordering it imposes. We begin by examining the root. If the value equals the root, the value exists in the tree. If it is less than the root, then it must be in the left subtree, so we recursively search the left subtree in the same manner. Similarly, if it is greater than the root, then it must be in the right subtree, so we recursively search the right subtree in the same manner. If we reach an external node, then the item is not where it would be if it were present, so it does not lie in the tree at all. A comparison may be made with binary search, which operates in nearly the same way but using random access on an array instead of following links.

Posted in Computers, Programming | 1 Comment »

## Searching: Binary Tree (Balanced)

24th January 2006 - By Paradochs

### Information

• Order: O(n)
• Best Case: O(1)
• Average: O(n/2)

### Description (from wikipedia)

In computer science, a binary search tree (BST) is a binary tree where every node has a value, every node’s left subtree contains only values less than or equal to the node’s value, and every node’s right subtree contains only values that are greater than or equal. This requires that the values have a linear order. New nodes are added as leaves. Sort algorithms and search algorithms exist for binary search trees. The values of a binary search tree can be retrieved in ascending order using an in-order traversal.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. We may or may not choose to allow duplicate values in a BST; if we do, it represents a multiset, and inequalities for the left and right subtrees above are non-strict (they have or equal to). If we do not, the inequalities can be taken as strict, and insertion operations must be modified to fail if the value being inserted is already present; in this case the BST represents a set with unique values, like the mathematical set.

Searching a binary tree for a specific value is a recursive process that we can perform due to the ordering it imposes. We begin by examining the root. If the value equals the root, the value exists in the tree. If it is less than the root, then it must be in the left subtree, so we recursively search the left subtree in the same manner. Similarly, if it is greater than the root, then it must be in the right subtree, so we recursively search the right subtree in the same manner. If we reach an external node, then the item is not where it would be if it were present, so it does not lie in the tree at all. A comparison may be made with binary search, which operates in nearly the same way but using random access on an array instead of following links.

Posted in Computers, Programming | 1 Comment »

## Searching: Driver Program for Searches

24th January 2006 - By Paradochs

### Description

This code implements and runs the search algorithm code in other articles.

Posted in Computers, Programming | No Comments »