masanar
شنبه 18 مهر 1388, 19:26 عصر
سلام
من یه آرایه دارم که با این آرایه یه درخت Bst ایجاد می کنم و اون درخت رو تو یه آرایه دیگه ذخیره می کنم . واسه اینکه یه Bst رو تو یه آرایه ذخیره کنیم مثلا اگه پدر تو خونه i قرار داره باید فرزند چپش توخونه 2*i و فرزند راستش تو خونه
i*2+1 باشه و از اونجا که این درخت موازنه شده نیست طول آرایه دوم خیلی بیشتر از طول آرایه اول میشه و چون اندیس آرایه فقط می تونه عدد باشه اگه آرایه اولم تعداد عناصرش زیاد باشه ممکنه در ساخت آرایه درخت مشکل ایجاد بشه مثلا وقتی آرایه اولم 800 تا عنصر داشته باشه ارور 'System.OutOfMemoryException' ایجاد میشه :گریه:
البته این ارور طبیعیه چون در بدترین حالت با این 800 تا عنصر ما یه درخت خواهیم داشت که 800 سطح داره و در هر سطحی فقط یه عنصر غیر null یعنی یه درخت که باید 2 به توان 800 منهای یک گره رو براش ذخیره کرد که فقط 800 تا از اونها null نیستن(که این مقدار از محدوده اعداد صحیح خیلی بیشتر میشه) :کف:
حالا سوال من اینه که چطور می تونم با حفظ این ساختار یه درخت خیلی بزرگ رو ذخیره کنم ؟؟؟ :متفکر:
من یه آرایه دارم که با این آرایه یه درخت Bst ایجاد می کنم و اون درخت رو تو یه آرایه دیگه ذخیره می کنم . واسه اینکه یه Bst رو تو یه آرایه ذخیره کنیم مثلا اگه پدر تو خونه i قرار داره باید فرزند چپش توخونه 2*i و فرزند راستش تو خونه
i*2+1 باشه و از اونجا که این درخت موازنه شده نیست طول آرایه دوم خیلی بیشتر از طول آرایه اول میشه و چون اندیس آرایه فقط می تونه عدد باشه اگه آرایه اولم تعداد عناصرش زیاد باشه ممکنه در ساخت آرایه درخت مشکل ایجاد بشه مثلا وقتی آرایه اولم 800 تا عنصر داشته باشه ارور 'System.OutOfMemoryException' ایجاد میشه :گریه:
البته این ارور طبیعیه چون در بدترین حالت با این 800 تا عنصر ما یه درخت خواهیم داشت که 800 سطح داره و در هر سطحی فقط یه عنصر غیر null یعنی یه درخت که باید 2 به توان 800 منهای یک گره رو براش ذخیره کرد که فقط 800 تا از اونها null نیستن(که این مقدار از محدوده اعداد صحیح خیلی بیشتر میشه) :کف:
حالا سوال من اینه که چطور می تونم با حفظ این ساختار یه درخت خیلی بزرگ رو ذخیره کنم ؟؟؟ :متفکر: