text:
Data Structures/List Structures

List Structures and Iterators
We have now seen two different data structures that allow us to store an ordered sequence of elements. However, they have two very different interfaces. The array allows us to use  and   functions to access and change elements. The node chain requires us to use  until we find the desired node, and then we can use   and   to access and modify its value. Now, what if you've written some code, and you realize that you should have been using the other sequence data structure? You have to go through all of the code you've already written and change one set of accessor functions into another. What a pain! Fortunately, there is a way to localize this change into only one place: by using the List Abstract Data Type (ADT).

  ADT    Returns the list iterator (we'll define this soon) that represents the first element of the list. Runs in $$O(1)$$ time.   Returns the list iterator that represents one element past the last element in the list. Runs in $$O(1)$$ time.   Adds a new element at the beginning of a list. Runs in $$O(1)$$ time.
Adds a new element immediately after iter. Runs in $$O(N)$$ time.

Removes the element at the beginning of a list. Runs in $$O(1)$$ time.

Removes the element immediately after iter. Runs in $$O(N)$$ time.

True if there are no elements in the list. Has a default implementation. Runs in $$O(1)$$ time.

Returns the number of elements in the list. Has a default implementation. Runs in $$O(N)$$ time.

Returns the nth element in the list, counting from 0. Has a default implementation. Runs in $$O(N)$$ time.

Assigns a new value to the nth element in the list, counting from 0. Has a default implementation. Runs in $$O(N)$$ time.

The iterator is another abstraction that encapsulates both access to a single element and incremental movement around the list. Its interface is very similar to the node interface presented in the introduction, but since it is an abstract type, different lists can implement it differently.
  ADT

Returns the value of the list element that this iterator refers to.

Assigns a new value to the list element that this iterator refers to.

Makes this iterator refer to the next element in the list.

True if the other iterator refers to the same list element as this iterator.

 All operations run in $$O(1)$$ time.

There are several other aspects of the List ADT's definition that need more explanation. First, notice that the  operation returns an iterator that is "one past the end" of the list. This makes its implementation a little trickier, but allows you to write loops like: var iter:List Iterator := list.get-begin while(not iter.equal(list.get-end)) # Do stuff with the iterator iter.move-next end while

Second, each operation gives a worst-case running time. Any implementation of the List ADT is guaranteed to be able to run this operation at least that fast. Most implementations will run most of the operations faster. For example, the node chain implementation of List can run  in $$O(1)$$.

Third, some of the operations say that they have a default implementation. This means that these operations can be implemented in terms of other, more primitive operations. They're included in the ADT so that certain implementations can implement them faster. For example, the default implementation of  runs in $$O(N)$$ because it has to traverse all of the elements before the nth. Yet the array implementation of List can implement it in $$O(1)$$ using its  operation. The other default implementations are: abstract type List<item-type> method is-empty return get-begin.equal(get-end) end method method get-size:Integer var size:Integer := 0 var iter:List Iterator<item-type> := get-begin while(not iter.equal(get-end)) size := size+1 iter.move-next end while return size end method helper method find-nth(n:Integer):List Iterator<item-type> if n >= get-size error "The index is past the end of the list" end if  var iter:List Iterator<item-type> := get-begin while(n > 0) iter.move-next n := n-1 end while return iter end method method get-nth(n:Integer):item-type return find-nth(n).get-value end method method set-nth(n:Integer, new-value:item-type) find-nth(n).set-value(new-value) end method end type

Syntactic Sugar
Occasionally throughout this book we'll introduce an abbreviation that will allow us to write, and you to read, less pseudocode. For now, we'll introduce an easier way to compare iterators and a specialized loop for traversing sequences.

Instead of using the  method to compare iterators, we'll overload the   operator. To be precise, the following two expressions are equivalent: iter1 .equal( iter2 ) iter1 == iter2

Second, we'll use the  keyword to express list traversal. The following two blocks are equivalent: var iter :List Iterator< item-type > := list .get-begin while(not iter == list .get-end) operations on iter iter .move-next end while

for iter in list operations on iter end for

Implementations
In order to actually use the List ADT, we need to write a concrete data type that implements its interface. There are two standard data types that naturally implement List: the node chain described in the Introduction, normally called a Singly Linked List; and an extension of the array type called a Vector, which automatically resizes itself to accommodate inserted nodes.

Singly Linked List
type Singly Linked List<item-type> implements List<item-type> head refers to the first node in the list. When it's null, the list is empty. data head:Node<item-type>

Initially, the list is empty. constructor head := null end constructor method get-begin:Sll Iterator<item-type> return new Sll-Iterator(head) end method The "one past the end" iterator is just a null node. To see why, think about what you get when you have an iterator for the last element in the list and you call. method get-end:Sll Iterator<item-type> return new Sll-Iterator(null) end method method prepend(new-item:item-type) head = make-node(new-item, head) end method method insert-after(iter:Sll Iterator<item-type>, new-item:item-type) var new-node:Node<item-type> := make-node(new-item, iter.node.get-next) iter.node.set-next(new-node) end method method remove-first head = head.get-next end method This takes the node the iterator holds and makes it point to the node two nodes later. method remove-after(iter:Sll Iterator<item-type>) iter.node.set-next(iter.node.get-next.get-next) end method end type If we want to make  be an $$O(1)$$ operation, we can add an Integer data member that keeps track of the list's size at all times. Otherwise, the default $$O(N)$$ implementation works fine.

An iterator for a singly linked list simply consists of a reference to a node. type Sll Iterator<item-type> data node:Node<item-type> constructor(_node:Node<item-type>) node := _node end constructor

Most of the operations just pass through to the node. method get-value:item-type return node.get-value end method method set-value(new-value:item-type) node.set-value(new-value) end method method move-next node := node.get-next end method

For equality testing, we assume that the underlying system knows how to compare nodes for equality. In nearly all languages, this would be a pointer comparison. method equal(other-iter:List Iterator<item-type>):Boolean return node == other-iter.node end method end type

Vector
Let's write the Vector's iterator first. It will make the Vector's implementation clearer. type Vector Iterator<item-type> data array:Array<item-type> data index:Integer constructor(my_array:Array<item-type>, my_index:Integer) array := my_array index := my_index end constructor method get-value:item-type return array.get-element(index) end method method set-value(new-value:item-type) array.set-element(index, new-value) end method method move-next index := index+1 end method method equal(other-iter:List Iterator<item-type>):Boolean return array==other-iter.array and index==other-iter.index end method end type

We implement the Vector in terms of the primitive Array data type. It is inefficient to always keep the array exactly the right size (think of how much resizing you'd have to do), so we store both a, the number of logical elements in the Vector, and a  , the number of spaces in the array. The array's valid indices will always range from  to. type Vector<item-type> data array:Array<item-type> data size:Integer data capacity:Integer

We initialize the vector with a capacity of 10. Choosing 10 was fairly arbitrary. If we'd wanted to make it appear less arbitrary, we would have chosen a power of 2, and innocent readers like you would assume that there was some deep, binary-related reason for the choice. constructor array := create-array(0, 9) size := 0 capacity := 10 end constructor method get-begin:Vector-Iterator<item-type> return new Vector-Iterator(array, 0) end method

The end iterator has an index of. That's one more than the highest valid index. method get-end:List Iterator<item-type> return new Vector-Iterator(array, size) end method

We'll use this method to help us implement the insertion routines. After it is called, the  of the array is guaranteed to be at least. A naive implementation would simply allocate a new array with exactly  elements and copy the old array over. To see why this is inefficient, think what would happen if we started appending elements in a loop. Once we exceeded the original capacity, each new element would require us to copy the entire array. That's why this implementation at least doubles the size of the underlying array any time it needs to grow. helper method ensure-capacity(new-capacity:Integer) If the current capacity is already big enough, return quickly. if capacity >= new-capacity return end if Now, find the new capacity we'll need, var allocated-capacity:Integer := max(capacity*2, new-capacity) var new-array:Array<item-type> := create-array(0, allocated-capacity - 1) copy over the old array, for i in 0..size-1 new-array.set-element(i, array.get-element(i)) end for and update the Vector's state. array := new-array capacity := allocated-capacity end method

This method uses a normally-illegal iterator, which refers to the item one before the start of the Vector, to trick  into doing the right thing. By doing this, we avoid duplicating code. method prepend(new-item:item-type) insert-after(new Vector-Iterator(array, -1), new-item) end method

needs to copy all of the elements between iter and the end of the Vector. This means that in general, it runs in $$O(N)$$ time. However, in the special case where iter refers to the last element in the vector, we don't need to copy any elements to make room for the new one. An append operation can run in $$O(1)$$ time, plus the time needed for the  call. will sometimes need to copy the whole array, which takes $$O(N)$$ time. But much more often, it doesn't need to do anything at all.

 Amortized Analysis

In fact, if you think of a series of append operations starting immediately after  increases the Vector's capacity (call the capacity here $$C$$), and ending immediately after the next increase in capacity, you can see that there will be exactly $$\frac{C}{2}=O(C)$$ appends. At the later increase in capacity, it will need to copy $$C$$ elements over to the new array. So this entire sequence of $$\frac{C}{2}$$ function calls took $$\frac{3C}{2}=O(C)$$ operations. We call this situation, where there are $$O(N)$$ operations for $$O(N)$$ function calls "amortized $$O(1)$$ time". method insert-after(iter:Vector Iterator<item-type>, new-item:item-type) ensure-capacity(size+1) This loop copies all of the elements in the vector into the spot one index up. We loop backwards in order to make room for each successive element just before we copy it. for i in size-1 .. iter.index+1 step -1 array.set-element(i+1, array.get-element(i)) end for Now that there is an empty space in the middle of the array, we can put the new element there. array.set-element(iter.index+1, new-item) And update the Vector's size. size := size+1 end method Again, cheats a little bit to avoid duplicate code. method remove-first remove-after(new Vector-Iterator(array, -1)) end method Like,   needs to copy all of the elements between iter and the end of the Vector. So in general, it runs in $$O(N)$$ time. But in the special case where iter refers to the last element in the vector, we can simply decrement the Vector's size, without copying any elements. A remove-last operation runs in $$O(1)$$ time. method remove-after(iter:List Iterator<item-type>) for i in iter.index+1 .. size-2 array.set-element(i, array.get-element(i+1)) end for size := size-1 end method This method has a default implementation, but we're already storing the size, so we can implement it in $$O(1)$$ time, rather than the default's $$O(N).$$ method get-size:Integer return size end method

Because an array allows constant-time access to elements, we can implement  and   in $$O(1)$$, rather than the default implementation's $$O(N)$$ method get-nth(n:Integer):item-type return array.get-element(n) end method method set-nth(n:Integer, new-value:item-type) array.set-element(n, new-value) end method end type

Bidirectional Lists
Sometimes we want to move backward in a list too. A Bidirectional List allows the list to be searched forwards and backwards. A Bidirectional list implements an additional iterator function,

  ADT

Returns the list iterator (we'll define this soon) that represents the first element of the list. Runs in $$O(1)$$ time.

Returns the list iterator that represents one element past the last element in the list. Runs in $$O(1)$$ time.

Adds a new element immediately before iter. Runs in $$O(N)$$ time.

Removes the element immediately referred to by iter. After this call, iter will refer to the next element in the list. Runs in $$O(N)$$ time.

True iff there are no elements in the list. Has a default implementation. Runs in $$O(1)$$ time.

Returns the number of elements in the list. Has a default implementation. Runs in $$O(N)$$ time.

Returns the nth element in the list, counting from 0. Has a default implementation. Runs in $$O(N)$$ time.

Assigns a new value to the nth element in the list, counting from 0. Has a default implementation. Runs in $$O(N)$$ time.

  ADT

Returns the value of the list element that this iterator refers to. Undefined if the iterator is past-the-end.

Assigns a new value to the list element that this iterator refers to. Undefined if the iterator is past-the-end.

Makes this iterator refer to the next element in the list. Undefined if the iterator is past-the-end.

Makes this iterator refer to the previous element in the list. Undefined if the iterator refers to the first list element.

True iff the other iterator refers to the same list element as this iterator.

 All operations run in $$O(1)$$ time.

Vector Implementation
The vector we've already seen has a perfectly adequate implementation to be a Bidirectional List. All we need to do is add the extra member functions to it and its iterator; the old ones don't have to change.

type Vector<item-type> ... # already-existing data and methods

Implement this in terms of the original  method. After that runs, we have to adjust iter 's index so that it still refers to the same element. method insert(iter:Bidirectional List Iterator<item-type>, new-item :item-type) insert-after(new Vector-Iterator(iter.array, iter.index-1)) iter.move-next end method

Also implement this on in terms of an old function. After  runs, the index will already be correct. method remove(iter:Bidirectional List Iterator<item-type>) remove-after(new Vector-Iterator(iter.array, iter.index-1)) end method end type

Tradeoffs
In order to choose the correct data structure for the job, we need to have some idea of what we're going to *do* with the data.

 * Do we know that we'll never have more than 100 pieces of data at any one time, or do we need to occasionally handle gigabytes of data ?
 * How will we read the data out ? Always in chronological order ? Always sorted by name ? Randomly accessed by record number ?
 * Will we always add/delete data to the end or to the beginning ? Or will we be doing a lot of insertions and deletions in the middle ?

We must strike a balance between the various requirements. If we need to frequently read data out in 3 different ways, pick a data structure that allows us to do all 3 things not-too-slowly. Don't pick some data structure that's unbearably slow for *one* way, no matter how blazingly fast it is for the other ways.

Often the shortest, simplest programming solution for some task will use a linear (1D) array.

If we keep our data as an ADT, that makes it easier to temporarily switch to some other underlying data structure, and objectively measure whether it's faster or slower.

Advantages / Disadvantages
For the most part, an advantage of an array is a disadvantage of a linked list, and vice versa.

 * Array Advantages (vs. Linked Lists)
 * 1) Index - Indexed access to any element in an array is fast; a linked list must be traversed from the beginning to reach the desired element.
 * 2) Faster - In general, accessing an element in an array is faster than accessing an element in a linked list.
 * Linked-List Advantages (vs. Arrays)
 * 1) Resize - A linked list can easily be resized by adding elements without affecting the other elements in the list; an array can be enlarged only by allocating new chunk of memory and copying all the elements.
 * 2) Insertion - An element can easily be inserted into the middle of a linked list: a new link is created with a pointer to the link after it, and the previous link is made to point to the new link.

Side-note: - How to insert an element in the middle of an array. If an array is not full, you take all the elements after the spot or index in the array you want to insert, and move them forward by 1, then insert your element. If the array is already full and you want to insert an element, you would have to, in a sense, 'resize the array.' A new array would have to be made one size larger than the original array to insert your element, then all the elements of the original array are copied to the new array taking into consideration the spot or index to insert your element, then insert your element.

title: Data Structures/List Structures


text:
Data Structures/Trees

Trees
A tree is a non-empty set with an element that is designated as the root of the tree while the remaining elements are partitioned into non-empty sets each of which is a subtree of the root.

Tree nodes have many useful properties. The depth of a node is the length of the path (or the number of edges) from the root to that node. The height of a node is the longest path from that node to its leaves. The height of a tree is the height of the root. A leaf node has no children—its only path is up to its parent.

See the axiomatic development of trees and its consequences for more information.

Types of trees:

Binary: Each node has zero, one, or two children. This assertion makes many tree operations simple and efficient.

Binary Search: A binary tree where any left child node has a value less than its parent node and any right child node has a value greater than or equal to that of its parent node.

Traversal
Many problems require we visit the nodes of a tree in a systematic way: tasks such as counting how many nodes exist or finding the maximum element. Three different methods are possible for binary trees: preorder, postorder, and in-order, which all do the same three things: recursively traverse both the left and right subtrees and visit the current node. The difference is when the algorithm visits the current node:

preorder: Current node, left subtree, right subtree (DLR)

postorder: Left subtree, right subtree, current node (LRD)

in-order: Left subtree, current node, right subtree (LDR)

levelorder: Level by level, from left to right, starting from the root node.

 * Visit means performing some operation involving the current node of a tree, like incrementing a counter or checking if the value of the current node is greater than any other recorded.

Sample implementations for Tree Traversal
preorder(node) visit(node) if node.left ≠ null then preorder(node.left) if node.right ≠ null then preorder(node.right)

inorder(node) if node.left ≠ null then inorder(node.left) visit(node) if node.right ≠ null then inorder(node.right)

postorder(node) if node.left ≠ null then postorder(node.left) if node.right ≠ null then postorder(node.right) visit(node)

levelorder(root) queue q q.push(root) while not q.empty do node = q.pop visit(node) if node.left ≠ null then q.push(node.left) if node.right ≠ null then q.push(node.right)

For an algorithm that is less taxing on the stack, see Threaded Trees.

Examples of Tree Traversals

preorder: 50,30, 20, 40, 90, 100 inorder: 20,30,40,50, 90, 100 postorder: 20,40,30,100,90,50

Balancing
When entries that are already sorted are stored in a tree, all new records will go the same route, and the tree will look more like a list (such a tree is called a degenerate tree). Therefore the tree needs balancing routines, making sure that under all branches are an equal number of records. This will keep searching in the tree at optimal speed. Specifically, if a tree with n nodes is a degenerate tree, the longest path through the tree will be n nodes; if it is a balanced tree, the longest path will be log n nodes.

Algorithms/Left rotation: This shows how balancing is applied to establish a priority heap invariant in a Treap, a data structure which has the queueing performance of a heap, and the key lookup performance of a tree. A balancing operation can change the tree structure while maintaining another order, which is binary tree sort order. The binary tree order is left to right, with left nodes' keys less than right nodes' keys, whereas the priority order is up and down, with higher nodes' priorities greater than lower nodes' priorities. Alternatively, the priority can be viewed as another ordering key, except that finding a specific key is more involved.

The balancing operation can move nodes up and down a tree without affecting the left right ordering.

AVL: A balanced binary search tree according to the following specification: the heights of the two child subtrees of any node differ by at most one.

Red-Black Tree: A balanced binary search tree using a balancing algorithm based on colors assigned to a node, and the colors of nearby nodes.

 AA Tree: A balanced tree, in fact a more restrictive variation of a red-black tree.

Binary Search Trees
A typical binary search tree looks like this:

Terms
Node Any item that is stored in the tree. Root The top item in the tree. (50 in the tree above) Child Node(s) under the current node. (20 and 40 are children of 30 in the tree above) Parent The node directly above the current node. (90 is the parent of 100 in the tree above) Leaf A node which has no children. (20 is a leaf in the tree above)

Searching through a binary search tree
To search for an item in a binary tree:

 * 1) Start at the root node
 * 2) If the item that you are searching for is less than the root node, move to the left child of the root node, if the item that you are searching for is more than the root node, move to the right child of the root node and if it is equal to the root node, then you have found the item that you are looking for.
 * 3) Now check to see if the item that you are searching for is equal to, less than or more than the new node that you are on. Again if the item that you are searching for is less than the current node, move to the left child, and if the item that you are searching for is greater than the current node, move to the right child.
 * 4) Repeat this process until you find the item that you are looking for or until the node does not have a child on the correct branch, in which case the tree doesn't contain the item which you are looking for.

Example

For example, to find the node 40...

.........
 * 1) The root node is 50, which is greater than 40, so you go to 50's left child.
 * 2) 50's left child is 30, which is less than 40, so you next go to 30's right child.
 * 3) 30's right child is 40, so you have found the item that you are looking for :)

Adding an item to a binary search tree

 * 1) To add an item, you first must search through the tree to find the position that you should put it in. You do this following the steps above.
 * 2) When you reach a node which doesn't contain a child on the correct branch, add the new node there.

For example, to add the node 25...

 * 1) The root node is 50, which is greater than 25, so you go to 50's left child.
 * 2) 50's left child is 30, which is greater than 25, so you go to 30's left child.
 * 3) 30's left child is 20, which is less than 25, so you go to 20's right child.
 * 4) 20's right child doesn't exist, so you add 25 there :)

Deleting an item from a binary search tree
It is assumed that you have already found the node that you want to delete, using the search technique described above.

Case 1: The node you want to delete is a leaf

For example, to delete 40...

 * Simply delete the node!

Case 2: The node you want to delete has one child

 * 1) Directly connect the child of the node that you want to delete, to the parent of the node that you want to delete.

For example, to delete 90...

 * Delete 90, then make 100 the child node of 50.

Case 3: The node you want to delete has two children
One non-standard way, is to rotate the node into a chosen subtree, and attempt to delete the key again from that subtree, recursively, until Case 1 or Case 2 occurs. This could unbalance a tree, so randomly choosing whether to right or left rotate may help.

The standard way is to pick either the left or right child, say the right, then get the right's leftmost descendent by following left ,starting from the right child, until the next left is null. Then remove this leftmost descendant of the right child, replacing it with its right sub-tree ( it has a left child of null). Then use the contents of this former leftmost descendant of the right child, as replacement for the key and value of the node being deleted, so that its values now are in the deleted node, the parent of the right child. This still maintains the key ordering for all nodes. Example java code is below in the treap example code.

The following examples use the standard algorithm, that is, the successor is the left-most node in the right subtree of the node to be deleted.

For example, to delete 30

 * 1) The right node of the node which is being deleted is 40.
 * 2) (From now on, we continually go to the left node until there isn't another one...) The first left node of 40, is 35.
 * 3) 35 has no left node, therefore 35 is the successor!
 * 4) 35 replaces 30, at the original right node, and the node with 35 is deleted, replacing it with the right sub-tree, which has the root node 37.

Case 1 of two-children case: The successor is the right child of the node being deleted

 * 1) Directly move the child to the right of the node being deleted into the position of the node being deleted.
 * 2) As the new node has no left children, you can connect the deleted node's left subtree's root as it's left child.

For example, to delete 30

 * 1) replace the contents to be deleted (30), with the successor's contents( 40).
 * 2) delete the successor node (contents 40), replacing it with its right subtree (head contents 45).

Case 2 of two-children case: The successor isn't the right child of the node being deleted
This is best shown with an example

To delete 30...

 * 1) Replace the contents to be deleted (30) with the successor's contents (35).
 * 2) replace the successor (35) with it's right subtree (37). There is no left subtree because the successor is leftmost.

Red-Black trees
A red-black tree is a self-balancing tree structure that applies a color to each of its nodes. The structure of a red-black tree must adhere to a set of rules which dictate how nodes of a certain color can be arranged. The application of these rules is performed when the tree is modified in some way, causing the rotation and recolouring of certain nodes when a new node is inserted or an old node is deleted. This keeps the red-black tree balanced, guaranteeing a search complexity of O(log n).

The rules that a red-black tree must adhere to are as follows:

 * 1) Each node must be either red or black.
 * 2) The root is always black.
 * 3) All leaves within the tree are black (leaves do not contain data and can be modelled as null or nil references in most programming languages).
 * 4) Every red node must have two black child nodes.
 * 5) Every path from a given node to any of its descendant leaves must contain the same number of black nodes.

A red-black tree can be modelled as 2-3-4 tree, which is a sub-class of B tree (below). A black node with one red node can be seen as linked together as a 3-node, and a black node with 2 red child nodes can be seen as a 4-node.

4-nodes are split, producing a two node, and the middle node made red, which turns a parent of the middle node which has no red child from a 2-node to a 3-node, and turns a parent with one red child into a 4-node (but this doesn't occur with always left red nodes).

A in-line arrangement of two red nodes, is rotated into a parent with two red children, a 4-node, which is later split, as described before.

A right rotate     'split 4-node'  | red red / \ -->    B      --->  B   B        red / \ red        / \ red / \       C  A        C  A  C  D         /          / D         D

An optimization mentioned by Sedgewick is that all right inserted red nodes are left rotated to become left red nodes, so that only inline left red nodes ever have to be rotated right before splitting. AA-trees (above) by Arne Anderson, described in a paper in 1993 , seem an earlier exposition of the simplification, however he suggested right-leaning 'red marking' instead of left leaning , as suggested by Sedgewick, but AA trees seem to have precedence over left leaning red black trees. It would be quite a shock if the Linux CFS scheduler was described in the future as 'AA based'.

In summary, red-black trees are a way of detecting two insertions into the same side, and levelling out the tree before things get worse. Two left sided insertions will be rotated, and the two right sided insertions, would look like two left sided insertions after left rotation to remove right leaning red nodes. Two balanced insertions for the same parent could result in a 4-node split without rotation, so the question arises as to whether a red black tree could be attacked with serial insertions of one sided triads of a < P < b, and then the next triad's P' < a.

Python illustrative code follows

Summary

 * Whereas binary trees have nodes that have two children, with the left child and all of its descendants less than the "value" of the node, and the right child and all of its children more than the "value" of the node, a B-tree is a generalization of this.
 * The generalization is that instead of one value, the node has a list of values, and the list is of size n ( n > 2 ). n is chosen to optimize storage, so that a node corresponds in size to a block for instance. This is in the days before ssd drives, but searching binary nodes stored on ssd ram would still be slower than searching ssd ram for a block of values, loading into normal ram and cpu cache, and searching the loaded list.
 * At the start of the list, the left child of the first element of the list has a value less than the first element, and so do all its children. To the right of the first element, is a child which has values more than the first element's value, as do all of its children, but also less than the value of the second element. Induction can be used , and this holds so for the child between element 1 and 2, 2 and 3, ... so on until n-1 and nth node.
 * To insert into a non-full B tree node, is to do a insertion into a sorted list.
 * In a B+ tree, insertions can only be done in leaf nodes, and non-leaf nodes hold copies of a demarcating value between adjacent child nodes e.g. the left most value of an element's right child's list of nodes.
 * Whenever a list becomes full e.g. there are n nodes, the node is "split", and this means making two new nodes, and passing the demarcating value upto the parent.

B Trees were described originally as generalizations of binary search trees, where a binary tree is a 2-node B-Tree, the 2 standing for two children, with 2-1 = 1 key separating the 2 children. Hence a 3-node has 2 values separating 3 children, and a N node has N children separated by N-1 keys.

A classical B-Tree can have N-node internal nodes, and empty 2-nodes as leaf nodes, or more conveniently, the children can either be a value or a pointer to the next N-node, so it is a union.

The main idea with B-trees is that one starts with a root N-node, which is able to hold N-1 entries, but on the Nth entry, the number of keys for the node is exhausted, and the node can be split into two half sized N/2 sized N nodes, separated by a single key K, which is equal to the right node's leftmost key, so any entry with key K2 equal or greater than K goes in the right node, and anything less than K goes in the left. When the root node is split, a new root node is created with one key, and a left child and a right child. Since there are N children but only N-1 entries, the leftmost child is stored as a separate pointer. If the leftmost pointer splits, then the left half becomes the new leftmost pointer, and the right half and separating key is inserted into the front of the entries.

An alternative is the B+ tree which is the most commonly used in database systems, because only values are stored in leaf nodes, whereas internal nodes only store keys and pointers to other nodes, putting a limit on the size of the datum value as the size of a pointer. This often allows internal nodes with more entries able to fit a certain block size, e.g. 4K is a common physical disc block size. Hence, if a B+ tree internal node is aligned to a physical disc block, then the main rate limiting factor of reading a block of a large index from disc because it isn't cached in a memory list of blocks is reduced to one block read.

A B+ tree has bigger internal nodes, so is wider and shorter in theory than an equivalent B tree which must fit all nodes within a given physical block size, hence overall it is a faster index due to greater fan out and less height to reach keys on average.

Apparently, this fan out is so important, compression can also be applied to the blocks to increase the number of entries fitting within a given underlying layer's block size (the underlying layer is often a filesystem block).

Most database systems use the B+ tree algorithm, including postgresql, mysql, derbydb, firebird, many Xbase index types, etc.

Many filesystems also use a B+ tree to manage their block layout (e.g. xfs, NTFS, etc).

Transwiki has a java implementation of a B+ Tree which uses traditional arrays as key list and value list.

Below is an example of a B Tree with test driver, and a B+ tree with a test driver. The memory / disc management is not included, but a usable hacked example can be found at /Hashing Memory Checking Example/.

This B+ tree implementation was written out of the B Tree, and the difference from the transwiki B+ tree is that it tries to use the semantics of SortedMap and SortedSet already present in the standard Java collections library.

Hence, the flat leaf block list of this B+ implementation can't contain blocks that don't contain any data, because the ordering depends on the first key of the entries, so a leaf block needs to be created with its first entry.

A B+ tree java example
Experiments include timing the run ( e.g. time java -cp . btreemap.BPlusTreeTest1 ), using an external blocksize + 1 sized leaf block size, so that this is basically the underlying entries TreeMap only, vs , say, 400 internal node size, and 200 external node size. Other experiments include using a SkipListMap instead of a TreeMap.

Treaps
The invariant in a binary tree is that left is less than right with respect to insertion keys. e.g. for a key with order, ord(L) < ord(R). This doesn't dictate the relationship of nodes however, and left and right rotation does not affect the above. Therefore another order can be imposed. If the order is randomised, it is likely to counteract any skewness of a plain binary tree e.g. when inserting an already sorted input in order.

Below is a java example implementation, including a plain binary tree delete code example.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Data Structures/Trees


text:
Data Structures/Hash Tables

Hash Tables
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. This hash maps directly to a bucket in the array of key/value pairs, hence the name hash map. The mapping method lets us directly access the storage location for any key/value pair.

Time complexity and common uses of hash tables
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. The (hopefully rare) worst-case lookup time in most hash table schemes is O(n). Compared to other associative array data structures, hash tables are most useful when we need to store a large numbers of data records.

Hash tables may be used as in-memory data structures. Hash tables may also be adopted for use with persistent data structures; database indexes commonly use disk-based data structures based on hash tables.

Hash tables are also used to speed-up string searching in many implementations of data compression.

In computer chess, a hash table can be used to implement the transposition table.

Choosing a good hash function
A good hash function is essential for good hash table performance. A poor choice of hash function is likely to lead to clustering behavior, in which the probability of keys mapping to the same hash bucket (i.e. a collision) is significantly greater than would be expected from a random function. A nonzero probability of collisions is inevitable in any hash implementation, but the number of operations to resolve collisions usually scales linearly with the number of keys mapping to the same bucket, so excess collisions will degrade performance significantly. In addition, some hash functions are computationally expensive, so the amount of time (and, in some cases, memory) taken to compute the hash may be burdensome.

Choosing a good hash function is tricky. The literature is replete with poor choices, at least when measured by modern standards. For example, the very popular multiplicative hash advocated by Knuth in The Art of Computer Programming (see reference below) has particularly poor clustering behavior. However, since poor hashing merely degrades hash table performance for particular input key distributions, such problems go undetected far too often.

The literature is also sparse on the criteria for choosing a hash function. Unlike most other fundamental algorithms and data structures, there is no universal consensus on what makes a "good" hash function. The remainder of this section is organized by three criteria: simplicity, speed, and strength, and will survey algorithms known to perform well by these criteria.

Simplicity and speed are readily measured objectively (by number of lines of code and CPU benchmarks, for example), but strength is a more slippery concept. Obviously, a cryptographic hash function such as SHA-1 would satisfy the relatively lax strength requirements needed for hash tables, but their slowness and complexity makes them unappealing. In fact, even a cryptographic hash does not provide protection against an adversary who wishes to degrade hash table performance by choosing keys all hashing to the same bucket. For these specialized cases, a universal hash function should be used instead of any one static hash, no matter how sophisticated.

In the absence of a standard measure for hash function strength, the current state of the art is to employ a battery of statistical tests to measure whether the hash function can be readily distinguished from a random function. Arguably the most important such test is to determine whether the hash function displays the avalanche effect, which essentially states that any single-bit change in the input key should affect on average half the bits in the output. Bret Mulvey advocates testing the strict avalanche condition in particular, which states that, for any single-bit change, each of the output bits should change with probability one-half, independent of the other bits in the key. Purely additive hash functions such as CRC fail this stronger condition miserably.

Clearly, a strong hash function should have a uniform distribution of hash values. Bret Mulvey proposes the use of a chi-squared test for uniformity, based on power of two hash table sizes ranging from 21 to 216. This test is considerably more sensitive than many others proposed for measuring hash functions, and finds problems in many popular hash functions.

Fortunately, there are good hash functions that satisfy all these criteria. The simplest class all consume one byte of the input key per iteration of the inner loop. Within this class, simplicity and speed are closely related, as fast algorithms simply don't have time to perform complex calculations. Of these, one that performs particularly well is the Jenkins One-at-a-time hash, adapted here from an article by Bob Jenkins, its creator.

The avalanche behavior of this hash shown on the right. The image was made using Bret Mulvey's AvalancheTest in his Hash.cs toolset. Each row corresponds to a single bit in the input, and each column to a bit in the output. A green square indicates good mixing behavior, a yellow square weak mixing behavior, and red would indicate no mixing. Only a few bits in the last byte are weakly mixed, a performance vastly better than a number of widely used hash functions.

Many commonly used hash functions perform poorly when subjected to such rigorous avalanche testing. The widely favored FNV hash, for example, shows many bits with no mixing at all, especially for short keys. See the evaluation of FNV by Bret Mulvey for a more thorough analysis.

If speed is more important than simplicity, then the class of hash functions which consume multibyte chunks per iteration may be of interest. One of the most sophisticated is "lookup3" by Bob Jenkins, which consumes input in 12 byte (96 bit) chunks. Note, though, that any speed improvement from the use of this hash is only likely to be useful for large keys, and that the increased complexity may also have speed consequences such as preventing an optimizing compiler from inlining the hash function. Bret Mulvey analyzed an earlier version, lookup2, and found it to have excellent avalanche behavior.

One desirable property of a hash function is that conversion from the hash value (typically 32 bits) to an bucket index for a particular-size hash table can be done simply by masking, preserving only the lower k bits for a table of size 2k (an operation equivalent to computing the hash value modulo the table size). This property enables the technique of incremental doubling of the size of the hash table - each bucket in the old table maps to only two in the new table. Because of its use of XOR-folding, the FNV hash does not have this property. Some older hashes are even worse, requiring table sizes to be a prime number rather than a power of two, again computing the bucket index as the hash value modulo the table size. In general, such a requirement is a sign of a fundamentally weak function; using a prime table size is a poor substitute for using a stronger function.

Collision resolution
If two keys hash to the same index, the corresponding records cannot be stored in the same location. So, if it's already occupied, we must find another location to store the new record, and do it so that we can find it when we look it up later on.

To give an idea of the importance of a good collision resolution strategy, consider the following result, derived using the birthday paradox. Even if we assume that our hash function outputs random indices uniformly distributed over the array, and even for an array with 1 million entries, there is a 95% chance of at least one collision occurring before it contains 2500 records.

There are a number of collision resolution techniques, but the most popular are chaining and open addressing.

Chaining

In the simplest chained hash table technique, each slot in the array references a linked list of inserted records that collide to the same slot. Insertion requires finding the correct slot, and appending to either end of the list in that slot; deletion requires searching the list and removal.

Chained hash tables have advantages over open addressed hash tables in that the removal operation is simple and resizing the table can be postponed for a much longer time because performance degrades more gracefully even when every slot is used. Indeed, many chaining hash tables may not require resizing at all since performance degradation is linear as the table fills. For example, a chaining hash table containing twice its recommended capacity of data would only be about twice as slow on average as the same table at its recommended capacity.

Chained hash tables inherit the disadvantages of linked lists. When storing small records, the overhead of the linked list can be significant. An additional disadvantage is that traversing a linked list has poor cache performance.

Alternative data structures can be used for chains instead of linked lists. By using a self-balancing tree, for example, the theoretical worst-case time of a hash table can be brought down to O(log n) rather than O(n). However, since each list is intended to be short, this approach is usually inefficient unless the hash table is designed to run at full capacity or there are unusually high collision rates, as might occur in input designed to cause collisions. Dynamic arrays can also be used to decrease space overhead and improve cache performance when records are small.

Some chaining implementations use an optimization where the first record of each chain is stored in the table. Although this can increase performance, it is generally not recommended: chaining tables with reasonable load factors contain a large proportion of empty slots, and the larger slot size causes them to waste large amounts of space.

Open addressing
Open addressing hash tables can store the records directly within the array. A hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include:

 * linear probing : in which the interval between probes is fixed—often at 1,
 * quadratic probing : in which the interval between probes increases linearly (hence, the indices are described by a quadratic function), and
 * double hashing : in which the interval between probes is fixed for each record but is computed by another hash function.

The main tradeoffs between these methods are that linear probing has the best cache performance but is most sensitive to clustering, while double hashing has poor cache performance but exhibits virtually no clustering; quadratic hashing falls in-between in both areas. Double hashing can also require more computation than other forms of probing. Some open addressing methods, such as last-come-first-served hashing and cuckoo hashing move existing keys around in the array to make room for the new key. This gives better maximum search times than the methods based on probing.

A critical influence on performance of an open addressing hash table is the load factor; that is, the proportion of the slots in the array that are used. As the load factor increases towards 100%, the number of probes that may be required to find or insert a given key rises dramatically. Once the table becomes full, probing algorithms may even fail to terminate. Even with good hash functions, load factors are normally limited to 80%. A poor hash function can exhibit poor performance even at very low load factors by generating significant clustering. What causes hash functions to cluster is not well understood, and it is easy to unintentionally write a hash function which causes severe clustering.

Example pseudocode
The following pseudocode is an implementation of an open addressing hash table with linear probing and single-slot stepping, a common approach that is effective if the hash function is good. Each of the lookup, set and remove functions use a common internal function findSlot to locate the array slot that either does or should contain a given key.

record pair { key, value } var pair array slot[0..numSlots-1] function findSlot(key) i := hash(key) modulus numSlots loop if slot[i] is not occupied or slot[i].key = key return i         i := (i + 1) modulus numSlots function lookup(key) i := findSlot(key) if slot[i] is occupied  // key is in table return slot[i].value else                    // key is not in table return not found function set(key, value) i := findSlot(key) if slot[i].key = key // (Key already in table. Update value.) slot[i].value := value else // (Insert key and value in un-occupied slot.) // (But first, make sure insert won't overload the table) if the table is almost full rebuild the table larger (note 1) i := findSlot(key) slot[i].key  := key slot[i].value := value

Another example showing open addressing technique. Presented function is converting each part(4) of an Internet protocol address, where NOT is bitwise NOT, XOR is bitwise XOR, OR is bitwise OR, AND is bitwise AND and < > are shift-left and shift-right:

// key_1,key_2,key_3,key_4 are following 3-digit numbers - parts of ip address xxx.xxx.xxx.xxx function ip(key parts) j := 1 do key := (key_2 << 2) key := (key + (key_3 << 7)) key := key + (j OR key_4 >> 2) * (key_4) * (j + key_1) XOR j         key := key AND _prime_	// _prime_ is a prime number j := (j+1) while collision return key

 * note 1 : Rebuilding the table requires allocating a larger array and recursively using the set operation to insert all the elements of the old array into the new larger array. It is common to increase the array size exponentially, for example by doubling the old array size.

function remove(key) i := findSlot(key) if slot[i] is unoccupied return  // key is not in the table j := i     loop j := (j+1) modulus numSlots if slot[j] is unoccupied exit loop k := hash(slot[j].key) modulus numSlots if (j > i and (k <= i or k > j)) or (j < i and (k <= i and k > j)) (note 2) slot[i] := slot[j] i := j     mark slot[i] as unoccupied

 * note 2 : For all records in a cluster, there must be no vacant slots between their natural hash position and their current position (else lookups will terminate before finding the record). At this point in the pseudocode, i is a vacant slot that might be invalidating this property for subsequent records in the cluster. j is such as subsequent record. k is the raw hash where the record at j would naturally land in the hash table if there were no collisions. This test is asking if the record at j is invalidly positioned with respect to the required properties of a cluster now that i is vacant.

Another technique for removal is simply to mark the slot as deleted. However this eventually requires rebuilding the table simply to remove deleted records. The methods above provide O(1) updating and removal of existing records, with occasional rebuilding if the high water mark of the table size grows.

The O(1) remove method above is only possible in linearly probed hash tables with single-slot stepping. In the case where many records are to be deleted in one operation, marking the slots for deletion and later rebuilding may be more efficient.

Open addressing versus chaining
Chained hash tables have the following benefits over open addressing:
 * They are simple to implement effectively and only require basic data structures.
 * From the point of view of writing suitable hash functions, chained hash tables are insensitive to clustering, only requiring minimization of collisions. Open addressing depends upon better hash functions to avoid clustering. This is particularly important if novice programmers can add their own hash functions, but even experienced programmers can be caught out by unexpected clustering effects.
 * They degrade in performance more gracefully. Although chains grow longer as the table fills, a chained hash table cannot "fill up" and does not exhibit the sudden increases in lookup times that occur in a near-full table with open addressing. (see right)
 * If the hash table stores large records, about 5 or more words per record, chaining uses less memory than open addressing.
 * If the hash table is sparse (that is, it has a big array with many free array slots), chaining uses less memory than open addressing even for small records of 2 to 4 words per record due to its external storage.

For small record sizes (a few words or less) the benefits of in-place open addressing compared to chaining are:
 * They can be more space-efficient than chaining since they don't need to store any pointers or allocate any additional space outside the hash table. Simple linked lists require a word of overhead per element.
 * Insertions avoid the time overhead of memory allocation, and can even be implemented in the absence of a memory allocator.
 * Because it uses internal storage, open addressing avoids the extra indirection required for chaining's external storage. It also has better locality of reference, particularly with linear probing. With small record sizes, these factors can yield better performance than chaining, particularly for lookups.
 * They can be easier to serialize, because they don't use pointers.

On the other hand, normal open addressing is a poor choice for large elements, since these elements fill entire cache lines (negating the cache advantage), and a large amount of space is wasted on large empty table slots. If the open addressing table only stores references to elements (external storage), it uses space comparable to chaining even for large records but loses its speed advantage.

Generally speaking, open addressing is better used for hash tables with small records that can be stored within the table (internal storage) and fit in a cache line. They are particularly suitable for elements of one word or less. In cases where the tables are expected to have high load factors, the records are large, or the data is variable-sized, chained hash tables often perform as well or better.

Ultimately, used sensibly any kind of hash table algorithm is usually fast enough; and the percentage of a calculation spent in hash table code is low. Memory usage is rarely considered excessive. Therefore, in most cases the differences between these algorithms is marginal, and other considerations typically come into play.

Coalesced hashing
A hybrid of chaining and open addressing, coalesced hashing links together chains of nodes within the table itself. Like open addressing, it achieves space usage and (somewhat diminished) cache advantages over chaining. Like chaining, it does not exhibit clustering effects; in fact, the table can be efficiently filled to a high density. Unlike chaining, it cannot have more elements than table slots.

Perfect hashing
If all of the keys that will be used are known ahead of time, and there are no more keys that can fit the hash table, perfect hashing can be used to create a perfect hash table, in which there will be no collisions. If minimal perfect hashing is used, every location in the hash table can be used as well.

Perfect hashing gives a hash table where the time to make a lookup is constant in the worst case. This is in contrast to chaining and open addressing methods, where the time for lookup is low on average, but may be arbitrarily large. There exist methods for maintaining a perfect hash function under insertions of keys, known as dynamic perfect hashing. A simpler alternative, that also gives worst case constant lookup time, is cuckoo hashing.

Probabilistic hashing
Perhaps the simplest solution to a collision is to replace the value that is already in the slot with the new value, or slightly less commonly, drop the record that is to be inserted. In later searches, this may result in a search not finding a record which has been inserted. This technique is particularly useful for implementing caching.

An even more space-efficient solution which is similar to this is use a bit array (an array of one-bit fields) for our table. Initially all bits are set to zero, and when we insert a key, we set the corresponding bit to one. False negatives cannot occur, but false positives can, since if the search finds a 1 bit, it will claim that the value was found, even if it was just another value that hashed into the same array slot by coincidence. In reality, such a hash table is merely a specific type of Bloom filter.

Table resizing
With a good hash function, a hash table can typically contain about 70%–80% as many elements as it does table slots and still perform well. Depending on the collision resolution mechanism, performance can begin to suffer either gradually or dramatically as more elements are added. To deal with this, when the load factor exceeds some threshold, we allocate a new, larger table, and add all the contents of the original table to this new table. In Java's HashMap class, for example, the default load factor threshold is 0.75.

This can be a very expensive operation, and the necessity for it is one of the hash table's disadvantages. In fact, some naive methods for doing this, such as enlarging the table by one each time you add a new element, reduce performance so drastically as to make the hash table useless. However, if we enlarge the table by some fixed percent, such as 10% or 100%, it can be shown using amortized analysis that these resizings are so infrequent that the average time per lookup remains constant-time. To see why this is true, suppose a hash table using chaining begins at the minimum size of 1 and is doubled each time it fills above 100%. If in the end it contains n elements, then the total add operations performed for all the resizings is:

 * 1 + 2 + 4 + ... + n = 2n - 1.

Because the costs of the resizings form a geometric series, the total cost is O(n). But we also perform n operations to add the n elements in the first place, so the total time to add n elements with resizing is O(n), an amortized time of O(1) per element.

On the other hand, some hash table implementations, notably in real-time systems, cannot pay the price of enlarging the hash table all at once, because it may interrupt time-critical operations. One simple approach is to initially allocate the table with enough space for the expected number of elements and forbid the addition of too many elements. Another useful but more memory-intensive technique is to perform the resizing gradually: To ensure that the old table will be completely copied over before the new table itself needs to be enlarged, it's necessary to increase the size of the table by a factor of at least (k + 1)/k during the resizing.
 * Allocate the new hash table, but leave the old hash table and check both tables during lookups.
 * Each time an insertion is performed, add that element to the new table and also move k elements from the old table to the new table.
 * When all elements are removed from the old table, deallocate it.

Linear hashing is a hash table algorithm that permits incremental hash table expansion. It is implemented using a single hash table, but with two possible look-up functions.

Another way to decrease the cost of table resizing is to choose a hash function in such a way that the hashes of most values do not change when the table is resized. This approach, called consistent hashing, is prevalent in disk-based and distributed hashes, where resizing is prohibitively costly.

Ordered retrieval issue
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.

Problems with hash tables
Although hash table lookups use constant time on average, the time spent can be significant. Evaluating a good hash function can be a slow operation. In particular, if simple array indexing can be used instead, this is usually faster.

Hash tables in general exhibit poor locality of reference—that is, the data to be accessed is distributed seemingly at random in memory. Because hash tables cause access patterns that jump around, this can trigger microprocessor cache misses that cause long delays. Compact data structures such as arrays, searched with linear search, may be faster if the table is relatively small and keys are cheap to compare, such as with simple integer keys. According to Moore's Law, cache sizes are growing exponentially and so what is considered "small" may be increasing. The optimal performance point varies from system to system; for example, a trial on Parrot shows that its hash tables outperform linear search in all but the most trivial cases (one to three entries).

More significantly, hash tables are more difficult and error-prone to write and use. Hash tables require the design of an effective hash function for each key type, which in many situations is more difficult and time-consuming to design and debug than the mere comparison function required for a self-balancing binary search tree. In open-addressed hash tables it's even easier to create a poor hash function.

Additionally, in some applications, a black hat with knowledge of the hash function may be able to supply information to a hash which creates worst-case behavior by causing excessive collisions, resulting in very poor performance (i.e., a denial of service attack). In critical applications, either universal hashing can be used or a data structure with better worst-case guarantees may be preferable. For details, see Crosby and Wallach's Denial of Service via Algorithmic Complexity Attacks.

Other hash table algorithms
Extendible hashing and linear hashing are hash algorithms that are used in the context of database algorithms used for instance in index file structures, and even primary file organization for a database. Generally, in order to make search scalable for large databases, the search time should be proportional log N or near constant, where N is the number of records to search. Log N searches can be implemented with tree structures, because the degree of fan out and the shortness of the tree relates to the number of steps needed to find a record, so the height of the tree is the maximum number of disc accesses it takes to find where a record is. However, hash tables are also used, because the cost of a disk access can be counted in units of disc accesses, and often that unit is a block of data. Since a hash table can, in the best case, find a key with one or two accesses, a hash table index is regarded as generally faster when retrieving a collection of records during a join operation e.g. SELECT * from customer, orders where customer.cust_id = orders.cust_id and cust_id = X i.e. If orders has a hash index on cust_id, then it takes constant time to locate the block that contains record locations for orders matching cust_id = X. (although, it would be better if the value type of orders was a list of order ids, so that hash keys are just one unique cust_id for each batch of orders, to avoid unnecessary collisions).

Extendible hashing and linear hashing have certain similarities: collisions are accepted as inevitable and are part of the algorithm where blocks or buckets of collision space is added ; traditional good hash function ranges are required, but the hash value is transformed by a dynamic address function : in extendible hashing, a bit mask is used to mask out unwanted bits, but this mask length increases by one periodically, doubling the available addressing space ; also in extendible hashing, there is an indirection with a directory address space, the directory entries being paired with another address (a pointer ) to the actual block containing the key-value pairs; the entries in the directory correspond to the bit masked hash value (so that the number of entries is equal to maximum bit mask value + 1 e.g. a bit mask of 2 bits, can address a directory of 00 01 10 11, or 3 + 1 = 4).

In linear hashing, the traditional hash value is also masked with a bit mask, but if the resultant smaller hash value falls below a 'split' variable, the original hash value is masked with a bit mask of one bit greater length, making the resultant hash value address recently added blocks. The split variable ranges incrementally between 0 and the maximum current bit mask value e.g. a bit mask of 2, or in the terminology of linear hashing, a "level" of 2, the split variable will range between 0 and 3. When the split variable reaches 4, the level increases by 1, so in the next round of the split variable, it will range between 0 and 7, and reset again when it reaches 8.

The split variable incrementally allows increased addressing space, as new blocks are added; the decision to add a new block occurs whenever a key-and=value is being inserted, and overflows the particular block the key-and-value's key hashes into. This overflow location may be completely unrelated to the block going to be split pointed to by the split variable. However, over time, it is expected that given a good random hash function that distributes entries fairly evenly amongst all addressable blocks, the blocks that actually require splitting because they have overflowed get their turn in round-robin fashion as the split value ranges between 0 - N where N has a factor of 2 to the power of Level, level being the variable incremented whenever the split variable hits N.

New blocks are added one at a time with both extendible hashing, and with linear hashing. In extendible hashing, a block overflow ( a new key-value colliding with B other key-values, where B is the size of a block) is handled by checking the size of the bit mask "locally", called the "local depth", an attribute which must be stored with the block. The directory structure, also has a depth, the "global depth". If the local depth is less than the global depth, then the local depth is incremented, and all the key values are rehashed and passed through a bit mask which is one bit longer now, placing them either in the current block, or in another block. If the other block happens to be the same block when looked up in the directory, a new block is added, and the directory entry for the other block is made to point to the new block. Why does the directory have entries where two entries point to the same block ? This is because if the local depth is equal to the global depth of the directory, this means the bit mask of the directory does not have enough bits to deal with an increment in the bit mask length of the block, and so the directory must have its bit mask length incremented, but this means the directory now doubles the number of addressable entries. Since half the entries addressable don't exist, the directory simply copies the pointers over to the new entries e.g. if the directory had entries for 00, 01, 10, 11, or a 2 bit mask, and it becomes a 3 bit mask, then 000 001 010 011 100 101 110 111 become the new entries, and 00's block address go to 000 and 001 ; 01's pointer goes to 010 and 011, 10 goes to 100 and 101 and so on. And so this creates the situation where two directory entries point to the same block. Although the block that was going to overflow, now can add a new block by redirecting the second pointer to a newly appended block, the other original blocks will have two pointers to them. When it is their turn to split, the algorithm will check local vs global depth and this time find that the local depth is less, and hence no directory splitting is required, only a new block be appended, and the second directory pointer moved from addressing the previous block to addressing the new block.

In linear hashing, adding a similarly hashed block does not occurs immediately when a block overflows, and therefore an overflow block is created to be attached to the overflowing block. However, a block overflow is a signal that more space will be required, and this happens by splitting the block pointed to by the "split" variable, which is initially zero, and hence initially points to block zero. The splitting is done by taking all the key-value pairs in the splitting block, and its overflow block(s), hashing the keys again, but with a bit mask of length current level + 1. This will result in two block addresses, some will be the old block number, and others will be a2 = old block number + ( N times 2 ^ (level) )

Let m = N times 2 ^ level ; if h is the original hash value, and old block number = h mod m, and now the new block number is h mod ( m * 2 ), because m * 2 = N times 2 ^ (level+1), then the new block number is either h mod m if (h / m) is even so dividing h/m by 2 leaves a zero remainder and therefore doesn't change the remainder, or the new block number is ( h mod m )  + m because h / m is an odd number, and dividing h / m by 2 will leave an excess remainder of m, + the original remainder. ( The same rationale applies to extendible hashing depth incrementing ).
 * Rationale

As above, a new block is created with a number a2, which will usually occur at +1 the previous a2 value. Once this is done, the split variable is incremented, so that the next a2 value will be again old a2 + 1. In this way, each block is covered by the split variable eventually, so each block is preemptively rehashed into extra space, and new blocks are added incrementally. Overflow blocks that are no longer needed are discarded, for later garbage collection if needed, or put on an available free block list by chaining.

When the split variable reaches ( N times 2 ^ level ), level is incremented and split variable is reset to zero. In this next round, the split variable will now traverse from zero to ( N times 2 ^ (old_level + 1 ) ), which is exactly the number of blocks at the start of the previous round, but including all the blocks created by the previous round.

A simple inference on file storage mapping of linear hashing and extendible hashing
As can be seen, extendible hashing requires space to store a directory which can double in size.

Since the space of both algorithms increase by one block at a time, if blocks have a known maximum size or fixed size, then it is straight forward to map the blocks as blocks sequentially appended to a file.

In extendible hashing, it would be logical to store the directory as a separate file, as doubling can be accommodated by adding to the end of the directory file. The separate block file would not have to change, other than have blocks appended to its end.

Header information for linear hashing doesn't increase in size : basically just the values for N, level, and split need to be recorded, so these can be incorporated as a header into a fixed block size linear hash storage file. However, linear hashing requires space for overflow blocks, and this might best be stored in another file, otherwise addressing blocks in the linear hash file is not as straight forward as multiplying the block number by the block size and adding the space for N,level, and split.

In the next section, a complete example of linear hashing in Java is given, using a in memory implementation of linear hashing, and code to manage blocks as files in a file directory, the whole contents of the file directory representing the persistent linear hashing structure.

Implementations
While many programming languages already provide hash table functionality, there are several independent implementations worth mentioning.
 * Google Sparse Hash The Google SparseHash project contains several hash-map implementations in use at Google, with different performance characteristics, including an implementation that optimizes for space and one that optimizes for speed. The memory-optimized one is extremely memory-efficient with only 2 bits/entry of overhead.
 * MCT provides hashtables similar to Google's, but without restriction on contained values; it also comes with exception safety and support for C++0x features.
 * A number of runtime languages and/or standard libraries use hash tables to implement their support for associative arrays because of their efficiency.

A python implementation of extendible hashing
The file - block management routines aren't there, so this could be added in to make this a real implementation of a database hash index.

A full page is split according to the (local depth)th bit, first by collecting all the directory indices pointing to the full page, updating the pointers according to the d bit being 0 or 1 corresponding to first and second new pages, then reloading all the key-values after hashing each key and using the d bit of each hash to see which page to allocate to. The local depth of each new page is one greater than the old page's local depth, so that the next d bit can be used next time when splitting.

A Java implementation of extendible hashing
A direct Java translation of the above python code, tested to work.

A Java implementation of linear hashing
( usable for simple database indexing of arbitrary size, (almost ?) ) This code evolved out of a need for a bigger Java HashMap. Originally, a Java HashMap standard object was used as a Map to index a heap like database file ( DBF format). But then, a file was encountered with so many records that the OutOfMemoryError was being thrown, so linear hashing seemed like a reasonably simple algorithm to use as a disk based index scheme.

Initially, linear hashing was implemented behind the Java Map interface, mainly the put(k,v) and get(k,v) methods. Generics was used, in order not to get too involved in the key and value details.

debugging to achieve functionality
Custom dumps to System.err was used to verify that blocks were being created, filled, and overflow blocks were of expected number if they existed ( no. = 1 ). This was all done in a purely in-memory implementation.

Later, the standard Java decoupling was introduced, where the original LHMap2 class accepted listeners to events, such as when a block was needed. The listener was then implemented as a block file manager, loading blocks into the block list of the memory LHMap2 object whenever a null block was encountered on the block list, and checking whether virtual machine runtime free memory was low, and retiring blocks using just a basic first-to-last-listed cache removal algorithm (not least recently used (LRU), not least often used ) by saving them to disk file, and then actively invoking the system garbage collector.

Because an application use case existed, which was to externally index a large DBF table, this use case was used as the main test harness for the algorithm implementation.

Each block is a file in this implementation, because blocks are variably sized here to account for generics and variable sized key and value pairs, and overflow blocks are conceptual, not actual as on disc storage, because the block's contents and that of its overflow bucket(s), are saved as a list of alternating keys and values in this implementation. Methods for saving and loading to Object streams was used in a standard java customized object persistence way by implementing the Externalizable interface in the Block data class.

title: Data Structures/Hash Tables


text: Data Structures/All Chapters

title: Data Structures/All Chapters


text:
Japanese/Dialects/Kanto

 * 関東弁 (kantouben) is generally regarded as standard Japanese. It seems to only differ, however, in slang used and some pronunciation. Nevertheless, it is a dialect in its own right, especially when compared to the other variations of Japanese, and will be treated here as such. It, as all other dialects discussed, will be compared with standard Japanese.

Pronunciation

 * There are few major differences in pronunciation. One worth noting appears in the Tokyo-ben (東京弁) section.

Intonation
(no sources found yet)

negative form
The negative form used in the Kanto region is the one used in standard. I list it here because it is different when compared to negative forms of other areas. example: 行かない　（いかない） will not go
 * ～ない is the negative imperfect tense verb ending, and
 * ～なかった is the negative perfective tense verb ending.

need to...
Because the construct of "need to" is just a combination of the negative form of a verb and another word, it is really just a matter of the difference in negative forms. However, as these constructs are often contracted, it is worth noting the differences. The standard "need to" form looks like the following: and in Kanto they are contracted, respectively, as follows:
 * ～なくては　いけない/ならない/だめ/etc...
 * ～なければ　いけない/ならない/だめ/etc...
 * ～なくちゃ　いけない/ならない/だめ/etc...
 * ～なきゃ　いけない/ならない/だめ/etc...

title: Japanese/Dialects/Kanto


text:
User talk:GoStone

My user name reflects my interest in Go, the ancient oriental board game.

I am male and live in the UK.

If I think of anything else I'll let you know!

title: User talk:GoStone


text:
User:Patrik

Hello,

I've got a degree in electronics and have been programming as a hobby on and off for a few years. I've been designing and building small robots are a hobby for the last few years.

I've been contributing to the Robotics Wikibook for about a half year now. Started the Theoretical_Mechanics wikibook to supplement the Robotics wikibook since there wasn't a complete wikibook on this subject.

--Patrik 13:33, 19 Jan 2005 (UTC)

title: User:Patrik


text:
Japanese/Lessons/Days

Counting the days of the month is really pretty simple — with a few exceptions. The first ten days generally follow the "native Japanese" counting stems. After the tenth of the month, all but the 14th, 20th and 24th follow the more basic Chinese-derived counting stems.

The first of the month is an exception, and simply must be memorized as such:
 * １日　ついたち

The second through tenth of the month follow the same native Japanese counting stems as used when counting generic items (つ,　つ,　つ, つ) or people. The ending "〜か" is simply one of the readings for the character for "日".
 * ２日　ふつか
 * ３日　みっか
 * ４日　よっか
 * ５日　いつか
 * ６日　むいか
 * ７日　なのか
 * ８日　ようか
 * ９日　ここのか
 * １０日　とおか

The rest of the days of the month, generally follow the normal pattern using the counters "いち", "に", "さん", etc., and the ending "〜か" is replaced with "〜にち". The numbers 14 and 24 use "〜よっか", not "〜よんにち" as one might assume from the pattern, and 20 uses "はつか", not "にじゅうにち".

Periods of days

 * "前" (まえ), which generally means "before" or "in front of", is used to indicate an amount of time ago.
 * "〜間" (かん) is used to indicate a length of time. It is usually dropped when unambiguous.

When periods of time are expressed in terms of "nights", the counter "泊" (はく) which means "night" or "overnight" in the context of staying somewhere, is affixed to the normal "いち", "に", "さん", etc.

The same character is also used for the word "泊まる" (とまる) which means "to stay" or "to stay over". As in English, this can be combined with "days", which is then read as the days of the week ("いっか", "ふつか", "みっか", "よっか, etc.).

title: Japanese/Lessons/Days


text:
User:DeWayneLehman~enwikibooks

See DeWayne Lehman @ Wikipedia

title: User:DeWayneLehman~enwikibooks


text:
Numerical Methods/Numerical Differentiation

Often in Physics or Engineering it is necessary to use a calculus operation known as differentiation. Unlike textbook mathematics, the differentiated functions are data generated by an experiment or a computer code.

Begin with the Taylor series as seen in Equation 1.

$$ f(x+h) = f(x) + f^{'}(x)h + \frac{f^{(2)}(x)}{2!}h^{2}+\frac{f^{(3)}(x)}{3!}h^{3}+ \cdots \quad (1)$$

Next by cutting off the Taylor series after the fourth term and evaluating it at h and -h yields Equations (2) and (3).

$$ f(x+h) = f(x) + f^{'}(x)h + \frac{f^{(2)}(x)}{2!}h^{2} +\frac{f^{(3)}(c_{1})}{3!}h^{3} \quad (2)$$

$$ f(x-h) = f(x) - f^{'}(x)h + \frac{f^{(2)}(x)}{2!}h^{2} - \frac{f^{(3)}(c_{2})}{3!}h^{3} \quad (3)$$

Then by subtracting Equation (2) by Equation (3) yields.

$$f(x+h) - f(x-h) = 2f^{'}(x)h + \frac{f^{(3)}(c_{1})}{3!}h^{3} + \frac{f^{(3)}(c_{2})}{3!}h^{3}$$

Central Difference
$$f^{'}(x) = \frac{f(x+h)-f(x-h)}{2h} + O(h^{2})$$

Forward Difference
$$f^{'}(x) = \frac{f(x+h)-f(x)}{h} + O(h)$$

Backward Difference
$$f^{'}(x) = \frac{f(x)-f(x-h)}{h} + O(h)$$

Second Derivative
The second order derivatives can be obtained by adding equations (2) and (3) (if properly expanded to include the fourth-derivative-term):

$$f^{''}(x) = \frac{f(x+h)-2f(x)+f(x-h)}{h^2} + O(h^2)$$


text:
Talk:Serial Programming/RS-232 Connections

This module is already a bit long, but here are some more things that might be worth covering. (Perhaps accompanied by splitting the chapter!)
 * Duplex (full, half, simplex)
 * Baud rate detection
 * RJ-45 connectors
 * Using a breakout box
 * Note that RS-232 uses unbalanced circuits, so twisted pair cables aren't useful
 * Baluns can be used to balance the circuits for longer distance transmission
 * RS-422 is similar to RS-232, but has the advantage of balanced circuits

---

Note that RJ-45 connectors are not standardized in regard to RS-232 protocols. There are some devices that use them, and there are enough wires with a Cat-5 line that makes it at least in theory possible to do RS-232 over Cat-5 with RJ-45 connectors, but it is not commonly done that way. In fact, the only "standard connector" specified by RS-232 is the DB-25 connector.

Rob Horning 21:55, 25 May 2005 (UTC)

Discrepancies - Possible Errors

 * According to the D-subminiature article, DE-9 is the correct name of the 9 pin D-shell connector. Links are now added for the D-shell connectors, but each instance of DB-9 should perhaps be replaced with DE-9 (possibly with a note about this common misnomer using a reference to DB-9.)
 * RS-232 signal levels are described more precisely in RS-232 than in this Serial_Programming:RS-232_Connections. The signal levels are not always +15V and -15V. Consider replacing parts of this section with a reference to RS-232.
 * The claim that the handshake signals use negative voltage to indicate "Ready" contradicts my experience. The RS-232 descriptions about "negative voltage has the functional significance of OFF" and "positive has the function ON" also support my experience that e.g. Data Terminal Ready is positive when the DTE is ready and negative otherwise.

KV 02:00, 25 Jun 2005 (UTC)
 * Be bold in editing this if you see factual errors. The information I have put in comes from more technical books related to the subject rather than any "hands-on" experience of messing with the voltages directly on a circuit design level.  I would like to see these changes, however, be based on something concrete and formal specs.

 * The +15V and -15V signals are a part of traditional RS-232 specifications, however. This admittedly is an older spec, and there are ranges of voltages to consider, with newer serial drivers going more toward the +/-5V range or less due to their use in embedded devices.  Still, if you were trying to hook something up to a 30 year old industrial controller using RS-232 connectors, expect the 15V line voltage, or even higher.

 * My experience when trying to purchase electronic components, parts, and cables, the suppliers understand the term DB-9. Until you mentioned the possible term DE-9, I had honestly never even heard of it.  I guess from a purest viewpoint it should be called a DE-9 connector, and the Wikipedia article explains it pretty clearly.  Thanks for the education (although the term DB-9 should also be used in the description somewhere with brief explaination...due to suppliers not really understanding this idea either).

 * It should also be obvious that I was not using the Wikipedia content as source material for this module. I will try and do some cleanup as well based on that source.  If you add anything from other sources, make sure that you note it on the external references area (even from dead-tree sources...include ISBN number instead).   Rob Horning 8 July 2005 18:04 (UTC)

The least significant bit (LSB) is transmitted first in this sequence of bits to form a character.
 * According to http://www.lammertbies.nl/comm/info/RS-232_specs.html and http://www.arcelect.com/rs232.htm the last sentence in Databits has to be changed in:

 * Thanks for the tip with the LSB/MSB change. That was an oversight on my part, and in retrospect, it should have been obvious.  It also makes all forms of RS-232 data compatable at least on the bit level to start with, where the format of the bits is the same for all bit size transmissions except for just the number of bits actually transmitted.  A logical way to organize the protocol.  That and a simple mistake in the writing, so thanks for catching the mistake.  --Rob Horning 09:07, 26 October 2005 (UTC)

Merging
What is the purpose of merging this module with the almost empty module Serial Programming:RS-232 Technical Manual (less then ten sentences in the module)? Shouldn't the almost empty module better be removed and references to it replaced with references to this module?

 * As the original author of this module, I strongly disagree with the premise that this module should be abandoned in favor of another Wikibook. There is a purpose and goal that I have in mind, particularly that I've put into the introduction to this Wikibook.  This is a multi-chapter book about serial data programming, which the RS-232 Technical Manual is really a totally seperate item.  This is not Wikipedia where you can have one and only one article about a particular subject.  IMHO, a separate Wikibook that goes into even more depth would be useful, although one I'm not willing to write at the moment.

 * This other Wikibook started as a part of an editorial conflict me regarding the direction of this Wikibook about serial programming. I am not making a Wikiproject that points to serial programming references, but instead I'm trying to write a book.  This distinction is somehow lost on some people, and don't understand the differences between Wikibooks and Wikipedia.  As a book, I am trying to go into detail about a subject, and build on that knowledge in subsequent chapters.  This is not an easy thing to do, although I am grateful for all of the assistance that has been rendered so far to improve these chapters I've already written.

 * In short, I don't see why the two Wikibooks can't be made for this subject. The Technical Manual is to be more of a reference guide, and this Wikibook is to be an introduction to the subject.  In short, I am trying to teach about serial programming, and it is my intention to turn this into a textbook.  Those are two very different goals and need to be written very differently.  That they may have some similar content is besides the point.  --Rob Horning 17:00, 15 October 2005 (UTC)

Where is it? (Hardware flow control description)
This is a part of the "Hardware" flow control protocol that will be explained below

At least the checked URL ? Two URL's below tells opposite voltage's meaning "stop" and "go".

http://www.camiresearch.com/Data_Com_Basics/RS232_standard.html

http://www.taltech.com/TALtech_web/resources/intro-sc.html#Synch

PS: This seems to claim 0=go, 1=stop also, but it is not said frankly: http://www.hw-server.com/rs232_signals.html#t6

 * I guess I need to simply pull out an oscilloscope and find out for myself with a difinitive answer from the real world. I would venture to bet that both + voltage and - voltage being asserted as a logical "1" does occur.  --Rob Horning 12:55, 5 March 2006 (UTC)


text:
Numerical Methods/Errors Introduction

When using numerical methods or algorithms and computing with finite precision, errors of approximation or rounding and truncation are introduced. It is important to have a notion of their nature and their order. A newly developed method is worthless without an error analysis. Neither does it make sense to use methods which introduce errors with magnitudes larger than the effects to be measured or simulated. On the other hand, using a method with very high accuracy might be computationally too expensive to justify the gain in accuracy.

Accuracy and Precision
Measurements and calculations can be characterized with regard to their accuracy and precision. Accuracy refers to how closely a value agrees with the true value. Precision refers to how closely values agree with each other. The following figures illustrate the difference between accuracy and precision. In the first figure, the given values (black dots) are more accurate; whereas in the second figure, the given values are more precise. The term error represents the imprecision and inaccuracy of a numerical computation.

Absolute Error
Absolute Error is the magnitude of the difference between the true value x and the approximate value xa. Therefore absolute error=[x-xa] The error between two values is defined as

 * $$ \epsilon_{abs}= \left \| x - xa \right \| \quad, $$

where $$x$$ denotes the exact value and $$xa$$ denotes the approximation.

Relative Error
The relative error of $$\tilde{x}$$ is the absolute error relative to the exact value. Look at it this way: if your measurement has an error of ± 1 inch, this seems to be a huge error when you try to measure something which is 3 in. long. However, when measuring distances on the order of miles, this error is mostly negligible. The definition of the relative error is

 * $$ \epsilon_{rel} = \frac{\left \| \tilde{x} - x \right \|}{\left \| x \right \|} \quad . $$

Sources of Error
In a numerical computation, error may arise because of the following reasons:
 * Truncation error

 * Roundoff error

Truncation Error
The word 'Truncate' means 'to shorten'. Truncation error refers to an error in a method, which occurs because some number/series of steps (finite or infinite) is truncated (shortened) to a fewer number. Such errors are essentially algorithmic errors and we can predict the extent of the error that will occur in the method. For instance, if we approximate the sine function by the first two non-zero term of its Taylor series, as in $$\sin(x) \approx x - \tfrac16 x^3$$ for small $$x$$, the resulting error is a truncation error. It is present even with infinite-precision arithmetic, because it is caused by truncation of the infinite Taylor series to form the algorithm.

Roundoff Error
Roundoff error occurs because of the computing device's inability to deal with certain numbers. Such numbers need to be rounded off to some near approximation which is dependent on the word size used to represent numbers of the device.

title: Numerical Methods/Errors Introduction


text:
Spanish/Vocabulary/Arts

= Los Artes (Arts) =

Bellas Artes (Fine Arts)

 *  la alfarería  :  pottery
 *  la arquitectura  :  architecture
 *  el arte conceptual  :  conceptual art
 *  la caligrafía  :  calligraphy
 *  el cine  :  film
 *  la danza  :  dance
 *  el dibujo  :  drawing
 *  la escultura  :  sculpture
 *  la fotografía  :  photography
 *  el grabado  :  printmaking
 *  el mosaico  :  mosaics
 *  la música  :  music
 *  la pintura  :  painting
 *  la poesía  :  poetry
 *  el teatro  :  theatre

La alfarería (Pottery)

 *  el alambre para cortar  :  cutting wire
 *  la arcilla  :  clay
 *  el cono pirométrico  :  pyrometric cone
 *  el cuchillo para desbastar  :  fettling knife
 *  las espátulas de modelar  :  wooden modeling tools
 *  el estique  :  rib
 *  el horno  :  kiln
 *  el punzón  :  needle tool
 *  el raspador  :  trimming tool
 *  el soporte  :  stilt
 *  el torno de alfarero  :  potter's wheel
 *  el torno de mesa  :  banding wheel

La caligrafía (Calligraphy)

 *  el cálamo  :  reed pen
 *  el estilo  :  stylus
 *  el lápiz de grafito  :  lead pencil
 *  el papel  :  paper
 *  el pincel  :  writing brush
 *  la pluma  :  pen
 *  la pluma de ave  :  quill
 *  la pluma de caña  :  cane pen
 *  la pluma metálica  :  steel pen

La sala de cine (movie theater/cinema)

 *  la butaca  :  seat
 *  el altavoz  :  speaker
 *  la pantalla de proyección  :  projection screen
 *  el proyector  :  projector
 *  la sala de proyección  :  projection room

El plató de rodaje (movie set)

 *  la cámara  :  camera
 *  el camerino  :  dressing room
 *  la claqueta  :  clapper/the slate
 *  el número de la escena  :  time code
 *  el difusor  :  diffuser
 *  el dolly  :  dolly
 *  el equipo de sonido y de grabación  :  sound recording equipment
 *  la esquema de iluminación  :  lighting set-up
 *  el monitor de control del director  :  director’s control monitors
 *  el proyector  :  spotlight
 *  el set  :  set
 *  la silla del director  :  director’s seat
 *  las sillas de los actores  :  actors’ seats
 *  el vestuario  :  costume

El dibujo (Drawing)

 *  el carboncillo  :  charcoal
 *  el crayón  :  crayon
 *  el maniquí  :  articulated mannequin
 *  el marcador  :  marker pen
 *  la mesa de dibujo  :  drafting table
 *  el papel  :  paper
 *  la pluma  :  pen
 *  el rotulador  :  felt tip pen
 *  la tinta china  :  Chinese ink/Indian ink

El grabado (Printmaking)

 *  el grabado en madera  :  wood engraving
 *  el bruñidor  :  burnisher
 *  la bruza  :  brush
 *  el buril  :  engraver's chisel
 *  el cabo  :  smoking candle
 *  el calibrador  :  caliper
 *  el carboncillo litográfico  :  litho crayon
 *  el cincel de rincón  :  V-shaped gouge
 *  el cuchillo de contornear  :  knife
 *  el escoplo  :  chisel
 *  la espátula  :  spatula
 *  el frotador  :  baren
 *  el graneador  :  rocking tool
 *  la gubia  :  U-shaped gouge
 *  el lápiz corrector de piedra pómez  :  pumice correcting pencil
 *  el lápiz litográfico  :  litho pencil
 *  la matriz  :  figure
 *  la matriz en relieve  :  raised figure
 *  la matriz plana  :  plane figure
 *  la matriz tallada  :  incised figure
 *  el mazo  :  mallet
 *  el papel  :  paper
 *  la piedra de afilar  :  sharpening stone
 *  la pinza  :  hand vise
 *  la placa de cobre  :  copper plate
 *  la plancha de entintado  :  inking slab
 *  la prensa  :  press
 *  la prensa de aguafuerte  :  etching press
 *  la prensa de pruebas  :  proof press
 *  la prensa litográfica  :  lithographic press
 *  la pulidora  :  levigator
 *  la punta seca  :  drypoint
 *  el rascador  :  scraper
 *  el rodillo entintador  :  brayer
 *  el rodillo para barnizar  :  varnish-roller
 *  la ruedecilla  :  roulette
 *  la sanguina  :  red ocher pencil
 *  el tampón  :  dabber
 *  la tarlatana  :  tarlatan
 *  la tinta  :  ink
 *  la tinta litográfica  :  lithographic tusche

La pintura (Painting)

 *  el aerógrafo  :  airbrush
 *  la brocha  :  fan brush
 *  el caballete  :  easel
 *  el cuchillo paleta  :  painting knife
 *  la espátula  :  spatula
 *  la gama de colores  :  color chart
 *  el lápiz de color  :  colored pencil
 *  el lienzo  :  canvas
 *  el óleo  :  oil paint
 *  la paleta con huecos para pintura  :  palette with hollows
 *  la paleta con tarrito  :  palette with dipper
 *  el pastel  :  dry pastel
 *  el pastel al óleo  :  oil pastel
 *  la pastilla de acuarela  :  watercolor cake
 *  el pincel  :  brush
 *  el pincel plano  :  flat brush
 *  el pincel sumie  :  sumi-e brush
 *  el pigmento  :  pigment
 *  el tarrito para pincel  :  dipper
 *  el tiento  :  maulstick
 *  el tubo de acuarela  :  watercolor tube
 *  el aceite de linaza  :  linseed oil
 *  el aguarrás  :  turpentine
 *  el barniz  :  varnish
 *  el fijador  :  fixative
 *  el soporte  :  support
 *  el cartón  :  cardboard
 *  el lienzo  :  canvas
 *  el papel  :  paper
 *  la tabla  :  panel

El teatro (theatre)

 *  la bambalina  :  backstage
 *  los bastidores  :  wings
 *  la cabina de control  :  control room
 *  la caja del escenario  :  stage house
 *  el camerino  :  dressing room
 *  el cuadro de aviso  :  prompt box
 *  el escenario  :  stage
 *  los focos  :  spotlights
 *  el foso de orquesta  :  orchestra pit
 *  la pasarela  :  catwalk
 *  el proscenio  :  proscenium
 *  los proyectores  :  lights
 *  los rastrillos  :  rakes
 *  la sala  :  house
 *  el techo acústico  :  acoustic ceiling
 *  el telón  :  curtain
 *  la tramoya  :  fly system
 *  la trampilla  :  trap

= Verbos =
 *  dibujar:  to draw
 *  pintar:  to paint
 *  crear:  to create
 *  bosquejar, esbozar:  to sketch

title: Spanish/Vocabulary/Arts


text:
Italian/Vocabulary

 * Adjectives
 * Animals
 * /Basic Words and Phrases/
 * Clothes
 * Colors
 * /Common phrases/
 * Computing
 * Days and Months
 * Family
 * Food
 * Greetings and Introductions
 * Health and Medical
 * Hobbies and Leisure Activities
 * Household
 * Household Chores
 * Human Body
 * Music
 * Professions
 * School
 * Shops and Services
 * Street
 * Symbols
 * Time
 * Travel
 * Weather

Italià/Vocabulari Italiano/Vocabulario

title: Italian/Vocabulary


text:
Italian/Vocabulary/Music

Instruments

 *  La tromba   trumpet
 *  La chitarra   guitar
 *  Il basso   bass
 *  La batteria   drums
 *  La tastiera   keyboard
 *  Il tamburo  drum
 *  Il flauto   flute
 *  Il corno   horn
 *  Il violino   violin
 *  Il pianoforte/Il piano   piano

Italià/Vocabulari/Música Italiano/Vocabulario/Música

title: Italian/Vocabulary/Music


text:
Tetum

Table of contents

 * 1) /Introduction/
 * 2) /Greetings/
 * 3) /Numbers/

External Resources
There are English-Tetun textbooks and other resources available at (http://www.tetundit.tl/Publications.html).

Tetum

title: Tetum


text:
Tetum/Numbers

Cardinal Numbers

 * ida one
 * rua two
 * tolu three
 * haat four
 * lima five
 * neen six
 * hitu seven
 * ualu eight
 * sia nine
 * sanulu ten

 * sanulu-resin-ida eleven
 * sanulu-resin-rua twelve
 * sanulu-resin-tolu thirteen
 * sanulu-resin-haat fourteen
 * sanulu-resin-lima fifteen
 * sanulu-resin-neen sixteen
 * sanulu-resin-hitu seventeen
 * sanulu-resin-ualu eighteen
 * sanulu-resin-sia nineteen
 * ruanulu twenty

 * tolunulu thirty
 * haatnulu forty
 * limanulu fifty
 * neennulu sixty
 * hitunulu seventy
 * ualunulu eighty
 * sianulu ninety
 * atus ida one hundred

 * atus rua two hundred
 * atus tolu three hundred
 * atus haat four hundred
 * atus lima five hundred
 * atus neen six hundred
 * atus hitu seven hundred
 * atus ualu eight hundred
 * atus sia nine hundred
 * rihun ida one thousand
 * rihun rua two thousand
 * rihun tolu three thousand

title: Tetum/Numbers