Correr una posición a la derecha un vector

for(int i = first+1,i<=length(vector_tree)-1,i++){
int aux = vector_tree[i];
vector_tree[i] = vector_tree[first];
vector_tree[first] = aux;
}
vector_tree[first] = element;

Blog interesante!! Sobre aprendizaje y programación.

http://okasaki.blogspot.com/2008/02/games-for-programmers-zendo.html

Comparación de árboles

La comparación de bosques de árboles es un problema NP-hard.

Listado de todas las EDA's (from Wikipedia )

Lista de la estructuras de datos existentes sacadas de la wikipedia

Data types

Primitive types

• Boolean
• Character
• Integer
• String
• Double
• Float

Composite types

• Record (also called tuple or struct)
• Union
• Tagged union (also called a variant, variant record, discriminated union, or disjoint union)

Abstract data types

• Container
• Deque
• List
• Map
• Multimap
• Multiset
• Priority queue
• Queue
• Set
• Stack
• String
• Tree

Some properties of abstract data types:

Structure	Stable	Unique	Cells per Node
Bag (multiset)	no	no	1
Set	no	yes	1
List	yes	no	1
Map	no	yes	2

"Stable" means that input order is retained. Other structures such as "linked list" and "stack" cannot easily be defined this way because there are specific operations associated with them.

Linear data structures

Arrays

• Array
• Bit field
• Bit array
• Bitboard
• Bitmaps
• Images
• Dynamic array
• Circular buffer
• Control table
• Gap Buffer
• Hashed array tree
• Heightfields
• Lookup table
• Matrix
• Parallel array
• Sparse array
• Sparse matrix

Lists

• Linked list
• Doubly linked list
• Xor linked list
• Unrolled linked list
• Zipper
• VList
• Skip list
• Jump list
• Self-organizing list

Trees

Binary trees

• Binary tree
• Binary search tree
• Self-balancing binary search tree
• Randomized binary search tree
• Weight-balanced tree
• Threaded binary tree
• AVL tree
• Red-black tree
• AA tree
• Scapegoat tree
• Splay tree
• T-tree
• Rope
• Top Trees
• Tango Trees
• Cartesian tree
• Treap

B-trees

• B-tree
• B+ tree
• B*-tree
• B sharp tree
• Dancing tree
• 2-3 tree
• 2-3-4 tree
• Fusion tree
• Bx-tree

Heaps

• Heap
• Binary heap
• Binomial heap
• Fibonacci heap
• 2-3 heap
• Soft heap
• Pairing heap
• Leftist heap
• Treap
• Beap
• Skew heap
• Ternary heap
• D-ary heap
• Van Emde Boas tree

Tries

In these data structures each tree node compares a bit slice of key values.

• Trie
• Radix tree
• Suffix tree
• Suffix array
• FM-index
• Generalised suffix tree
• B-trie
• Judy array

Multiway trees

• Ternary search tree
• And–or tree
• (a,b)-tree
• Link/cut tree
• SPQR-tree
• Spaghetti stack
• Disjoint-set data structure
• Fusion tree
• Enfilade
• Exponential tree
• Fenwick tree

Space-partitioning trees

This is data structures used for space partitioning or binary space partitioning.

• Segment tree
• Interval tree
• Range tree
• Bin
• Kd-tree
• Implicit kd-tree
• Min/max kd-tree
• Adaptive k-d tree
• Kdb tree
• Quadtree
• Octree
• Linear octrees
• Z-order
• UB-tree
• R-tree
• R+ tree
• R* tree
• Hilbert R-tree
• X-tree
• Metric tree
• Cover tree
• M tree
• VP-tree
• BK-tree
• Bounding interval hierarchy
• BSP tree

Application-specific trees

• Syntax tree
• Abstract syntax tree
• Parse tree
• Decision tree
• Alternating decision tree
• Minimax tree
• Expectiminimax tree
• Finger tree

Hashes

• Hash table
• Bloom filter
• Hash list
• Hash tree
• Prefix hash tree
• Hash trie
• Hash array mapped trie
• Distributed hash table
• Koorde

Graphs

• Graph
• Adjacency list
• Adjacency matrix
• Graph-structured stack
• Scene graph
• Binary decision diagram
• Zero suppressed decision diagram
• And-inverter graph
• Propositional directed acyclic graph

Bolean Formules:

• Decision List.
• Decision Tree.
  

Problema 4

Dado un vector desordenado de v[1..n] elementos, demuestra que los siguientes problemas son linealmente equivalentes:

1. Selección: El problema 2.
2. Mediana: Encontrar la mediana en un vector desordenado.
3. Descomposición: Separar v en dos vectores X y Y, tal que para todo elemento x de X y para todo elemento y de Y se cumpla que x <= y.
   

Problema 3

Diseña un algoritmo divide y vencerás lo más eficiente posible que dado un vector n elementos y un k, tenga el siguiente comportamiento:

k= 3 1,2,3,4,5,6

4,5,6,1,2,3

sin utilizar un vector auxiliar

Problema 2

Diseñar un algoritmo que dado un vector desordenado de n elementos y un natural k, encuentre el elemento k-ésimo.

Problema 1

Dado dos vectores ordenados crecientemente con n elementos y dado un natural k, diseñar un algoritmo que encuentre el k-ésimo elemento más pequeño en un tiempo log n.