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

عندما تتعلم البرمجة لأول مرة ، من الشائع أن تتعلم المصفوفات باعتبارها "بنية البيانات الرئيسية".

في النهاية ، سوف تتعلم hash tablesأيضًا. إذا كنت تسعى للحصول على درجة علمية في علوم الكمبيوتر ، فعليك أن تأخذ فصلًا دراسيًا حول بنية البيانات. سوف تتعلم أيضا عن linked lists، queuesو stacks. تسمى هياكل البيانات هذه هياكل البيانات "الخطية" لأن لها جميعها بداية منطقية ونهاية منطقية.

عندما نبدأ تعلم treesو graphs، فإنه يمكن الحصول على مربكة حقا. نحن لا نخزن البيانات بطريقة خطية. كل من هياكل البيانات تخزن البيانات بطريقة محددة.

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

في هذه المقالة سوف نتعلم:

• ما هي الشجرة
• أمثلة على الأشجار
• مصطلحاته وكيف يعمل
• كيفية تنفيذ الهياكل الشجرية في الكود.

لنبدأ رحلة التعلم هذه. :)

تعريف

عند بدء البرمجة ، من الشائع فهم هياكل البيانات الخطية بشكل أفضل من هياكل البيانات مثل الأشجار والرسوم البيانية.

تُعرف الأشجار بأنها بنية بيانات غير خطية. لا يقومون بتخزين البيانات بطريقة خطية. ينظمون البيانات بشكل هرمي.

دعونا نتعمق في أمثلة من الحياة الواقعية!

ماذا أعني عندما أقول بطريقة هرمية؟

تخيل شجرة عائلة لها علاقات من جميع الأجيال: الأجداد والآباء والأبناء والأشقاء ، إلخ. نحن عادة ننظم أشجار العائلة بشكل هرمي.

الرسم أعلاه هو شجرة عائلتي. Tossico, Akikazu, Hitomi,و Takemiهي أجدادي.

Toshiakiو Juliana على والدي.

TK, Yuji, Bruno، Kaioوهم أبناء والديّ (أنا وإخوتي).

هيكل المنظمة هو مثال آخر على التسلسل الهرمي.

في HTML ، يعمل نموذج كائن المستند (DOM) كشجرة.

على HTMLالعلامة تتضمن العلامات الأخرى. لدينا headعلامة bodyوعلامة. تحتوي تلك العلامات على عناصر محددة. في headعلامة و metaو titleالعلامات. تحتوي bodyالعلامة على عناصر تظهر في واجهة المستخدم ، على سبيل المثال ، h1، a، li، إلخ.

تعريف تقني

أ treeهي مجموعة من الكيانات تسمى nodes. العقد متصلة بواسطة edges. nodeيحتوي كل منها على valueأو data، وقد يحتوي أو لا يحتوي على child node.

و first nodeمن treeيسمى root. إذا كان هذا root nodeمتصلاً بآخر node، فإن rootهو ثم parent nodeالمتصل nodeهو child.

كل Tree nodesترتبط بها وصلات تسمى edges. إنه جزء مهم من trees، لأنه يدير العلاقة بين nodes.

Leavesهي الأخيرة nodesعلى tree.وهي عقد بدون أطفال. مثل أشجار حقيقية، لدينا root، branchesوأخيرا leaves.

المفاهيم الهامة الأخرى التي يجب فهمها هي heightو depth.

يمثل heightالحرف a treeطول أطول مسار إلى a leaf.

الحرف depthمن a nodeهو طول المسار المؤدي إليه root.

ملخص المصطلحات

• الجذر هو الجزء العلوي nodeمنtree
• الحافة هي الرابط بين اثنينnodes
• الطفل هو nodeالذي لديهparent node
• الوالد هو nodeالذي لديه edgeإلىchild node
• الورقة هي nodeالتي لا تحتوي على child nodeملفtree
• الارتفاع هو طول أطول مسار إلىleaf
• العمق هو طول المسار المؤدي إليهroot

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

الآن سنناقش نوع معين من tree. نسميها binary tree.

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

فلنلقِ نظرة على مثال على a binary tree.

لنقم بترميز شجرة ثنائية

أول شيء يجب أن نضعه في الاعتبار عند تطبيق a binary treeهو أنها مجموعة من nodes. كل nodeديه ثلاث صفات: value، left_childو right_child.

كيف ننفذ بسيطًا يتم binary treeتهيئته باستخدام هذه الخصائص الثلاثة؟

لنلقي نظرة.

class BinaryTree: def __init__(self, value): self.value = value self.left_child = None self.right_child = None

ها هو. لدينا binary treeمن الدرجة.

عندما ننشئ كائنًا ، فإننا نمرر value(بيانات العقدة) كمعامل. انظر إلى left_childو right_child. كلاهما مضبوط على None.

لماذا ا؟

لأننا عندما نصنعنا node، ليس لدينا أي أطفال. لدينا فقط node data.

دعونا نختبرها:

tree = BinaryTree('a') print(tree.value) # a print(tree.left_child) # None print(tree.right_child) # None

هذا هو.

يمكننا تمرير string' a' كما valueلدينا Binary Tree node. إذا كنا طباعة value، left_childو right_child، يمكننا أن نرى القيم.

Let’s go to the insertion part. What do we need to do here?

We will implement a method to insert a new node to the right and to the left.

Here are the rules:

• If the current node doesn’t have a left child, we just create a new nodeand set it to the current node’s left_child.
• If it does have the left child, we create a new node and put it in the current left child’s place. Allocate this left child node to the new node’s left child.

Let’s draw it out. :)

Here’s the code:

def insert_left(self, value): if self.left_child == None: self.left_child = BinaryTree(value) else: new_node = BinaryTree(value) new_node.left_child = self.left_child self.left_child = new_node

Again, if the current node doesn’t have a left child, we just create a new node and set it to the current node’s left_child. Or else we create a new node and put it in the current left child’s place. Allocate this left child node to the new node’s left child.

And we do the same thing to insert a right child node.

def insert_right(self, value): if self.right_child == None: self.right_child = BinaryTree(value) else: new_node = BinaryTree(value) new_node.right_child = self.right_child self.right_child = new_node

Done. :)

But not entirely. We still need to test it.

Let’s build the followingtree:

To summarize the illustration of this tree:

• anode will be the root of our binary Tree
• aleft child is bnode
• aright child is cnode
• bright child is dnode (bnode doesn’t have a left child)
• cleft child is enode
• cright child is fnode
• both e and fnodes do not have children

So here is the code for the tree:

a_node = BinaryTree('a') a_node.insert_left('b') a_node.insert_right('c') b_node = a_node.left_child b_node.insert_right('d') c_node = a_node.right_child c_node.insert_left('e') c_node.insert_right('f') d_node = b_node.right_child e_node = c_node.left_child f_node = c_node.right_child print(a_node.value) # a print(b_node.value) # b print(c_node.value) # c print(d_node.value) # d print(e_node.value) # e print(f_node.value) # f

Insertion is done.

Now we have to think about tree traversal.

We have two options here: Depth-First Search (DFS) and Breadth-First Search (BFS).

• DFS “is an algorithm for traversing or searching tree data structure. One starts at the root and explores as far as possible along each branch before backtracking.” — Wikipedia
• BFS “is an algorithm for traversing or searching tree data structure. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.” — Wikipedia

So let’s dive into each tree traversal type.

Depth-First Search (DFS)

DFS explores a path all the way to a leaf before backtracking and exploring another path. Let’s take a look at an example with this type of traversal.

The result for this algorithm will be 1–2–3–4–5–6–7.

Why?

Let’s break it down.

1. Start at the root (1). Print it.

2. Go to the left child (2). Print it.

3. Then go to the left child (3). Print it. (This node doesn’t have any children)

4. Backtrack and go the right child (4). Print it. (This node doesn’t have any children)

5. Backtrack to the rootnode and go to the right child (5). Print it.

6. Go to the left child (6). Print it. (This node doesn’t have any children)

7. Backtrack and go to the right child (7). Print it. (This node doesn’t have any children)

8. Done.

When we go deep to the leaf and backtrack, this is called DFS algorithm.

Now that we are familiar with this traversal algorithm, we will discuss types of DFS: pre-order, in-order, and post-order.

Pre-order

This is exactly what we did in the above example.

1. Print the value of the node.
2. Go to the left child and print it. This is if, and only if, it has a left child.
3. Go to the right child and print it. This is if, and only if, it has a right child.

def pre_order(self): print(self.value) if self.left_child: self.left_child.pre_order() if self.right_child: self.right_child.pre_order()

In-order

The result of the in-order algorithm for this tree example is 3–2–4–1–6–5–7.

The left first, the middle second, and the right last.

Now let’s code it.

def in_order(self): if self.left_child: self.left_child.in_order() print(self.value) if self.right_child: self.right_child.in_order()

1. Go to the left child and print it. This is if, and only if, it has a left child.
2. Print the node’s value
3. Go to the right child and print it. This is if, and only if, it has a right child.

Post-order

The result of the post order algorithm for this tree example is 3–4–2–6–7–5–1.

The left first, the right second, and the middle last.

Let’s code this.

def post_order(self): if self.left_child: self.left_child.post_order() if self.right_child: self.right_child.post_order() print(self.value)

1. Go to the left child and print it. This is if, and only if, it has a left child.
2. Go to the right child and print it. This is if, and only if, it has a right child.
3. Print the node’s value

Breadth-First Search (BFS)

BFS algorithm traverses the tree level by level and depth by depth.

Here is an example that helps to better explain this algorithm:

So we traverse level by level. In this example, the result is 1–2–5–3–4–6–7.

• Level/Depth 0: only node with value 1
• Level/Depth 1: nodes with values 2 and 5
• Level/Depth 2: nodes with values 3, 4, 6, and 7

Now let’s code it.

def bfs(self): queue = Queue() queue.put(self) while not queue.empty(): current_node = queue.get() print(current_node.value) if current_node.left_child: queue.put(current_node.left_child) if current_node.right_child: queue.put(current_node.right_child)

To implement a BFS algorithm, we use the queue data structure to help.

How does it work?

Here’s the explanation.

1. First add the rootnode into the queue with the put method.
2. Iterate while the queue is not empty.
3. Get the first node in the queue, and then print its value.
4. Add both left and rightchildren into the queue (if the current nodehas children).
5. Done. We will print the value of each node, level by level, with our queuehelper.

Binary Search tree

"تسمى شجرة البحث الثنائية أحيانًا الأشجار الثنائية المرتبة أو المصنفة ، وهي تحتفظ بقيمها في ترتيب مصنف ، بحيث يمكن أن تستخدم عمليات البحث والعمليات الأخرى مبدأ البحث الثنائي" - ويكيبيديا

من الخصائص المهمة لـ a Binary Search Treeأن قيمة a Binary Search Treenodeأكبر من قيمة نسلها left child، ولكنها أصغر من قيمة نسلها right child."

فيما يلي تفصيل للشكل التوضيحي أعلاه:

• A هو مقلوب. و subtreeاحتياجات 7-5-8-6 لتكون على الجانب الأيمن، و subtreeاحتياجات 2-1-3 لتكون على اليسار.
• B هو الخيار الصحيح الوحيد. يرضي Binary Search Treeالممتلكات.
• C لديها مشكلة واحدة: nodeمع القيمة 4. يجب أن تكون على الجانب الأيسر من rootلأنها أصغر من 5.

Let’s code a Binary Search Tree!

Now it’s time to code!

What will we see here? We will insert new nodes, search for a value, delete nodes, and the balance of the tree.

Let’s start.

Insertion: adding new nodes to our tree

Imagine that we have an empty tree and we want to add new nodes with the following values in this order: 50, 76, 21, 4, 32, 100, 64, 52.

The first thing we need to know is if 50 is the root of our tree.

We can now start inserting node by node.

• 76 is greater than 50, so insert 76 on the right side.
• 21 is smaller than 50, so insert 21 on the left side.
• 4 is smaller than 50. Node with value 50 has a left child 21. Since 4 is smaller than 21, insert it on the left side of this node.
• 32 is smaller than 50. Node with value 50 has a left child 21. Since 32 is greater than 21, insert 32 on the right side of this node.
• 100 is greater than 50. Node with value 50 has a right child 76. Since 100 is greater than 76, insert 100 on the right side of this node.
• 64 is greater than 50. Node with value 50 has a right child 76. Since 64 is smaller than 76, insert 64 on the left side of this node.
• 52 is greater than 50. Node with value 50 has a right child 76. Since 52 is smaller than 76, node with value 76 has a left child 64. 52 is smaller than 64, so insert 54 on the left side of this node.

Do you notice a pattern here?

Let’s break it down.

1. Is the new node value greater or smaller than the current node?
2. If the value of the new node is greater than the current node, go to the right subtree. If the current node doesn’t have a right child, insert it there, or else backtrack to step #1.
3. If the value of the new node is smaller than the current node, go to the left subtree. If the current node doesn’t have a left child, insert it there, or else backtrack to step #1.
4. We did not handle special cases here. When the value of a new node is equal to the current value of the node, use rule number 3. Consider inserting equal values to the left side of the subtree.

Now let’s code it.

class BinarySearchTree: def __init__(self, value): self.value = value self.left_child = None self.right_child = None def insert_node(self, value): if value <= self.value and self.left_child: self.left_child.insert_node(value) elif value  self.value and self.right_child: self.right_child.insert_node(value) else: self.right_child = BinarySearchTree(value)

It seems very simple.

The powerful part of this algorithm is the recursion part, which is on line 9 and line 13. Both lines of code call the insert_node method, and use it for its left and rightchildren, respectively. Lines 11 and 15 are the ones that do the insertion for each child.

Let’s search for the node value… Or not…

The algorithm that we will build now is about doing searches. For a given value (integer number), we will say if our Binary Search Tree does or does not have that value.

An important item to note is how we defined the tree insertion algorithm. First we have our rootnode. All the left subtreenodes will have smaller values than the rootnode. And all the right subtreenodes will have values greater than the rootnode.

Let’s take a look at an example.

Imagine that we have this tree.

Now we want to know if we have a node based on value 52.

Let’s break it down.

1. We start with the rootnode as our current node. Is the given value smaller than the current node value? If yes, then we will search for it on the left subtree.
2. Is the given value greater than the current node value? If yes, then we will search for it on the right subtree.
3. If rules #1 and #2 are both false, we can compare the current node value and the given value if they are equal. If the comparison returns true, then we can say, “Yeah! Our tree has the given value,” otherwise, we say, “Nooo, it hasn’t.”

Now let’s code it.

class BinarySearchTree: def __init__(self, value): self.value = value self.left_child = None self.right_child = None def find_node(self, value): if value  self.value and self.right_child: return self.right_child.find_node(value) return value == self.value

Let’s beak down the code:

• Lines 8 and 9 fall under rule #1.
• Lines 10 and 11 fall under rule #2.
• Line 13 falls under rule #3.

How do we test it?

Let’s create our Binary Search Tree by initializing the rootnode with the value 15.

bst = BinarySearchTree(15)

And now we will insert many new nodes.

bst.insert_node(10) bst.insert_node(8) bst.insert_node(12) bst.insert_node(20) bst.insert_node(17) bst.insert_node(25) bst.insert_node(19)

For each inserted node , we will test if our find_node method really works.

print(bst.find_node(15)) # True print(bst.find_node(10)) # True print(bst.find_node(8)) # True print(bst.find_node(12)) # True print(bst.find_node(20)) # True print(bst.find_node(17)) # True print(bst.find_node(25)) # True print(bst.find_node(19)) # True

Yeah, it works for these given values! Let’s test for a value that doesn’t exist in our Binary Search Tree.

print(bst.find_node(0)) # False

Oh yeah.

Our search is done.

Deletion: removing and organizing

Deletion is a more complex algorithm because we need to handle different cases. For a given value, we need to remove the node with this value. Imagine the following scenarios for this node : it has no children, has a single child, or has two children.

• Scenario #1: A node with no children (leafnode).

# |50| |50| # / \ / \ # |30| |70| (DELETE 20) ---> |30| |70| # / \ \ # |20| |40| |40|

If the node we want to delete has no children, we simply delete it. The algorithm doesn’t need to reorganize the tree.

• Scenario #2: A node with just one child (left or right child).

# |50| |50| # / \ / \ # |30| |70| (DELETE 30) ---> |20| |70| # / # |20|

In this case, our algorithm needs to make the parent of the node point to the child node. If the node is the left child, we make the parent of the left child point to the child. If the node is the right child of its parent, we make the parent of the right child point to the child.

• Scenario #3: A node with two children.

# |50| |50| # / \ / \ # |30| |70| (DELETE 30) ---> |40| |70| # / \ / # |20| |40| |20|

When the node has 2 children, we need to find the node with the minimum value, starting from the node’sright child. We will put this node with minimum value in the place of the node we want to remove.

It’s time to code.

def remove_node(self, value, parent): if value < self.value and self.left_child: return self.left_child.remove_node(value, self) elif value  self.value and self.right_child: return self.right_child.remove_node(value, self) elif value > self.value: return False else: if self.left_child is None and self.right_child is None and self == parent.left_child: parent.left_child = None self.clear_node() elif self.left_child is None and self.right_child is None and self == parent.right_child: parent.right_child = None self.clear_node() elif self.left_child and self.right_child is None and self == parent.left_child: parent.left_child = self.left_child self.clear_node() elif self.left_child and self.right_child is None and self == parent.right_child: parent.right_child = self.left_child self.clear_node() elif self.right_child and self.left_child is None and self == parent.left_child: parent.left_child = self.right_child self.clear_node() elif self.right_child and self.left_child is None and self == parent.right_child: parent.right_child = self.right_child self.clear_node() else: self.value = self.right_child.find_minimum_value() self.right_child.remove_node(self.value, self) return True

1. First: Note the parameters value and parent. We want to find the nodethat has this value , and the node’s parent is important to the removal of the node.
2. Second: Note the returning value. Our algorithm will return a boolean value. It returns True if it finds the node and removes it. Otherwise it will return False.
3. From line 2 to line 9: We start searching for the node that has the valuethat we are looking for. If the value is smaller than the current nodevalue , we go to the left subtree, recursively (if, and only if, the current node has a left child). If the value is greater, go to the right subtree, recursively.
4. Line 10: We start to think about the remove algorithm.
5. From line 11 to line 13: We cover the node with no children , and it is the left child from its parent. We remove the node by setting the parent’s left child to None.
6. Lines 14 and 15: We cover the node with no children , and it is the right child from it’s parent. We remove the node by setting the parent’s right child to None.
7. Clear node method: I will show the clear_node code below. It sets the nodes left child , right child, and its value to None.
8. From line 16 to line 18: We cover the node with just one child (left child), and it is the left child from it’s parent. We set the parent's left child to the node’s left child (the only child it has).
9. From line 19 to line 21: We cover the node with just one child (left child), and it is the right child from its parent. We set the parent's right child to the node’s left child (the only child it has).
10. From line 22 to line 24: We cover the node with just one child (right child), and it is the left child from its parent. We set the parent's left child to the node’s right child (the only child it has).
11. From line 25 to line 27: We cover the node with just one child (right child) , and it is the right child from its parent. We set the parent's right child to the node’s right child (the only child it has).
12. From line 28 to line 30: We cover the node with both left and rightchildren. We get the node with the smallest value (the code is shown below) and set it to the value of the current node . Finish it by removing the smallest node.
13. Line 32: If we find the node we are looking for, it needs to return True. From line 11 to line 31, we handle this case. So just return True and that’s it.

• To use the clear_node method: set the None value to all three attributes — (value, left_child, and right_child)

def clear_node(self): self.value = None self.left_child = None self.right_child = None

• To use the find_minimum_value method: go way down to the left. If we can’t find anymore nodes, we found the smallest one.

def find_minimum_value(self): if self.left_child: return self.left_child.find_minimum_value() else: return self.value

Now let’s test it.

We will use this tree to test our remove_node algorithm.

# |15| # / \ # |10| |20| # / \ / \ # |8| |12| |17| |25| # \ # |19|

Let’s remove the node with the value 8. It’s a node with no child.

print(bst.remove_node(8, None)) # True bst.pre_order_traversal() # |15| # / \ # |10| |20| # \ / \ # |12| |17| |25| # \ # |19|

Now let’s remove the node with the value 17. It’s a node with just one child.

print(bst.remove_node(17, None)) # True bst.pre_order_traversal() # |15| # / \ # |10| |20| # \ / \ # |12| |19| |25|

Finally, we will remove a node with two children. This is the root of our tree.

print(bst.remove_node(15, None)) # True bst.pre_order_traversal() # |19| # / \ # |10| |20| # \ \ # |12| |25|

The tests are now done. :)

That’s all for now!

We learned a lot here.

Congrats on finishing this dense content. It’s really tough to understand a concept that we do not know. But you did it. :)

This is one more step forward in my journey to learning and mastering algorithms and data structures. You can see the documentation of my complete journey here on my Renaissance Developer publication.

Have fun, keep learning and coding.

My Twitter & Github. ☺

Additional resources

• Introduction to Tree Data Structure by mycodeschool
• Tree by Wikipedia
• How To Not Be Stumped By Trees by the talented Vaidehi Joshi
• Intro to Trees, Lecture by Professor Jonathan Cohen
• Intro to Trees, Lecture by Professor David Schmidt
• Intro to Trees, Lecture by Professor Victor Adamchik
• Trees with Gayle Laakmann McDowell
• Binary Tree Implementation and Tests by TK
• Coursera Course: Data Structures by University of California, San Diego
• Coursera Course: Data Structures and Performance by University of California, San Diego
• Binary Search Tree concepts and Implementation by Paul Programming
• تنفيذ شجرة البحث الثنائية والاختبارات بواسطة TK
• اجتياز الشجرة بواسطة ويكيبيديا
• شجرة البحث الثنائية إزالة خوارزمية العقدة بواسطة GeeksforGeeks
• شجرة البحث الثنائية إزالة خوارزمية العقدة بواسطة Algolist
• تعلم بايثون من الصفر إلى البطل