Tech Off Post

Single Post Permalink

View Thread: AVL tree vs red-black tree
  • User profile image

    MasterPie said:
    Mr Crash said:

    Forgive me for thinking you were asking a hw question. It's very typical for CS students to come onto a forum or QandA site to ask for help on some homework problem. Their posts generally are vague and of "hit and run...ask question, get quick answer, leave" form, prompting an answer that can at times be a 500 word essay. Sadly, questions on CS homework (I'm a CS student btw) are just as vague (as well as uninteresting) as those. Additionally, they're questions that are really only asked in a CS undergrad context.


    Thus, you have to understand why some of us might jump the gun when we see questions that follow the same pattern. While we would happily answer a CS hw question, I and many others would prefer that students find the answer on their own as hard work will only benefit them in the end.


    But you've clarified your question and added some context. My apologies for classifying you in the CS slackers group. Tongue Out


    As Dexter and others have said, people very rarely worry about each specific data structure in the context of a large application or system. If you worry too much about why basic arithmetic works the way it does, then you'll waste time that could be better spent solving the complex problem. Not to say that it's something you shouldn't care about at all, especially if you're in the process of designing a new tree based algorithm. But, if you're trying to solve a problem or create an app, you might be better off defaulting to your language's premade data structures as a lot of thought has already gone in to the construction of these implementations.


    Actually, I think that (correct me if I'm wrong guys) either Java's or .NET's list implementations will morph their data structure backings so as to work appropriately for your data. Though, this could just be my imagination. Wink

    Java's or .NET's list implementations will morph their data structure backings so as to work appropriately for your data


    To the best of my knowledge only HybridDictionary fits this description. It uses a list when it contains only a few elements and a hashtable otherwise.


    Quick summary:

    - List<T>, Queue, Stack, ArrayList, SortedList - array

    - Dictionary<K, V>, HashSet<T>, Hashtable - hashtable

    - SortedDictionary<K, V>, SortedSet<T> - red-black tree