tp_traverse is completely orthogonal to tp_dealloc, it's needed to detect (and then break) reference cycles like:
    obj = xxlimited.Xxo()
    obj.foo = obj

As for tp_finalize: yes, mentioning it in tp_dealloc docs would be good, but I'll need a bit more studying to understand the problem correctly. The cases fixed here are relatively simple; Antoine gives more complex ones in [0]. When I feel qualified to give advice, I'll change the docs. (And most likely, write a PEP to make things easier; some changes to classes will be needed anyway to make PEP 489 multi-phase init work nicely in all cases).
But, I plan to focus my CPython time on documenting PEP 489 before diving in here. I think issue 16690 is a good place to track tp_dealloc docs changes.

[0] https://mail.python.org/pipermail/python-dev/2015-June/140423.html