البحث اغية الأولى في شجرة ثنائية مع ذاكرة محدودة

Question

ولدي شجرة ثنائية حيث كل عقدة يمكن أن يكون لها قيمة.

وأريد أن أجد عقدة في الشجرة التي لها قيمة لاغية والأقرب إلى الجذر. إذا كان هناك عقدتين مع نفس المسافة من جذورها، سواء ستفعل. ولست بحاجة إلى تقليل عدد قراءة يصل إلى شجرة ثنائية. نفترض أن الذاكرة العاملة يقتصر على العقد ك فقط.

وDFS إلى عمق k غير كامل إلا أنه لن تجد أقرب عقدة ما لم يتم تشغيل من خلال الشجرة كلها أولا. سوف BFS العثور على الأقرب، لكنها قد تفشل بسبب DFS أن تجد بلا قيم أعمق مع نفس الذاكرة.

وكنت ترغب في الحصول على أقل عدد من القراءة يصل إلى شجرة لمعرفة أقرب عقدة فارغة.

و(أنا بحاجة لتنفيذ ذلك في أشجار ن الطريق في نهاية المطاف، أيضا، لذلك الحل العام سيكون جيدا. لا حق الكتابة إلى شجرة، وقراءة فقط).

Answer 1

وأنت قد ترغب في النظر في التكرارية-تعميق متعمقة أول بحث . وسوف تجد أقرب العقدة تلقائيا ولكن سوف تكون قادرة على الوصول إلى نفس العمق كما DFS. وسوف تستخدم أكثر قراءة يصل بالرغم من ذلك.

هل يمكن أن تبدأ أيضا مع BFS، وإذا كنت لا تجد فارغة مع الذاكرة يسمح بتشغيل DFS.

Answer 2

وأود أن تنفيذ DFS مع تقليم شجرة بسيطة. لذا، فإنه ليس صحيحا أن لديك لتشغيل الشجرة كلها.

على سبيل المثال إذا كنت قد تقع على قيمة فارغة في أوج ساعة، يمكنك <م> تخطي العقد التي هي في نفس أو أعمق الموقف.

Answer 3

إذا كنت لا تستطيع تغيير بنية البيانات ثم سيكون لديك لقراءة كل عقدة - الاتساع اولا

إذا يمكنك تغيير هيكل البيانات، ثم كل عقدة يمكن ان يسجل عمق نسبي من أول عقدة تابعة لاغية. (كل العمل بها من القيم تعادل أبنائها).

وبعد ذلك يمكنك أن تعرف أي خط في شجرة لملاحقة عندما تبحث عن أقرب فارغة.

Answer 4

وهناك طريقة بسيطة، إذا كنت على استعداد لتخزين شجرة الخاص بك في صفيف. بدلا من كل عقدة وجود مؤشرات إلى الأطفال الأيمن والأيسر لها، والأطفال من عقدة ن هم 2N + 1 و2N + 2 في المصفوفة. (الأم والعقدة ن هو (ن 1) / 2، إذا كان n! = 0).

Node tree[] = { 0, //root
1, // root's left child
2, // root's right child
3, // 1's left child
4, // 1's right child
5, // 2's left child
6, // 2's right child
...,
};

وببساطة بالتكرار عبر مجموعة غير خطيا يعادل BFS، ولكن مع متطلبات المساحة من O (1).

ويمكن بسهولة أن تمتد هذه الأشجار ن آرى. على سبيل المثال، في شجرة الثلاثي، والطفل الأيسر 3N + 1، المركز 3N + 2، هو حق 3N + 3، والأصل هو (ن 1) / 3 إذا كان n! = 0.