|
|
back to boardset_class in C++ (1439 ) Posted by svr 25 Nov 2006 22:14 In seems that in C++ for set-object no operator for standard container inquiry : N-tn element, with log N complexity, but should be. With such operator problem 1439 would be very simple. In reality was necessary to program my own set class based on red-black trees. And N-th element to realize was very simple(hard work was balancing). It,s not well that tree-structures of standard containers are hidden for uses in C++. Can u just explain me, please (+) Posted by Donat 19 Apr 2007 11:19 What did you store in red-black tree? I've tried 4 self-invented algorithms and no of them Accepted (MLE, TLE most common). Re: Can u just explain me, please (+) Posted by svr 19 Apr 2007 19:42 In standard container's descriptions operation take_N-th_element with O(log N) complexity presence but in Microsoft Visual C++ dosn't. Using Cormen's book I build myself red-black tree -type with last additional operation. My structure stores: left, right,father, color for each node- this is standard, but additional I support(this means O(log N) renewing in each operation) new characteristics: number of sublines for each node- or subtree nodes count. Using this charactiristics and binary search It's not difficalt to build "take_N-th_element" with O(log N) complexity . Edited by author 19.04.2007 19:43 Re: Can u just explain me, please (+) |
|
|