21. 3. 2023
Prohazujeme rodiče s jeho právým potomkem. V novém stromu bude původní rodič nalevo od kořene. Levý podstrom potomku příjde nově jako pravý podstrom původního kořene.
Prohazujeme rodiče s jeho levým potomkem. V novém stromu bude původní rodič napravo od kořene. Pravý podstrom potom příjde nově jako levý podstrom původního kořene.
Do stukruty node přidáme další položku a to count (int), kde si budeme pamatovat počet vrcholů v podstromu, které má tento vrchol. Pokud je potomek vrcholu nil, pak count tohoto potomku bude 0.
x.count = x.left.count + x.right.count + 1
Kvůli této změně musíme upravit funkce tree-insert, tree-delete a rotate-R i rotate-L.
Umožňují nám najít k-tý nejmenší klíč v binárním vyhledávacím stromu.
select (r:node, k:int):
if r.left == nil:
t = 0
else:
t = r.left.count
if t > k - 1:
return select(r.left, k)
if t < k - 1:
return select(r.right, k - t - 1)
else:
return r
K vrcholu x nalezneme k tak, že x je k-tá pořádková statistika.
rank(r:node, x:node):
if x.left == nil:
t = 1
else:
t = 1 + x.left.count
y = x
while y!=r
if y == y.parent.right:
if y.parent.left == nil:
t = t + 1
else:
t = t + y.parent.left.count + 1
y = y.parent
return t
root-insert(r:node, added:node):
if r == nil:
return added
if added.key < r.key:
r.left = root-insert(r.left, added)
r.left.parent = r
else:
r.right = root-insert(r.right, added)
r.right.parent = r
return r
partition(r:node, k:int):
if r.left == nil:
t = 0
else:
t = r.left.count
if t == k - 1:
return r
if t > k - 1:
r.left = partition(r.left, k)
r.left.parent = r
return rotate-R(r)
else:
r.right = partition(r.right, k - t - 1)
r.right.parent = r
return rotate-L(r)
Pomocí in-order-walk umožníme vrcholy do pole uspořádány podle klíčů. Potom pomocí insert vytvoříme strom minimální výšky.
Nebo využijeme partition a s jeho pomocí umístíme medián do kořene. Potom rekurzivně provedeme totéž pro levý a pravý podstrom.
balance(r:node):
if r == nil or r.count <= 2:
return r
ret = partition(r, floor(r.count / 2) + 1)
ret.left = balance(ret.left)
ret.right = balance(ret.right)
return ret
je varianta binárního vyhledávacího stormu, kdy vyváženost každého vrcholu v něm je rovna 1, 0 nebo -1. Vyváženost vrcholu x je rozdíl výšky levého podstromu a výšky pravého podstromu vrcholu x. Výšku prázdného podstromu definujeme rovnu -1.
Kvůli této změně budeme muset provést změny ve funkcích pro insert a delete oproti klasického binárnímu vyhledávacímu stromu. Do struktury si přidáme další položku pro uchovávání vyváženosti vrcholu (bf). Musíme tedy po každé změně projít strom od změny ke kořeni a opravit složky bf a případný problém vyřešit. Vždy změna v bf může být maximálně o 1, takže nepovolené hodnoty, které musíme řešit jsou 2 a -2.