Succinct Trees ppt.
seminar surveyer Active In SP Posts: 3,541 Joined: Sep 2010 
28012011, 01:46 PM
Succinct Trees .ppt (Size: 254.5 KB / Downloads: 66) Sivaramaiah.B.V M. Sc. (Engg.) in Computer Science and Networking Module Leader: N.D.Gangadhar Contents Introduction to Trees Succinct Trees Representation of Trees LOUDS Representation Balanced Parentheses DOUDS Representation Introduction to Trees Trees are the most fundamental objects which stores a large amount of data. Standard representation of the binary trees on ‘n’ nodes using pointers take O(n log n) bits of space. The extra space 2n is needed in order to support constant time navigation between tree nodes. Succinct trees Succinct trees takes only “2n+O(n)” bits and support constant time computation and a set of Query operations: Parent(x): returns the parent of node x. Degree(x): returns the degree i.e. number of children of node x. Child(x,i): I’th child at node x. Depth(x): height or distance from root x. LevelAncestor(x,d): return the ancestor of x with depth d. Binary tree representation A Binary Trees on ‘n’ nodes can be represented using “2n+O(n)” bits to support: 1) Parent 2) Left child 3) Right child in constant time. Ordered trees A rooted ordered tree of “n” nodes: Navigational operations are  Parent(x)=a  first child(x)=b  next sibling(x)=c Other operations are  degree(x)  sub tree size(x) LOUDS Representation Louds is “Level Order Unary Degree Sequence”. This is the name because of traversing the tree in level order and writing the sequence of each node in unary order. The node with 3 children is written as 1110. The parent and child can be formulated as parent(x)=1+rank0(select1(x)) child(x)=rank1(select0(x1)+k) Now computing parent(7), for the first we need to calculate select1(7). Select1(7)=10, which is one corresponding position of the node “g”. Next is Rank0(10)=3, which gives the number of 0’s preceding the unary degree of “g” parent. G’s parent position is 1+Rank0(10)=4 and the node is “D”. Balanced Parentheses Representation This representation is obtained by traversing the tree by depth first order writing a left parentheses when node is encountered first and a closing parentheses when the same node is encountered again while going up after traversing the sub tree. The directions of parentheses is shown in figure. The operations are  Parent(x)=Rankopen(enclose(selectopen(x))) subtreeSize(x)=(Findclose(selectopen(x))selectopen(x)+1/2) firstchild(x)=x+1 Rightsibling(x)=Rankopen(Findclose(selectopen(x))+1) For the computation of parent(6), selectopen(6) should be computed. Selectopen(6)=8, which is the position of open parentheses associated to node “j”. Then, enclose(8)=3, which is the position of the closest open parenthesis associated to j’s parent. At last Rank(3)=3, we get the identifier j’s parent. Another computation is finding the SubtreeSize(9). Selectopen(9)=16, which is the position of the “(” of the node “d”. Findclose(16)=23, which is the position of “)” associated to “d”. Then the SubtreeSize=(2316+1)/2=4. DFUDS Representation DFUDS is DepthFirst Unary Degree Sequence. DFUDS combines both LOUDS and BP representation and benefits of both. Due to the combination of both representation, it is able to support all the query operations with in the (2n+O(n)) bits. 



Important Note..!
If you are not satisfied with above reply ,..PleaseASK HERE
So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this pagePossibly Related Threads...  
Thread  Author  Replies  Views  Last Post  
NEAREST NEIGHBOUR MATCHING USING K DTREES pdf  seminar projects maker  0  243 
28092013, 01:05 PM Last Post: seminar projects maker 

Rtrees Report  study tips  0  305 
09052013, 04:07 PM Last Post: study tips 

Binary Search Trees PPT  study tips  0  322 
03052013, 03:10 PM Last Post: study tips 

(Linear, Circular, Doubly) Linked Lists, Stacks, Queues, Trees  study tips  0  403 
13042013, 04:52 PM Last Post: study tips 

ppt on Trees  project girl  0  299 
24012013, 02:33 PM Last Post: project girl 

Trees Report  project girl  0  367 
21012013, 10:15 AM Last Post: project girl 

BTrees report  project girl  0  321 
19122012, 02:36 PM Last Post: project girl 

Decision Trees for Uncertain Data pdf  project girl  0  395 
18122012, 04:35 PM Last Post: project girl 

MultiWay search Trees PPT  project girl  0  339 
10122012, 01:36 PM Last Post: project girl 

Splay Trees PPT  project girl  0  551 
27112012, 01:28 PM Last Post: project girl 