Search code examples
data-structurestreebinary-search-treered-black-tree

Why the Red Black Tree is kept unbalanced after insertion?


Here is a red black tree which seems unbalanced. If this is the case, Someone please explain why it is unbalanced?.


Solution

  • The term "balanced" is a bit ambiguous, since different kinds of balanced trees have different constraints.

    A red-black tree ensures that every path to a leaf has the same number of black nodes, and at least as many black nodes as red nodes. The result is that the longest path is at most twice as long as the shortest path, which is good enough to guarantee O(log N) time for search, insert, and delete operations.

    Most other kinds of balanced trees have tighter balancing constraints. An AVL tree, for example, ensures that the lengths of the longest paths on either side of every node differ by at most 1. This is more than you need, and that has costs -- inserting or deleting in an AVL tree (after finding the target node) takes O(log N) operations on average, while inserting or deleting in a red-black tree takes O(1) operations on average.

    If you wanted to keep a tree completely balanced, so that you had the same number of descendents on either side of every node, +/- 1, it would be very expensive -- insert and delete operations would take O(N) time.