Beginner Programming
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed ForumsOtherBeginner Programming

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old August 7th, 2011, 03:22 AM
jakotheshadows's Avatar
jakotheshadows jakotheshadows is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Aug 2009
Posts: 149 jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level) 
Time spent in forums: 3 Days 12 h 1 m 16 sec
Reputation Power: 35
Homework: Tries

I'm confused on the properties of Tries. I'm looking at a definition from Data Structures & Algorithms in Java 5th ed. and it gives the following:

A standard trie T storing a collection S of s strings of total length n from an alphabet of size d has the following properties-
*Every internal node of T has at most d children.
*T has s external nodes.
*The height of T is equal to the length of the longest string in S.
*The number of nodes of T is O(n).

My confusion is over the fact that tries are supposed to be commonly used to store things like dictionaries. T having s external nodes is the source of my confusion. Suppose I wish to add the following two words to the trie: "bar" and "bard".
After adding "bar", 'r' would be an external node accounting for one string in s. If I then add "bard" then that 'r' would no longer be an external node. Would I then just have two 'r' nodes coming from the 'a' node with one being internal and one being external, or can the words "bar" and "bard" simply not exist in the same trie?

Reply With Quote
  #2  
Old August 8th, 2011, 09:10 AM
jakotheshadows's Avatar
jakotheshadows jakotheshadows is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Aug 2009
Posts: 149 jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level)jakotheshadows User rank is Sergeant Major (2000 - 5000 Reputation Level) 
Time spent in forums: 3 Days 12 h 1 m 16 sec
Reputation Power: 35
I figured this out once the school's email maintenance was done and I got in touch with my teacher. My homework assignment doesn't strictly adhere to the book's definition of a standard trie.

Reply With Quote
Reply

Viewing: Dev Shed ForumsOtherBeginner Programming > Homework: Tries

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap