Succinct Trees ppt.
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
seminar surveyer
Active In SP
**

Posts: 3,541
Joined: Sep 2010
#1
28-01-2011, 01:46 PM





.ppt   Succinct Trees .ppt (Size: 254.5 KB / Downloads: 65)

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(x-1)+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=(23-16+1)/2=4.

DFUDS Representation
DFUDS is Depth-First 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.








Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK 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 page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  NEAREST NEIGHBOUR MATCHING USING K D-TREES pdf seminar projects maker 0 238 28-09-2013, 01:05 PM
Last Post: seminar projects maker
  R-trees Report study tips 0 299 09-05-2013, 04:07 PM
Last Post: study tips
  Binary Search Trees PPT study tips 0 317 03-05-2013, 03:10 PM
Last Post: study tips
  (Linear, Circular, Doubly) Linked Lists, Stacks, Queues, Trees study tips 0 399 13-04-2013, 04:52 PM
Last Post: study tips
  ppt on Trees project girl 0 295 24-01-2013, 02:33 PM
Last Post: project girl
  Trees Report project girl 0 361 21-01-2013, 10:15 AM
Last Post: project girl
  B-Trees report project girl 0 313 19-12-2012, 02:36 PM
Last Post: project girl
  Decision Trees for Uncertain Data pdf project girl 0 385 18-12-2012, 04:35 PM
Last Post: project girl
  Multi-Way search Trees PPT project girl 0 331 10-12-2012, 01:36 PM
Last Post: project girl
  Splay Trees PPT project girl 0 543 27-11-2012, 01:28 PM
Last Post: project girl