- Add implementation notes for RtlSplayTree Modified: trunk/reactos/lib/rtl/splaytree.c _____
Modified: trunk/reactos/lib/rtl/splaytree.c --- trunk/reactos/lib/rtl/splaytree.c 2005-11-08 22:25:29 UTC (rev 19070) +++ trunk/reactos/lib/rtl/splaytree.c 2005-11-08 22:45:45 UTC (rev 19071) @@ -73,10 +73,42 @@
*/ PRTL_SPLAY_LINKS NTAPI -RtlSplay ( - PRTL_SPLAY_LINKS Links - ) +RtlSplay(PRTL_SPLAY_LINKS Links) { + /* + * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree): + * + * To do a splay, we carry out a sequence of rotations, + * each of which moves the target node N closer to the root. + * + * Each particular step depends on only two factors: + * - Whether N is the left or right child of its parent node, P, + * - Whether P is the left or right child of its parent, G (for grandparent node). + * + * Thus, there are four cases: + * - Case 1: N is the left child of P and P is the left child of G. + * In this case we perform a double right rotation, so that + * P becomes N's right child, and G becomes P's right child. + * + * - Case 2: N is the right child of P and P is the right child of G. + * In this case we perform a double left rotation, so that + * P becomes N's left child, and G becomes P's left child. + * + * - Case 3: N is the left child of P and P is the right child of G. + * In this case we perform a rotation so that + * G becomes N's left child, and P becomes N's right child. + * + * - Case 4: N is the right child of P and P is the left child of G. + * In this case we perform a rotation so that + * P becomes N's left child, and G becomes N's right child. + * + * Finally, if N doesn't have a grandparent node, we simply perform a + * left or right rotation to move it to the root. + * + * By performing a splay on the node of interest after every operation, + * we keep recently accessed nodes near the root and keep the tree + * roughly balanced, so that we achieve the desired amortized time bounds. + */ UNIMPLEMENTED; return 0; }