فعل الوندوز الان بارخص الاسعار

فعل الوندوز الان بارخص الاسعار
فقط ب30 ريال مدى الحياة

setoolkit اداة الهندسة الاجتماعية والأختراق

0

 


setoolkit هي اداة خبيثة تستخدم لعمليات الهندسة الاجتماعية والتصيد والاختراق هذه الاداة تسمح للمخترق بالوصول الى معلومات الضحية ( اسم المستخدم وكلمة المرور) لاي من مواقع التواصل الاجتماعي بالتعاون بشكل طوعي من قبل  الضحية ! حيث تقدم هذه الاداة خيارات متعددة للمخترق باختيار اي قالب لاي موقع تواصل اجتماعي 

كيف تعمل هذه الاداة ؟ 

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


كيف تتم عملية التصيد ؟ 

نلاحظ في الصورة التالية للصفحة الوهمية وواجهة تسجيل الدخول لاحد مواقع التواصل الاجتماعي ، من خلالها تقوم الضحية بتسجيل معلومات تسجيل الدخول - ولكن هل لاحظت اي اختلاف عن المنصة الرسمية ؟ في حال لم تلاحظ ذلك بعد  نود لفت انتباهك الى رابط الصفحة ، احسنت ننصحك دائما التحقق من اي رابط يصلك قبل تسجيل دخولك لاي موقع رسمي . 


في الطرف الاخر كيف يتمكن المخترق من الاستفادة من المعلومات المدخلة ؟ 

عموما في مجال الامن السيبراني والاختراق الادوات متطورة بشكل كبير فكل ما يحتاجه المخترق ضغطة زر من الضحية لاحظ الصورة التالية تحديدا المربع المعلم بالاحمر 


الان جميع معلومات الضحية تحت رحمة المخترق ، !!! وفي هذا المثال خاطرنا و استخدمنا معلومات حسابنا على تويتر وفي حال لم تلحظ ذلك  نوذ لفت انتباهك الى كلمة المرور ، مع قبلاتنا وتمنياتنا لك بالتوفيق في رحلتك السبرانية

عوما ما اللذي يحديث الان للضحية ؟ بعد ارساله لمعلومات تسجيل الدخول الى المخترق بسبب خطأ بسيط وهو عدم تحققه من رابط الموقع  من المتوقع مالذي سيحدث له ولكن لا نقصد ذلك - ولكن هنا نقصد مالذي حدث بعد ضغطه على ايقونة تسجيل الدخول 

قامت الاداة بشكل خبيث بتحويله بشكل مباشر الى الصفحة الرسمية للمنصة وبالتالي من المؤكد ان الضحية لن تلفت انتباهه هذا الاجراء فالعنوان اعلى الصفحة حقيقي وآمن ونلاحظ الذكاء والخبث في برمجة هذه الاداه ، وللمعلومية عمليات التصيد والهندسة الاجتماعية تعتبر من انجح عمليات الاختراق لانها بشكل عام تعتمد على وعي الضحية وحالته وقس على ذلك العمليات التي تعتمد على مشاعر الاخرين والتلاعب بها لهدف معين ، وليس فقط في مجال الاختراقات الالكترونية فقط فأي عملية تعتمد على التلاعب بالضحية تعتبر هندسة اجتماعية ! 

شكرا لك على وقتك الثمين 

انتهت التدوينه . 




للمتخصصين في مجال الامن السيبراني وامن المعلومات في ما يلي المعلومات والخطوات المفصلة للأداة : 

المتطلبات : نظام لينكس - يفضل استخدامه كنظام وهمي 

VM -برنامج محاكي لتشغيل الانظمة 















برنامج جافا لحذف node من شجرة بحث ثنائية.

0



 import java.util.*;

class BinaryTree {

int data;

BinaryTree left, right;

BinaryTree(int x) {

this.left=this.right=null; data=x;

}

public void insert( int i ) {

if (i <= data) {

if (left != null) left.insert(i);

else left = new BinaryTree( i );

}

else if (i >= data) {

if (right != null) right.insert(i);

else right = new BinaryTree( i );

}

}

public void inOrder(BinaryTree tree) {

if(tree!=null) {

inOrder(tree.left);

System.out.print(tree.data+" ");

inOrder(tree.right); }

}

public static int min(BinaryTree node) {

if (node.left == null) {

return node.data;

}

return min(node.left);

}

public static BinaryTree deleteNodeInBST(BinaryTree node, int data) {

if (null == node) {

System.out.println("Element is not in binary search tree");

return null;

}

if (data < node.data) {

node.left = deleteNodeInBST(node.left, data);

} else if (data > node.data) {

node.right = deleteNodeInBST(node.right, data);

} else { // case for equality

// Now we see that whether we can directly delete the node

if (node.left != null && node.right != null) {

int minInRightSubTree = min(node.right);

node.data = minInRightSubTree;

node.right = deleteNodeInBST(node.right, minInRightSubTree);

} else { // either one child or leaf node

if (node.left == null && node.right == null) {

node = null;

} else {// one child case

BinaryTree deleteNode = node;

node = (node.left != null) ? (node.left) : (node.right);

deleteNode = null;

}

}

}

return node;

}

public static void main (String args[]) {

char choice='y'; int n, d;

Scanner sc = new Scanner(System.in);

System.out.print("Enter Root node value = ");

n=sc.nextInt();

System.out.print("Enter ur Choice(y/n) = ");

choice=sc.next().charAt(0); BinaryTree ob=new BinaryTree(n);

while (choice == 'y') {

System.out.print("Enter node value = ");

n=sc.nextInt(); ob.insert(n);

System.out.print("Enter ur Choice(y/n) = ");

choice=sc.next().charAt(0);

}

System.out.print("\nInorder Traversal = "); ob.inOrder(ob);

System.out.print("\nEnter the Node to delete = ");

d = sc.nextInt(); ob.deleteNodeInBST(ob, d);

System.out.print("\n After deleting the Node "+d+" = "); ob.inOrder(ob);

}

}



Output:

Inorder Traversal = 2 10 16 50 110

Enter the Node to delete = 16

After deleting the Node 16 = 2 10 50 110

برنامج جافا لتنفيذ اجتياز INORDER و PREORDER و POSTORDER لشجرة بحث ثنائية.

0


class Node

{

int key;

Node left, right;

public Node(int item)

{

key = item;

left = right = null;

}

}

public class BinaryTree1

{

Node root;

BinaryTree1()

{

root = null;

}

void printPostorder(Node node)

{

if (node == null)

return;

printPostorder(node.left);

printPostorder(node.right);

System.out.print(node.key + " ");

}

void printInorder(Node node)

{

if (node == null)

return;

printInorder(node.left);

System.out.print(node.key + " ");

printInorder(node.right);

}

public void printPreorder(Node node)

{

if (node == null)

return;

System.out.print(node.key + " ");

printPreorder(node.left);

printPreorder(node.right);

}

void printPostorder() { printPostorder(root); }

void printInorder() { printInorder(root); }

void printPreorder() { printPreorder(root); }

public static void main(String[] args)

{

BinaryTree1 tree = new BinaryTree1();

tree.root = new Node(1);

tree.root.left = new Node(2);

tree.root.right = new Node(3);

tree.root.left.left = new Node(4);

tree.root.left.right = new Node(5);

System.out.println("Preorder traversal of binary tree is ");

tree.printPreorder();

System.out.println("\nInorder traversal of binary tree is ");

tree.printInorder();

System.out.println("\nPostorder traversal of binary tree is ");

tree.printPostorder();

}

}




Output

Preorder traversal of binary tree is

1 2 4 5 3

Inorder traversal of binary tree is

4 2 5 1 3

Postorder traversal of binary tree is

4 5 2 3 1 

الخوارزميات وهياكل البيانات: اشجار البيانات الثنائية binary trees

0

 الأشجار

إنه رسم بياني متصل غير دوري حيث تحتوي كل عقدة على 7 = 0 أو أكثر من العقد الفرعية وعقدة رئيسية واحدة على الأكثر. العقدة عبارة عن هيكل يحتوي على قيمة وعناوين من اليمين واليسار و child. تحتوي كل عقدة في الشجرة على صفر أو أكثر من العقد الفرعية الموجودة تحتها في الشجرة. العقدة التي لديها child تسمى العقدة child's parent . تحتوي العقدة على parent واحد على الأكثر.  العقدة الداخلية هي أي عقدة في شجرة تحتوي على عقد فرعية. وبالمثل ، فإن العقدة الخارجية (تُعرف أيضًا باسم العقدة الخارجية أو العقدة الطرفية ) ، هي أي عقدة لا تحتوي على عقد فرعية. تسمى العقدة العلوية في الشجرة عقدة الجذر. أمثلة على انواع اشجار البيانات

ملاحظة من المترجم - يصعب احيانا الترجمة الحرفية لعبض المصطلحات ولكن رأس الشجرة يسمى parent والافرع المندرجة تحته تسمى children وnodes اطلقت عليها في المقالة عقد

ملاحظة 2 : سميت بالشجرة لان تفرع البيانات في هيكلة البيانات هذه ياخذ شكل التفرع الشجري 


يمكن تعريف الشجرة بشكل متكرر على النحو التالي:

1. الهيكل الفارغ هو شجرة فارغة 

2. إذا كانت t1 ، t2 ، ... ، tk عبارة عن أشجار مفككة ، فإن البنية التي يكون لجذرها أطفال

إذا كانت t1 ، t2 ، ... ، tk عبارة عن أشجار مفككة ، فإن البنية التي يكون لجذرها children  t1 ، t2 ، ... ، tk هي أيضًا شجرة

ويرمز للشجرة ب t متبوعة بعدد اذا كان يوجد لدينا اكثر من شجرة للتحديدها كما في الصورة السابقة

3. فقط الهياكل التي تم إنشاؤها بواسطة القاعدتين 1 و 2 هي الأشجار.

المسار: يجب أن تكون كل عقدة قابلة للوصول من الجذر من خلال سلسلة فريدة من الأقواس.

طول المسار: عدد الأقواس في المسار.

المستوى: مستوى العقدة هو طول المسار من الجذر إلى العقدة زائد 1 ، وهو عدد العقد في المسار.

الارتفاع: هو الحد الأقصى لمستوى العقدة في الشجرة.


بناء ع الصورة السابقة 

الارتفاع = المستوى الأقصى = 4

طول المسار = 3

المستوى = 3 + 1 = 4

هذه لا تعتبر شجرة بيانات


يوجد مسار فريد بين أي عقدتين في الشجرة. الشجرة ليس لها دورات. بمعنى لا تاخذ شكل حلقي كما في الصورة السابقة نلاحظ انها تاخذ شكل حلقي 

ضع في اعتبارك قائمة مرتبطة بالعناصر n. لتحديد موقع عنصر ، يجب أن يبدأ البحث من بداية القائمة ويجب فحص القائمة حتى يتم العثور على العنصر أو الوصول إلى نهاية القائمة. (أفضل حالة: O (1) ، أسوأ حالة: O (n))

الشجرة المنظمة
شجرة منظمة: شجرة يتم فيها تخزين جميع العناصر وفقًا لبعض معايير الترتيب المحددة مسبقًا ، إذا تم تخزين جميع العناصر في شجرة منظمة ، فيمكن تقليل عدد الاختبارات.


الأشجار الثنائية

الشجرة الثنائية هي بنية بيانات شجرية تحتوي كل عقدة فيها على عقدتين فرعيتين على الأكثر ، وعادة ما يتم تمييزهما على أنهما "يسار" و "يمين".


جرة ثنائية كاملة: وهي شجرة ثنائية تحتوي على جميع العقد nodes على جميع المستويات باستثناء اخرها يكون فيها 2children . تحتوي جميع العقد غير الطرفية علىchildrens ، وجميع الأوراق تكون في نفس المستوى.

سيكون هناك 20 عقدة في المستوى 1 (الجذر) ، و 21 عقدة في المستوى 2 ، وبشكل عام ، 2i في المستوى i + 1.

شجرة القرار: هي شجرة ثنائية تحتوي فيها جميع العقد على صفر أو فرعين غير فارغين.


شجرة البحث الثنائية (BST)

إنها بنية بيانات شجرة ثنائية لها الخصائص التالية:

• لا يكتسب الذنب الأيسر للعقدة سوى العقد ذات المفاتيح الأقل من مفتاح العقدة. • الشجرة الفرعية اليمنى للعقدة تحتوي فقط على عقد ذات مفاتيح أكبر من مفتاح العقدة. • يجب أن تكون كل من الأشجار الفرعية اليمنى واليسرى عبارة عن أشجار بحث ثنائية.


قم بإنشاء شجرة بحث ثنائية (BST) ، مع إعطاء التسلسل التالي : 

100، 90، 110، 80، 95، 120، 50، 130، 65، 150، 165، 25، 45، 60، 145 التسلسل العنصر الأول في التسلسل = جذر BST

إنها بنية بيانات شجرة ثنائية لها الخصائص التالية:

• الشجرة الفرعية اليسرى للعقدة تحتوي فقط على عقد ذات مفاتيح أقل من مفتاح العقدة. • الشجرة الفرعية اليمنى للعقدة تحتوي فقط على عقد ذات مفاتيح أكبر من مفتاح العقدة. • يجب أن تكون كل من الأشجار الفرعية اليمنى واليسرى عبارة عن أشجار بحث ثنائية.


 شجرة البحث الثنائية بشكل عام 

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



public class IntBSTNode {

 protected int key; 

protected IntBSTNode left, right;

 public IntBSTNode() {

 left = right = null; 

}

public IntBSTNode(int el) {

 this(el,null,null); 

}

public IntBSTNode(int el, IntBSTNode lt, IntBSTNode rt) {

 key = el; left = It; right - rt; 

}

 public void visit() {

 System.out.print(key + " "); 

}

}


لكل عقدة ، قارن المفتاح الذي سيتم تحديد موقعه بالقيمة المخزنة في العقدة المشار إليها حاليًا.

المفتاح أقل من القيمة ، انتقل إذا إلى الشجرة الفرعية اليسرى وحاول مرة أخرى.

إذا كانت أكبر من تلك القيمة ، فجرب الشجرة الفرعية الصحيحة.

إذا كان هو نفسه يمكن إيقاف البحث.

يمكن إلغاء البحث ، إذا لم يكن هناك طريق للذهاب ، يعني أن المفتاح ليس في الشجرة


دالة البحث في شجرة البحث الثنائية:

















يقاس مدى تعقيد البحث بعدد المقارنات التي أجريت أثناء عملية البحث.
يعتمد هذا الرقم على عدد العقد التي تمت مواجهتها على المسار الفريد المؤدي من الجذر إلى العقدة التي يتم البحث عنها.
التعقيد هو طول المسار المؤدي إلى هذه العقدة زائد 1.
يعتمد ذلك على شكل الشجرة وموضع العقدة في الشجرة.
تحتوي الشجرة على العقد من 1 إلى n. إذا كان i هو الجذر ، فإن شجرته الفرعية اليسرى بها عقد i ‐ 1 ، وشجرته الفرعية اليمنى بها عقد n ‐ i. إذا كان المسار ‐ 1 والمسار n ‐ i هما مساران متوسطان في هذه الأشجار الفرعية ، فإن متوسط مسار هذه الشجرة هو:


يمكن أن يكون جذر الشجرة أي رقم i ، 1 <= i <= n لذلك ، يتم الحصول على متوسط مسار الشجرة المتوسطة عن طريق حساب متوسط جميع قيم المسار n (i) على جميع قيم i.
اجتياز الشجرة

اجتياز الشجرة هو عملية زيارة كل عقدة في الشجرة مرة واحدة بالضبط.
اتساع ، أول اجتياز .BREADTH‐FIRST TRAVERSAL.
اتساع - أول اجتياز هو زيارة كل عقدة بدءاً من الجذر والانتقال إلى أسفل مستوى بمستوى ، وزيارة العقد على كل مستوى من اليسار إلى اليمين.

 
تسلسل اجتياز النطاق الأول:

13 ، 10 ، 25 ، 2 ، 12 ، 20 ، 31 ، 29


تنفيذ اتساع ‐ اجتياز الأول
يكون واضحًا تمامًا عند استخدام قائمة انتظار.
بعد زيارة العقدة ، يتم وضع عناصرها الفرعية ، إن وجدت ، في نهاية قائمة الانتظار ، وتتم زيارة العقدة الموجودة في بداية قائمة الانتظار.
ملاحظة: enqueue تعني إدراج عنصر في قائمة الانتظار dequeue يعني حذف عنصر من قائمة الانتظار


عمق الترحيل الأولي DEPTH‐FIRST TRAVERSAL. 
يتقدم قدر الإمكان إلى اليسار (أو اليمين) ، ثم يعود لأعلى حتى أول مفترق طرق ، ويذهب خطوة واحدة إلى اليمين (أو اليسار) ، ومرة أخرى قدر الإمكان إلى اليسار (أو اليمين). كرر هذه العملية حتى تتم زيارة جميع العقد.
هناك ثلاث مهام مهمة في هذا النوع من الاجتياز:
V: زيارة العقدة
L: اجتياز الشجرة الفرعية اليسرى
R: اجتياز الشجرة الفرعية اليمنى
يحدث الاجتياز المنظم إذا تم تنفيذ هذه المهام بنفس الترتيب لكل عقدة. إذن ، هناك ست عمليات اجتياز محتملة:
VLR ، VRL ، LVR ، RVL ، LRV ، RLV

VLR: 13,10,2,12,25,20,31,29
VRL: 13 25,31,29,20,10,12,2
LVR: 2,10,12,13,20,25,29,31
RVL: 31,29,25,20,13,12,10,2
LRV: 2,12,10,20,29,31,25,13
RLV: 29,31,20,25,12,2,10,13

افترض أن الحركة دائمًا من اليسار إلى اليمين ، إذن هناك ثلاث عمليات اجتياز قياسية:
VLR: اجتياز الشجرة (الثنائي) للطلب المسبق
LVR: اجتياز الشجرة في الترتيب
LRV: اجتياز الشجرة بعد الطلب


الإدراج
 إذا كانت قيمة العنصر الجديد مساوية لقيمة العقدة الحالية ، فلا تقم بأي إجراء.
 إذا كانت قيمة العنصر الجديد أقل من قيمة العقدة الحالية ، فانتقل إلى الشجرة الفرعية اليسرى (child الأيسر) للعقدة. إذا كانت القيمة خالية ، فقم بإدراج العقدة child أيسر للـ parent .
 إذا كانت قيمة العنصر الجديد أكبر من قيمة العقدة الحالية ، فانتقل إلى الشجرة الفرعية اليمنى (child الأيمن) للعقدة. إذا كانت القيمة خالية ، فقم بإدراج العقدة child أيسر للparent.



الحذف :
هناك ثلاث حالات يجب أخذها في الاعتبار أثناء حذف عقدة من BST: • العقدة الطرفية: تم تعيين المرجع المناسب للعقدة parent على "فارغ" والمساحة التي تشغلها العقدة المحذوفة يطالب بها جامع البيانات المهملة لاحقًا

عقدة بها child واحد: تتم إعادة تعيين مرجع الأصل إلى العقدة للإشارة إلى فرع العقدة. يتم رفع child العقدة بمقدار مستوى واحد
عقدة بها 2children: في هذه الحالة ، لا يمكن إجراء عملية من خطوة واحدة لأن المؤشر الأيمن أو الأيسر للparent’s لا يمكن أن يشير إلى كلا 2children في نفس الوقت. لذلك يمكن القيام بذلك عن طريق الحذف عن طريق الدمج أو الحذف عن طريق النسخ

الحذف عن طريق الدمج
• يتكون جذر الشجرة الفرعية اليسرى كجذر الشجرة
• يتكون جذر الشجرة الفرعية اليمنى كجذر الشجرة
الحذف عن طريق النسخ
• انسخ مفتاح الحد الأدنى في الشجرة الفرعية اليمنى لـ x إلى العقدة x ، ثم احذف العقدة باستخدام هذا المفتاح الأدنى

انسخ مفتاح الحد الأقصى في الشجرة الفرعية اليسرى لـ x إلى العقدة x ، ثم احذف العقدة باستخدام هذا المفتاح الأقصى.


تحليل التعقيد - شجرة ثنائية:
• البحث: للبحث عن عنصر 2 ، علينا اجتياز جميع العناصر (بافتراض أننا نقوم باجتياز النطاق الأول). لذلك ، فإن البحث في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (n).
• الإدراج: لإدراج العنصر كـchild أيسر لـ 2 ، علينا اجتياز جميع العناصر. لذلك ، فإن الإدراج في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (n).
• الحذف: لحذف العنصر 2 ، علينا اجتياز جميع العناصر للعثور على 2 (بافتراض أننا نقوم بعملية اجتياز العرض أولاً). لذلك ، فإن الحذف في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (n).
• البحث: للبحث عن العنصر 1 ، علينا اجتياز جميع العناصر. لذلك ، فإن البحث في شجرة البحث الثنائي لديه أسوأ تعقيد للحالة O (n). بشكل عام ، يكون تعقيد الوقت هو O (h) حيث h هو ارتفاع BST.
• الإدراج: لإدخال العنصر 0 ، يجب إدراجه باعتباره تابعًا يسارًا للرقم 1. لذلك ، نحتاج إلى اجتياز جميع العناصر لإدخال 0 الذي يحتوي على أسوأ حالة من التعقيد O (n). بشكل عام ، يكون الوقت المعقد هو O (h).
• الحذف: لحذف العنصر 1 ، يتعين علينا اجتياز جميع العناصر للعثور عليها. لذلك ، فإن الحذف في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (n). بشكل عام ، يكون الوقت المعقد هو O (h).

AVL TREES (ADEL’SON ‐ VEL’SKILL & LANDIS)
شجرة AVL (تسمى في الأصل الشجرة المسموح بها) هي شجرة يختلف فيها ارتفاع الشجرة الفرعية اليمنى واليسرى لكل عقدة بمقدار واحد على الأكثر


بالنسبة لشجرة AVL ، يجب أن تكون جميع عوامل التوازن +1 أو 0 أو -1.









• الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى هما شجرتا AVL

• يُقال أن العقدة  مرتفعة إذا كانت الشجرة الفرعية اليسرى أعلى ارتفاعًا
يمين ‐ مرتفع إذا كانت الشجرة الفرعية اليمنى متساوية في الارتفاع إذا كانت ارتفاعات LST و RST متساوية



موازنة شجرة AVL




بعد إدخال (أ) 60 ؛ (ب) 50 ؛ و (ج) 20 في شجرة بحث ثنائية فارغة في البداية ، فإن الشجرة تصبح غير متوازنة ؛ د) تقوم شجرة AVL المقابلة بتدوير عقدها لاستعادة التوازن.

أ) إضافة 80 إلى شجرة في الصورة السابقة (د) لا يغير توازن الشجرة ؛ (ب) إضافة 90 لاحقًا تجعل الشجرة غير متوازنة ؛ (ج) الدوران الأيسر يعيد التوازن.

تحليل التعقيد - شجرة AVL:
• البحث: للبحث عن العنصر 1 ، علينا اجتياز العناصر (بالترتيب 5 ، 4 ، 1) = 3 = log2n. لذلك ، فإن البحث في شجرة AVL لديه أسوأ حالة تعقيد لـ O (log2n).
• الإدراج: لإدخال العنصر 12 ، يجب إدراجه كعنصر تابع لليمين 9. لذلك ، نحتاج إلى اجتياز العناصر (بالترتيب 5 ، 7 ، 9) لإدخال 12 الذي يحتوي على أسوأ حالة تعقيد لـ O (log2n).
• الحذف: لحذف العنصر 9 ، علينا اجتياز العناصر لإيجاد 9 (بالترتيب 5 ، 7 ، 9). لذلك ، الحذف في الشجرة الثنائية له أسوأ حالة تعقيد لـ O (log2n).




HEAPS
نوع معين من الشجرة الثنائية ، يسمى heaps ، له الخصائص التالية:
• لا تقل قيمة كل عقدة عن القيم المخزنة في كل من فروعها.
• الشجرة متوازنة تمامًا ، والأوراق في المستوى الأخير كلها في أقصى اليسار.
• كل شجرة فرعية هي كومة. يوجد نوعان من الأكوام: Minheap: قيمة كل عقدة أقل من قيمة فروعها او children.، أي الجذر يحتوي على أصغر عنصر Maxheap: قيمة كل عقدة أكبر من قيمة فروعها او كما يطلق عليها children. أي الجذر يحتوي على أكبر عنصر


الشكل أ كلها أكوام ، والشكل ب ينتهك الخاصية الأولى ، والشكل ج ينتهك الخاصية الثانية.

إدراج عنصر في A MIN HEAP
• أدخل العنصر الجديد في الموضع التالي أسفل الكومة.
• بينما العنصر الجديد ليس في الجذر والعنصر الجديد أصغر من العنصر الأصل
• قم بتبديل العنصر الجديد بأصله ، ونقل العنصر الجديد لأعلى


إزالة عنصر من HEAP
قم بإزالة العنصر في العقدة الجذرية عن طريق استبداله بالعنصر الأخير في الكومة (LIH).
• في حين أن العنصر LIH لديه children و LIH أكبر children
• قم بتبديل LIH بchildren الأصغر ، مع تحريك LIH أسفل الكومة.


تحليل التعقيد - الكومة:
• الإدراج: يعتمد عدد العمليات المطلوبة فقط على عدد المستويات التي يجب أن يرتفعها العنصر الجديد لتلبية خاصية الكومة.
  وبالتالي ، فإن عملية الإدراج لها تعقيد زمني أسوأ حالة من O (log n). بالنسبة إلى كومة عشوائية ، ولإدخالات متكررة ، فإن عملية الإدراج لها متوسط تعقيد الحالة O (1).
• الاستخراج: في أسوأ الحالات ، يجب تبديل الجذر الجديد مع فرعه في كل مستوى حتى يصل إلى المستوى السفلي من الكومة ، مما يعني أن عملية الحذف لها تعقيد زمني بالنسبة لارتفاع الشجرة ، أو O (log n).
• البحث: البحث عن عنصر عشوائي يستغرق O (n) من الوقت. يمكن تقليل هذا إلى وقت O (1) المغلق إذا كان لدينا جدول تجزئة يعين عناصر كومة لمؤشرات الكومة أو مؤشرات العناصر.


ترجمة فيصل عسيري لصالح مدونة فاب
المرجع :
Adam Drozdek, Data Structures and Algorithms in Java, 4th edition, Cengage Learning Asia, 2013

مقالات شائعة

جميع الحقوق محفوظه © مدونة فـاب

تصميم الورشه