Binary search tree & wijzigen van node met niet unieke key

[SideShow]

Hallo

Ik ben bezig met een custom (single user/single threaded) document databaseje, om van te leren.
Hierbij een probleem ivm binary search trees.

Ik wil een BST index maken van een bepaald veld op een class/document. (Voorlopig natuurlijk enkel primitives, ook geen strings.) Mijn huidige tree kan nodes bevatten met dezelfde key, waarbij deze steeds als right child gezet worden.

Nu is de vraag: als ik twee nodes heb, die beide het nummer 789 als key hebben, hoe kan ik dan weten welke node verwijst naar het document die ik daadwerkelijk heb aangepast en wens te bewaren? Node values scannen lijkt me een beetje tegennatuurlijk in dit verhaal. Ik dacht aan een omgekeerde tree, waarbij je dan dus als key een referentie hebt naar het document, en als value een referentie naar de node in de originele BST index.

Klopt deze redenering, of is dit gewoon volledig not done?
Enige raad is welkom.

[sam.vimes]

Als ik je probleem goed heb begrepen, kun je met binair zoeken snel bij de eerste key 789 komen. Daarna steeds het rechter child nemen voor de volgende nodes met key 789. Omdat de key niet uniek is, zul je toch elke node met die key moeten testen om te zien of het wel de gewenste node is.

[HMS]

Je zou ook op een node de value kunnen bijhouden (in dit geval 789), en dan een verwijzing (pointer / reference) naar de documenten die daar aan voldoen in de node opslaan. Zo kan je snel zoeken (O(n log n)) en je hoeft geen rare truukjes uit te halen met rechter nodes.

En je weet toch wel de Primary Key (die heb je toch wel? met unique constraints?) van het document dat aangepast is? Dan kan je aan de hand van de reference in de node je index updaten.

[SideShow]

Dat zal het inderdaad ongeveer zijn. Dank !