You could make a "ternari" tee, using your proposition: each node has tits index value, and THREE pointers: GreaterThan, LesserThan (as the original binary tree does) and ... Equal.
The original binary tree has its records in its leafs, the nodes are merely there for organizing/traversing the data. This part is left intact, but you change the leaves.
If your "search" yealds a "record found" signal, that is: you found your "Smith" node, then all Smith records are in a subtree of this node.
Say, you are a phone company, not having 12 nodes named Smith, but 1200, then your subtree is a new binary/ternary tree, containing all Smith records, sorted by a key that can discriminate between them.
So you binary-search until you hit "TheRightKey", then see it isn't unique, so you search within the "equals" subtree.
As long as you did NOT hit the top-level "ThisNode", you have BinarySearch1, looking for Smith. After you found "Smith", you'll be searching for John (search2, confined to the subtree), when John isn't unique either, search for other data.
Do you have records in your database that are ENTIRELY IDENTICAL? Then re-read J.C. Date's book on Databases and SQL, or look for something explaining "database normalisation" and "relational databases".
Having IDENTICAL RECORDS, as in indistinguishably identical, is of no use for you: you either added the same client/article/order/employee twice (no use for that), OR you forgot to define/fill-in a crucial field: the one that lets you give a raise to John-Smith-the-mailman, without upsetting John-Smith-the-vice-president. The former will be surprised , the latter really mad if their pacheck turns out the same. |
