User Tag List

Results 1 to 3 of 3

Thread: [Request] Red-black tree extension

  1. #1
    Clicker Fusion 2.5 DeveloperAndroid Export ModuleHTML5 Export ModuleSWF Export Module

    Join Date
    Apr 2007
    Posts
    208
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    [Request] Red-black tree extension

    Hi, I am looking for a way of storing a large number of string values in a dictionary and I am looking for the most efficient method of searching the dictionary for a particular string. I think the implementation of a red-black tree would be the most efficient method, but as I don't code c++ I can't write it myself. A dictionary generally tends to be static so I am not concerned about the amount of computation required to add/delete items from a red-black tree. Maybe someone can find it already coded in c++ and simply implement it?

    Thanks, ~Matt

  2. #2
    Clickteam Clickteam
    Anders's Avatar
    Join Date
    Jun 2006
    Location
    Denmark, ┼rhus
    Posts
    3,455
    Mentioned
    4 Post(s)
    Tagged
    1 Thread(s)

    Re: [Request] Red-black tree extension

    I recall from our algorithm and data structures course that red-black trees is a pain to implement properly.

    Besides, for most things a binary search is sufficient as you get O(log n) lookup time. Red-black trees are mainly used for inserting a lot of elements and keeping the tree balanced which you said wasn't really a priority.

  3. #3
    Clicker Fusion 2.5 DeveloperAndroid Export ModuleHTML5 Export ModuleSWF Export Module

    Join Date
    Apr 2007
    Posts
    208
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Re: [Request] Red-black tree extension

    Well the idea is that the red-black tree implementation will be used to form a balanced tree in the first place. Yes in the general case you have O(log n) complexity with a standard binary tree, but in the case you added those items in alphabetical order you can manage to form an all-left binary tree or an all-right binary tree, hence the complexity of that given situation is equivalent to a linear search i.e. O(n). The red-black tree keeps things balanced on both sides, and although initially forming that tree is costly, it doesn't matter because you don't intend to make frequent modifications to the tree structure. It's forming that tree structure in the first place which is important.

    [Edit]
    Well thinking about it, a binary search would be fine. (If the data is already sorted anyway.) So perhaps someone can make an extension to do such a thing?

Similar Threads

  1. MMF2 Extension Request : OE-Cake Fluid extension
    By pyromane in forum Extension Development
    Replies: 5
    Last Post: 1st July 2013, 03:51 AM
  2. Oh Tree object..Oh darling Tree object..Problem
    By Orpa1 in forum Multimedia Fusion 2 - Technical Support
    Replies: 39
    Last Post: 2nd August 2009, 08:00 PM
  3. [Request] Useing Tree Control + FTP object
    By Locaz00 in forum Multimedia Fusion 2 - Technical Support
    Replies: 2
    Last Post: 11th April 2009, 04:14 AM
  4. Tree Control, save and load tree bug?
    By Decal in forum Multimedia Fusion 2 - Technical Support
    Replies: 3
    Last Post: 11th April 2008, 12:13 PM
  5. Tree Control - Explore Path - Extension specific?
    By MetalGeo in forum Multimedia Fusion 2 - Technical Support
    Replies: 0
    Last Post: 6th January 2007, 01:48 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •