مقدمة
هذه المقالة حول أشجار البحث الثنائية. لقد كتبت مؤخرًا مقالًا عن هناك لم أهتم حقًا بالأشجار الثنائية ، لأن طرق البحث والإدراج والحذف لم تكن ذات صلة. الآن قررت أن أكتب مقالاً عن الأشجار. ربما سنبدأ.
الشجرة هي بنية بيانات تتكون من عقد متصلة بواسطة حواف. يمكننا القول أن الشجرة هي حالة خاصة للرسم البياني. هنا مثال على شجرة:
هذه ليست شجرة بحث ثنائية! كل شيء تحت الخفض!
مفردات اللغة
جذر
جذر الشجرة هي العقدة العليا. في المثال ، هذه هي العقدة A. في الشجرة ، يمكن أن يؤدي مسار واحد فقط من الجذر إلى أي عقدة أخرى! في الواقع ، يمكن اعتبار أي عقدة جذرًا للشجرة الفرعية المقابلة لهذه العقدة.
الآباء / النسل
جميع العقد باستثناء الجذر لها حافة واحدة بالضبط تؤدي إلى عقدة أخرى. العقدة فوق العقدة الحالية تسمى الأبوين هذه العقدة. تسمى العقدة الموجودة أسفل العقدة الحالية والمتصلة بها تنازلي هذه العقدة. لنأخذ مثالا. خذ العقدة B ، ثم سيكون والدها هو العقدة A ، وأبنائها سيكونون العقد D و E و F.
ورقة
تسمى العقدة التي ليس لها أطفال بورقة الشجرة. في المثال ، العقد D ، E ، F ، G ، I ، J ، K ستكون أوراقًا.
هذا هو المصطلح الأساسي. سيتم مناقشة مفاهيم أخرى في وقت لاحق. لذلك ، فإن الشجرة الثنائية هي شجرة لا تحتوي كل عقدة فيها على أكثر من طفلين. كما خمنت ، لن تكون الشجرة من المثال ثنائية ، لأن العقدتين B و H بها أكثر من طفلين. فيما يلي مثال على شجرة ثنائية:
يمكن أن تحتوي عقد الشجرة على أي معلومات. شجرة البحث الثنائية هي شجرة ثنائية لها الخصائص التالية:
- كل من الأشجار الفرعية اليمنى واليسرى عبارة عن أشجار بحث ثنائية.
- تحتوي جميع عقد الشجرة الفرعية اليسرى لعقدة عشوائية X على قيم مفاتيح بيانات أقل من قيمة مفتاح البيانات الخاصة بالعقدة X نفسها.
- تحتوي جميع عقد الشجرة الفرعية اليمنى لعقدة عشوائية X على قيم مفاتيح بيانات أكبر من أو تساوي قيمة مفتاح البيانات للعقدة X نفسها.
مفتاح - بعض خصائص العقدة (على سبيل المثال ، رقم). المفتاح ضروري حتى تتمكن من العثور على عنصر الشجرة الذي يتوافق معه هذا المفتاح. مثال على شجرة البحث الثنائية:
عرض الشجرة
مع تقدمي ، سأقوم بتضمين بعض أجزاء التعليمات البرمجية (ربما غير المكتملة) من أجل تحسين فهمك. سيكون الرمز الكامل في نهاية المقال.
تتكون الشجرة من عقد. هيكل العقدة:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...остальные методы узла
}
كل عقدة لها طفلان (من المحتمل جدًا أن يكون الطفل الأيسر و / أو الطفل الأيمن فارغًا). ربما تكون قد فهمت أنه في هذه الحالة ، تكون بيانات الرقم هي البيانات المخزنة في العقدة ؛ مفتاح - مفتاح العقدة.
لقد توصلنا إلى حل المشكلة ، لنتحدث الآن عن المشاكل الملحة المتعلقة بالأشجار. فيما يلي كلمة "شجرة" تعني مفهوم شجرة البحث الثنائية. هيكل الشجرة الثنائية:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
كحقل فئة ، نحتاج فقط إلى جذر الشجرة ، لأنه من الجذر ، باستخدام أساليب getLeftChild () و getRightChild () ، يمكنك الوصول إلى أي عقدة في الشجرة.
خوارزميات الشجرة
بحث
لنفترض أن لديك شجرة مبنية. كيف تجد العنصر مع المفتاح الرئيسي؟ تحتاج إلى الانتقال بالتسلسل من الجذر إلى أسفل الشجرة ومقارنة قيمة المفتاح بمفتاح العقدة التالية: إذا كان المفتاح أقل من مفتاح العقدة التالية ، فانتقل إلى سليل العقدة الأيسر ، إذا كان هناك المزيد - إلى اليمين ، إذا كانت المفاتيح متساوية - تم العثور على العقدة المطلوبة! الكود ذو الصلة:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
إذا أصبح التيار فارغًا ، فهذا يعني أن التكرار قد وصل إلى نهاية الشجرة (على المستوى المفاهيمي ، أنت في مكان غير موجود في الشجرة - طفل ورقة).
ضع في اعتبارك كفاءة خوارزمية البحث على شجرة متوازنة (شجرة يتم فيها توزيع العقد بشكل متساوٍ أو أكثر). ثم ستكون كفاءة البحث O (log (n)) ، واللوغاريتم الأساسي 2. انظر: إذا كان هناك عدد n من العناصر في شجرة متوازنة ، فهذا يعني أنه سيكون هناك مستويات أساسية 2 من الشجرة. وفي البحث ، عن خطوة واحدة من الدورة ، تنزل مستوى واحدًا.
أدخل
إذا كنت قد فهمت جوهر البحث ، فلن يكون من الصعب عليك فهم الإدخال. تحتاج فقط إلى النزول إلى ورقة الشجرة (وفقًا لقواعد النسب الموضحة في البحث) وتصبح سليلها - يسارًا أو يمينًا ، اعتمادًا على المفتاح. تطبيق:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
في هذه الحالة ، بالإضافة إلى العقدة الحالية ، من الضروري تخزين معلومات حول أصل العقدة الحالية. عندما يصبح التيار فارغًا ، سيحتوي المتغير الأصل على الورقة التي نحتاجها.
من الواضح أن كفاءة الإدراج ستكون مماثلة لكفاءة البحث - O (log (n)).
إزالة
الحذف هو أكثر العمليات تعقيدًا التي يجب إجراؤها باستخدام الشجرة. من الواضح أنه سيكون من الضروري أولاً العثور على العنصر الذي سنقوم بإزالته. لكن ماذا بعد ذلك؟ إذا قمنا ببساطة بتعيين مرجعها إلى فارغ ، فسوف نفقد معلومات حول الشجرة الفرعية التي يكون جذرها هو هذه العقدة. تنقسم طرق إزالة الأشجار إلى ثلاث حالات.
الحالة الأولى. العقدة المراد إزالتها ليس لها توابع.
إذا لم يكن للعقدة المراد حذفها توابع ، فهذا يعني أنها ورقة طرفية. لذلك ، يمكنك ببساطة تعيين حقلي leftChild أو rightChild لوالديها على null.
الحالة الثانية. العقدة المراد إزالتها لها طفل واحد
هذه الحالة ليست صعبة للغاية أيضًا. دعنا نعود إلى مثالنا. لنفترض أننا بحاجة إلى حذف عنصر بالمفتاح 14. توافق على أنه نظرًا لأنه الطفل الصحيح للعقدة التي تحتوي على المفتاح 10 ، فإن أي من أحفادها (في هذه الحالة ، العنصر الصحيح) سيكون له مفتاح أكبر من 10 ، لذلك أنت يمكنه بسهولة "قطعه" من الشجرة ، وربط الوالد مباشرة بفرع العقدة التي يتم حذفها ، أي قم بتوصيل العقدة بالمفتاح 10 بالعقدة 13. سيكون الموقف مشابهًا إذا اضطررنا إلى حذف عقدة هي الفرع الأيسر لوالدها. فكر في الأمر بنفسك - تشبيه دقيق.
الحالة الثالثة. العقدة لديها طفلان
أصعب حالة. دعنا نلقي نظرة على مثال جديد.
ابحث عن خليفة
لنفترض أننا بحاجة إلى إزالة العقدة بالمفتاح 25. من الذي نضعه في مكانه؟ يشترط في أحد أتباعه (الأحفاد أو الأحفاد) أن يصبح خليفة(الشخص الذي سيحل محل العقدة التي تمت إزالتها).
كيف تعرف من يجب أن يكون الخلف؟ بشكل بديهي ، هذه هي العقدة في الشجرة التي يكون مفتاحها هو ثاني أكبر نقطة من العقدة التي يتم إزالتها. الخوارزمية هي على النحو التالي. أنت بحاجة للذهاب إلى الطفل الأيمن (دائمًا إلى اليمين ، لأنه قيل بالفعل أن مفتاح الخلف أكبر من مفتاح العقدة التي يتم حذفها) ، ثم انتقل عبر سلسلة الأطفال الأيسر من هذا اليمين طفل. في المثال ، يجب أن نذهب إلى العقدة التي تحتوي على المفتاح 35 ، ثم نذهب إلى أسفل سلسلة الأبناء الأيسر إلى الورقة - في هذه الحالة ، تتكون هذه السلسلة فقط من العقدة ذات المفتاح 30. بالمعنى الدقيق للكلمة ، نحن نبحث عن أصغر عقدة في مجموعة العقد أكبر من العقدة المطلوبة.
رمز طريقة البحث الوريث:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//родитель преемника
Node<T> successor = deleteNode;//преемник
Node<T> current = successor.getRightChild();//просто "пробегающий" узел
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//на выходе из цикла имеем преемника и родителя преемника
if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
}
return successor;
}
الكود الكامل لطريقة الحذف:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//второй случай
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//третий случай
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
يمكن تقريب التعقيد إلى O (سجل (ن)).
إيجاد الحد الأقصى / الأدنى في الشجرة
من الواضح ، كيفية العثور على الحد الأدنى / الحد الأقصى للقيمة في الشجرة - تحتاج إلى المرور بالتسلسل عبر سلسلة العناصر اليسرى / اليمنى للشجرة ، على التوالي ؛ عندما تصل إلى الورقة ، سيكون الحد الأدنى / الحد الأقصى للعنصر.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
التعقيد - O (تسجيل (ن))
متماثل الالتفافية
الاجتياز عبارة عن زيارة لكل عقدة في الشجرة للقيام بشيء ما معها.
خوارزمية الاجتياز المتكرر المتماثل:
- قم بعمل على الطفل الأيسر
- قم بعمل مع نفسك
- اتخذ إجراء بشأن الطفل المناسب
كود:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
اختتام
أخيراً! إذا لم أشرح شيئًا أو لدي أي تعليقات ، فأنا أنتظر في التعليقات. كما وعدت ، ها هي الكود الكامل.
عقدة جافا:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.جافا:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
انحطاط إلى O (ن)
ربما لاحظ الكثير منكم: ماذا لو جعلت الشجرة غير متوازنة؟ على سبيل المثال ، ضع عقدًا في الشجرة بمفاتيح متزايدة: 1,2,3,4,5,6،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX ... ثم ستذكرنا الشجرة إلى حد ما بقائمة مرتبطة. ونعم ، ستفقد الشجرة هيكلها الشجري ، وبالتالي كفاءة الوصول إلى البيانات. سيصبح تعقيد عمليات البحث والإدراج والحذف هو نفسه الموجود في القائمة المرتبطة: O (n). هذا هو أحد أهم عيوب الأشجار الثنائية ، في رأيي.
يمكن للمستخدمين المسجلين فقط المشاركة في الاستطلاع. ، من فضلك.
لم أقم بزيارة حبري منذ فترة طويلة ، وأود أن أعرف ما هي المقالات حول أي مواضيع تود أن ترى المزيد؟
-
هياكل البيانات
-
الخوارزميات (DP ، العودية ، ضغط البيانات ، إلخ.)
-
تطبيق هياكل البيانات والخوارزميات في الحياة الواقعية
-
برمجة تطبيقات أندرويد بجافا
-
برمجة تطبيقات الويب جافا
صوت 2 من المستخدمين. امتنع مستخدم واحد عن التصويت.
المصدر: www.habr.com