treemap - How tree map uses red black tree algorithm -

i have read many articles on red black tree take o(log n) time operations .i not clear how works , how tree map uses red black tree algorithm balance tree compared binary search tree.

ref links https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-binary-search-and-red-black-trees/

can please explain example how algorithm works.

a red-black tree is binary search tree. it's flavor of bst has fancy versions of insert , delete operations reorganize tree run tree never gets "long , stringy." longer , stringier tree gets, more behaves linked list. on average, linked list operations require half list touched (or whole list in worst case), run time varies linearly (o(n) in number of elements n). when tree "bushy" or balanced, operations cheaper ( o (log n) ) each. red-black algorithms guarantee tree remains bushy.

to make concrete, here 2 trees store keys g. left long , stringy. note how looks list. in worst case, takes 4 key comparisons find element. tree on right bushy. needs 3. here difference small. tree of 1023 elements, stringy tree needs 512 comparisons , bushy 1 10. power of log n.

  b                    _d_  / \                  /   \   d                b     f    / \              / \   / \   c   f              c e   g      / \     e   g 

the red-black tree isn't guaranteed bushy (in correct terminology "perfectly balanced"), red-black rules guarantee it's bushy enough in mathematically strict way operation times vary log of n rather linearly in n.

the red-black rules' genius "local." during insertion or deletion breaks rules, it's possible restore them adjusting constant number of nodes each node touched operation. therefore cheap , easy implement.

yet when red-black rules true whole tree, it's possible show clever mathematical proof it's bushy enough described above.

what tree map? map function domain called key set k , range called value set v. implement tree map, each node stores key-value pair <k,v> k \in k , v \in v. in drawings above (and presentations), keys (letters a-g) shown. in map, insertion, lookup, , deletion work on these pairs in pretty obvious way. example, lookup searches key using usual bst algorithm. when key found, value found because it's in same pair. that's what's returned. in java, pair called map.entry. can check out in java source code.

i won't go details on how red-black rules work because couldn't improve on the wikipedia page. guess , hope missing "big picture" discussion make sense. news languages provide thoroughly tested , performance-optimized tree implementation, knowing arcane details of rotations not necessary. of course, if you're curious , want know, have @ it! congratulations!

for it's worth, top coder explanations of algorithms not clearest. hunt around others until 1 "clicks" you. respected textbooks in cs respected reason: explanations excellent. corman , rivest accepted favorite.