Solutions to exercises and problems from "Introduction to Algorithms", Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (in Polish)
(b) podpis pod rysunkiem: "W przypadku „lewo-prawo” po przyjęciu, że wysokością \delta jest h, mamy, że" -> "Przypadek ,,lewo-prawo''. Jeśli wysokością \delta jest h, to"
Przepisać całe rozwiązanie. Rezygnujemy ze wskaźników do ojca, ale stosujemy węzeł wartownik nil z polem h=0. Opisać uproszczone w porównaniu z obecną wersją operacje Balance-Factor, Height i rotacje zwracające węzeł, który stał się ojcem x. Czy rysunki trzeba poprawić w związku ze zmienioną implementacją?
(c) Zmienić nazwę procedury na AVL-Subtree-Insert. Zmienić nazwę procedury AVL-Insert-Wrapper na AVL-Insert. Dopisać odpowiednie uzasadnienie.
"Podobnie ..." -> "Podobnie jak w przypadku Recursive-Tree-Insert, powyższa procedura powinna być wywoływana wyłącznie przez następujący pseudokod, który dodatkowo aktualizuje pole root drzewa T, do którego wstawiany jest węzeł z."
(d) notka: "czego" -> "którego"
"dla drzewa" -> "wywołana dla drzewa"
"sumaryczna ... 2" -> "sumarycznie w trakcie działania AVL-Insert zostaną przeprowadzone nie więcej niż 2 rotacje"
uprościć opis przypadków, w końcu sam rysunek i podpis pod nim uzasadnia już, że rotacje zostawiają zrównoważone poddrzewa, zostawić jedynie uzasadnienie wysokości tych poddrzew
(b) podpis pod rysunkiem: "W przypadku „lewo-prawo” po przyjęciu, że wysokością \delta jest h, mamy, że" -> "Przypadek ,,lewo-prawo''. Jeśli wysokością \delta jest h, to" Przepisać całe rozwiązanie. Rezygnujemy ze wskaźników do ojca, ale stosujemy węzeł wartownik nil z polem h=0. Opisać uproszczone w porównaniu z obecną wersją operacje Balance-Factor, Height i rotacje zwracające węzeł, który stał się ojcem x. Czy rysunki trzeba poprawić w związku ze zmienioną implementacją? (c) Zmienić nazwę procedury na AVL-Subtree-Insert. Zmienić nazwę procedury AVL-Insert-Wrapper na AVL-Insert. Dopisać odpowiednie uzasadnienie. "Podobnie ..." -> "Podobnie jak w przypadku Recursive-Tree-Insert, powyższa procedura powinna być wywoływana wyłącznie przez następujący pseudokod, który dodatkowo aktualizuje pole root drzewa T, do którego wstawiany jest węzeł z." (d) notka: "czego" -> "którego" "dla drzewa" -> "wywołana dla drzewa" "sumaryczna ... 2" -> "sumarycznie w trakcie działania AVL-Insert zostaną przeprowadzone nie więcej niż 2 rotacje" uprościć opis przypadków, w końcu sam rysunek i podpis pod nim uzasadnia już, że rotacje zostawiają zrównoważone poddrzewa, zostawić jedynie uzasadnienie wysokości tych poddrzew