BD-2st-1.2-w07.tresc-1.1-Slajd35
Wstawianie danych do indeksu - przykład (3)
Wartość 12 musi być wstawiona do skrajnie prawego liścia. Jednak jest on już w całości zajęty. Z tego powodu węzeł jest rozbijany na 2. W tym celu porządkujemy wartości istniejące w węźle i wartość wstawianą, od lewej (najmniejsza) do prawej (największa). Wartość środkową, czyli 8, przenosimy do korzenia. Wartości 7 i 8 trafiają do lewego liścia, a 12 - do prawego, jak pokazano na slajdzie.
Ponadto, w tym przypadku wartość 8 powinna trafić do korzenia, który jest już w całości wypełniony. Z tego względu ulega on rozbiciu na nowy korzeń i dwa węzły wewnętrzne. W tym celu porządkujemy wartości już przechowywane w korzeniu i wstawianą do niego wartość, jak pokazano na slajdzie. Wartość środkowa, czyli 5 trafia do nowego korzenia. Wartość 3 trafia do lewego poddrzewa, a wartość 8 - do prawego, jak pokazano na slajdzie.
