Red/Black trees and AVL trees

[Danimal1209]

So, I have had lectures in class recently about these two data structures, in addition to 2-3 and 2-3-4 trees, and I'm not clear on how they differ. From what I can tell, both are binary search trees that are able to balance themselves. I am not sure what, besides color, makes a BST a red/black tree, Is anyone able to help explain the main differences?

Prof stated that a red/black tree is a visual representation of a 2-3-4 tree. I don't get this at all.

 

[Ken g6]

Prof stated that a red/black tree is a visual representation of a 2-3-4 tree. I don't get this at all.

Imagine if each red node of a red/black tree were merged into its parent black node. (As I recall, every red node has a black parent.) Keeping the child nodes in order, you get a 2-3-4 tree.

I don't recall ever learning about AVL trees. My professor was into splay trees.

 

[Danimal1209]

So, what qualifies a node to be a red node? And the same question for black.

 

[Danimal1209]

Nevermind, I figured it out. Thanks though!

 

[wantedSpidy]

You should REALLY watch this particular lecture ->

http://ocw.mit.edu/courses/electric...d-black-trees-rotations-insertions-deletions/

But here is some overview (just so you can be sure abt what you know) ->
1 - All operations on a BST are O(height) - insert, delete, find ..
2 - People incorrectly assume the height of a randomly built BST always going to be O(lg n). However the height is not necessarily going to be asymptotically bound by lg n. For example, if you build a BST by inserting elements in order from a sorted array you will end up with a BST of height n (i.e. all the nodes only have a right child) Fact is, the expected height of a randomly build BST is lg n which is not the same as being asymptotically bound by lg n in the worst case.
3 - Motivation for RB tree (and other self balancing trees) was to have a data structure like BST's that guarantees lg n height which makes the operations in (1) to be done in worst case O (lg n) time!

All these trees achieve their balancing in different ways, and all have their advantages so if you really want to be working at a place like Akamai, then you should have some idea about the advantages of all of them! ;-)