Monthly Archives: October 2011

Implementing Trie datastructure in C

In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key it is associated with. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest.

The term trie comes from retrieval.Trie data structure is a tree with each node consisting of one letter as data and pointer to the next node. It uses Finite Deterministic automation. That means, it uses state to state transition.

This is a trie for keys “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, and “inn”. When we need to do auto complete for the starting characters, “te”, we need to get output tea, ted and ten. Instead of checking regular expression match for all the words in the database, it will make use of transitions. First character is t. Then in the root element, it will make transition for ‘t’ so that it will reach the node with data ‘t’, then at node ‘t’, it will make transition for next node ‘e’. At that point, we need to follow all paths from node ‘e’ to leaf nodes so that we can get the paths t->e->a, t->e->d and t->e->n. This is the basic algorithm behind implementing an efficient auto complete.

I implemented it using dfs(Depth First Search). DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal node is found, or until it hits a node that has no children. Then the search backtracks, returning to the most recent node it hasn’t finished exploring. In a non-recursive implementation, all freshly expanded nodes are added to a stack for exploration.

The complete code of this program is available in https://bitbucket.org/vidyakv/trie-datastructure/changeset/8c9e1cc33592

Advertisements

Bitwise Operators in C

Bitwise operator is an operator that manipulates individual bits. The bitwise operators are similar to the logical operators, except that they work on a smaller scale — binary representations of data. We need to know about the precedences and associativities of different bitwise operators for efficient and error prone coding. Precedence is the priority for grouping different types of operators with their operands. Associativity is the left-to-right or right-to-left order for grouping operands to operators that have the same precedence. An operator’s precedence is meaningful only if other operators with higher or lower precedence are present. Expressions with higher-precedence operators are evaluated first. The grouping of operands can be forced by using parentheses.

The following table lists C operators in order of precedence (highest to lowest). Their associativity indicates in what order operators of equal precedence in an expression are applied.

Operator Description Associativity
( )[ ].– >

++, —

Parentheses (function call)
Brackets (array subscript)
Member selection via object name
Member selection via pointerPostfix increment/decrement
left-to-right
++  —
+  –
!  ~
(type)
*
&
sizeof
 
Prefix increment/decrement
Unary plus/minus
Logical negation/bitwise complement
Cast (change type)
Dereference
Address
Determine size in bytes
right-to-left
*  /  % Multiplication/division/modulus left-to-right
+  – Addition/subtraction left-to-right
<<  >> Bitwise shift left, Bitwise shift right left-to-right
<  <=
>  >=
Relational less than/less than or equal to
Relational greater than/greater than or equal to
left-to-right
==  != Relational is equal to/is not equal to left-to-right
& Bitwise AND left-to-right
^ Bitwise exclusive OR left-to-right
| Bitwise inclusive OR left-to-right
&& Logical AND left-to-right
| | Logical OR left-to-right
? : Ternary conditional right-to-left
=
+=  -=
*=  /=
%=  &=
^=  |=

<<=  >>=

Assignment
Addition/subtraction assignment
Multiplication/division assignment
Modulus/bitwise AND assignment
Bitwise exclusive/inclusive OR assignment
Bitwise shift left/right assignment
right-to-left
, Comma (separate expressions) left-to-right
The WordPress.com Blog

The latest news on WordPress.com and the WordPress community.