Tree hay Binary Tree đều là những khái niệm quen thuộc đối với dev chúng ta hiện nay. Nên bài viết này mình sẽ không focus nhiều vào lý thuyết về tree, mà sẽ cùng với các bạn tìm hiểu về chúng được sử dụng trong Python như thế nào. Trước khi bắt đầu, mình sẽ nói qua về 2 khái niệm này để cùng nhau ôn lại kiến thức nha.
Tree
Là cấu trúc dữ liệu phi tuyến tính (non-linear) đại diện cho các nút (node) được kết nối với nhau bởi các cạnh (edges). Mỗi cây đều bao gồm 1 nút cha (parent node), các nút trái và nút phải là các nút con (children nodes)
Binary Tree
Một tree mà bao gồm nhiều nhất một phần tử con ở mỗi bên trái và phải được gọi là Cây nhị phân (Binary Tree). Mỗi phần tử con chỉ có thể có hai phần tử con. Nút con bên trái có giá trị nhỏ hơn, nút con bên phải có giá trị lớn hơn giá trị của nút cha.
Implement a Binary Tree
Bài toán: Nhập một số bất kỳ và thêm chúng vào Cây nhị phân.
1. Lên kịch bản
1.1. Xác định Parent node
Ở đây mình chọn một con số mà đa số các anh em đều thích đó là con số 69 làm gốc. Ta sẽ có một cây nhị phân có dạng.
1.2. Thêm các chữ số vào cây
Sau đó, mình sẽ tiếp tục thêm 2 số 39 và 79. Theo quy tắc “Nhỏ trái – Lớn phải” thì mình có thể dễ dàng thêm 2 số này vào cây. Và cây của chúng ta giờ đây trông đã hoàn chỉnh hơn rồi.
Để chiếc cây trông đẹp hơn thì mình cùng thêm vào lần lượt các số: 68, 75, 30, 80.
Ở đây, chúng ta có một vấn đề nho nhỏ với con số 68 này. Chúng ta thấy rằng 68 lớn hơn 39 nhưng 68 cũng nhỏ hơn 79. Vậy, chúng ta sẽ đặt nó ở đâu được?
Để ý kỹ hơn một chút ta thấy có thể thấy 68 < 69 (Parent Node) nên theo quy tắc, ta sẽ để nó ở bên nhỏ hơn (39). Với số tiếp theo 75 cũng tương tự ta sẽ đặt nó ở vế nhỏ hơn của 79. Cuối cùng, ta được cây nhị phân trông khá bắt mắt =))
Khi chuyển về dạng dãy số thì chúng ta sẽ lấy các chữ số từ trái qua phải hay nói cách khác, cây nhị phân thể hiện cho dãy số được sắp xếp từ nhỏ đến lớn.
1 2 | Output: 30, 39, 68, 69, 75, 79, 80 |
Đây chỉ là bản “phác thảo” ý tưởng trên giấy. Vậy còn khi viết thành code nó sẽ ra sao? Chúng ta cùng tìm hiểu tiếp nha.
1.3. Tìm kiếm phần tử trong cây nhị phân
Để tìm kiếm được, ta lấy Parent Node làm gốc để so sánh. Nếu số nhận vào lớn hơn gốc, số cần tìm sẽ nằm ở bên phải của gốc và ngược lại, nếu nhỏ hơn số cần tìm sẽ nằm ở bên trái. Tương tự, chúng ta lấy nút con tiếp theo làm gốc và tiếp tục tìm kiếm. Kết quả cuối cùng sẽ nhận được là tìm thấy hoặc không.
Lợi ích của việc tìm kiếm bằng cây nhị phân giúp chúng ta không cần phải focus vào nửa còn lại của Parent Node, giúp giảm thời gian đáng kể khi tìm kiếm với lượng dữ liệu lớn.
2. Chuyển thể thành “phim”
Sau khi đã được lên được “Kịch bản” thì tiếp theo chúng ta cùng chuyển thể nó thành “phim” nhé (dull)
2.1. Xác định Parent node
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token punctuation">:</span> <span class="token keyword">def</span> <span class="token function">__init__</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> data<span class="token punctuation">)</span><span class="token punctuation">:</span> self<span class="token punctuation">.</span>left_child <span class="token operator">=</span> <span class="token boolean">None</span> self<span class="token punctuation">.</span>right_child <span class="token operator">=</span> <span class="token boolean">None</span> self<span class="token punctuation">.</span>parent_node <span class="token operator">=</span> data <span class="token keyword">def</span> <span class="token function">print_tree</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span>self<span class="token punctuation">.</span>data<span class="token punctuation">)</span> root <span class="token operator">=</span> Node<span class="token punctuation">(</span><span class="token number">69</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>print_tree<span class="token punctuation">(</span><span class="token punctuation">)</span> |
Ở đây mình tạo một class Node và gán một giá trị được nhập từ bàn phím cho nút.
1 2 3 | # Output 69 |
2.2. Thêm các chữ số vào cây
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token punctuation">:</span> <span class="token keyword">def</span> <span class="token function">__init__</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> data<span class="token punctuation">)</span><span class="token punctuation">:</span> self<span class="token punctuation">.</span>left_child <span class="token operator">=</span> <span class="token boolean">None</span> self<span class="token punctuation">.</span>right_child <span class="token operator">=</span> <span class="token boolean">None</span> self<span class="token punctuation">.</span>parent_node <span class="token operator">=</span> data <span class="token comment"># print function</span> <span class="token keyword">def</span> <span class="token function">print_tree</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token comment"># if there is no left_child then don't print</span> <span class="token keyword">if</span> self<span class="token punctuation">.</span>left_child<span class="token punctuation">:</span> self<span class="token punctuation">.</span>left_child<span class="token punctuation">.</span>print_tree<span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token comment"># print parent_node at the center</span> <span class="token keyword">print</span><span class="token punctuation">(</span>self<span class="token punctuation">.</span>parent_node<span class="token punctuation">)</span> <span class="token comment"># if there is no right_child then don't print</span> <span class="token keyword">if</span> self<span class="token punctuation">.</span>right_child<span class="token punctuation">:</span> self<span class="token punctuation">.</span>right_child<span class="token punctuation">.</span>print_tree<span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token keyword">def</span> <span class="token function">insert_number</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> input_number<span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token comment"># Compare the new value with the parent node</span> <span class="token keyword">if</span> self<span class="token punctuation">.</span>parent_node<span class="token punctuation">:</span> <span class="token comment"># if input number less than parent node, then it is on the left</span> <span class="token keyword">if</span> input_number <span class="token operator"><</span> self<span class="token punctuation">.</span>parent_node<span class="token punctuation">:</span> <span class="token keyword">if</span> self<span class="token punctuation">.</span>left_child <span class="token keyword">is</span> <span class="token boolean">None</span><span class="token punctuation">:</span> self<span class="token punctuation">.</span>left_child <span class="token operator">=</span> Node<span class="token punctuation">(</span>input_number<span class="token punctuation">)</span> <span class="token keyword">else</span><span class="token punctuation">:</span> self<span class="token punctuation">.</span>left_child<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span>input_number<span class="token punctuation">)</span> <span class="token comment"># if input number greater than parent node, then it is on the right</span> <span class="token keyword">elif</span> input_number <span class="token operator">></span> self<span class="token punctuation">.</span>parent_node<span class="token punctuation">:</span> <span class="token keyword">if</span> self<span class="token punctuation">.</span>right_child <span class="token keyword">is</span> <span class="token boolean">None</span><span class="token punctuation">:</span> self<span class="token punctuation">.</span>right_child <span class="token operator">=</span> Node<span class="token punctuation">(</span>input_number<span class="token punctuation">)</span> <span class="token keyword">else</span><span class="token punctuation">:</span> self<span class="token punctuation">.</span>right_child<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span>input_number<span class="token punctuation">)</span> <span class="token keyword">else</span><span class="token punctuation">:</span> self<span class="token punctuation">.</span>parent_node <span class="token operator">=</span> input_number root <span class="token operator">=</span> Node<span class="token punctuation">(</span><span class="token number">69</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">39</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">79</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">68</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">75</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">30</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">80</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>print_tree<span class="token punctuation">(</span><span class="token punctuation">)</span> |
Chúng ta sẽ được kết quả:
1 2 3 4 5 6 7 8 9 | # Output 30 39 68 69 75 79 80 |
2.3. Tìm kiếm phần tử trong cây nhị phân
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | <span class="token keyword">class</span> <span class="token class-name">Node</span><span class="token punctuation">:</span> <span class="token keyword">def</span> <span class="token function">__init__</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> data<span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token keyword">def</span> <span class="token function">print_tree</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token keyword">def</span> <span class="token function">insert_number</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> input_number<span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token punctuation">.</span><span class="token punctuation">.</span><span class="token punctuation">.</span> <span class="token comment"># find_value method to compare the value with nodes</span> <span class="token keyword">def</span> <span class="token function">find_value</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> input_number<span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token keyword">if</span> input_number <span class="token operator"><</span> self<span class="token punctuation">.</span>parent_node<span class="token punctuation">:</span> <span class="token keyword">if</span> self<span class="token punctuation">.</span>left_child <span class="token keyword">is</span> <span class="token boolean">None</span><span class="token punctuation">:</span> <span class="token keyword">return</span> <span class="token builtin">str</span><span class="token punctuation">(</span>input_number<span class="token punctuation">)</span><span class="token operator">+</span><span class="token string">" is not Found"</span> <span class="token keyword">return</span> self<span class="token punctuation">.</span>left_child<span class="token punctuation">.</span>find_value<span class="token punctuation">(</span>input_number<span class="token punctuation">)</span> <span class="token keyword">elif</span> input_number <span class="token operator">></span> self<span class="token punctuation">.</span>parent_node<span class="token punctuation">:</span> <span class="token keyword">if</span> self<span class="token punctuation">.</span>right_child <span class="token keyword">is</span> <span class="token boolean">None</span><span class="token punctuation">:</span> <span class="token keyword">return</span> <span class="token builtin">str</span><span class="token punctuation">(</span>input_number<span class="token punctuation">)</span><span class="token operator">+</span><span class="token string">" is not found"</span> <span class="token keyword">return</span> self<span class="token punctuation">.</span>right_child<span class="token punctuation">.</span>find_value<span class="token punctuation">(</span>input_number<span class="token punctuation">)</span> <span class="token keyword">else</span><span class="token punctuation">:</span> <span class="token keyword">return</span> <span class="token builtin">str</span><span class="token punctuation">(</span>self<span class="token punctuation">.</span>parent_node<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token string">" is found"</span> root <span class="token operator">=</span> Node<span class="token punctuation">(</span><span class="token number">69</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">39</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">79</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">68</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">75</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">30</span><span class="token punctuation">)</span> root<span class="token punctuation">.</span>insert_number<span class="token punctuation">(</span><span class="token number">80</span><span class="token punctuation">)</span> <span class="token keyword">print</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>find_value<span class="token punctuation">(</span><span class="token number">75</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">print</span><span class="token punctuation">(</span>root<span class="token punctuation">.</span>find_value<span class="token punctuation">(</span><span class="token number">70</span><span class="token punctuation">)</span><span class="token punctuation">)</span> |
Kết quả nhận được là:
1 2 3 4 | # Output 75 is found 70 is not found |
Lời cảm ơn
Nếu thấy “bộ phim” này có ích, đừng ngần ngại cho mình 1 upvote mình có thêm động lực ra nhiều bài viết có ích hơn nữa. Nếu “bộ phim” này có điều gì chưa được, hãy comment phía dưới để mình cải thiện thêm nha
Cảm ơn các bạn rất nhiều