الدرس 15 · Data structures

Trees

لم يُترجم بعد؛ يُعرض باللغة الإنجليزية

Lists and queues keep values in a row. A tree branches instead: each node links down to children, from one root at the top to the leaves at the bottom. Meet the parts of a tree, see the trees you already use, then watch a binary search tree find 60, insert 35 and list every value in sorted order.

10 دقيقة10 خطوات5 أسئلةBeginner

شكل 15 · تفاعلي

جارٍ تحميل الرسم…

أو ← →

اختبر نفسك

5 أسئلة سريعة

اختر إجابة لتعرف السبب. تُحفَظ نتيجتك مع تقدّمك.

01In a tree, what is a leaf?

Leaves are the nodes at the ends of the branches: they have no children. The top node, the only one with no parent, is the root.

02In the binary search tree 50 (root), 30, 70, 20, 40, 60, 80, which nodes does a search for 40 visit?

Start at the root. 40 is smaller than 50, so go left to 30. 40 is larger than 30, so go right, and there is 40.

03Where does inserting 65 into that same tree put the new node?

65 > 50: go right to 70. 65 < 70: go left to 60. 65 > 60: go right. That spot is empty, so 65 becomes the right child of 60.

04You insert 1, 2, 3, 4, 5 into an empty binary search tree, in that order. What shape do you get?

Each new value is larger than everything before it, so it always goes right. The tree becomes a line, and a search may have to check every node.

05What does an in-order traversal of a binary search tree produce?

In-order visits the left subtree, then the node, then the right subtree. In a binary search tree everything left is smaller and everything right is larger, so the values come out sorted.

المصطلحات الأساسية

المسرد

Node: One item in a tree. It holds a value and links to its children.
Root: The top node of a tree: the only node with no parent.
Leaf: A node with no children.
Parent and child: A node links down to its children; each child has exactly one parent.
Depth and height: A node's depth is the number of links from the root down to it. A tree's height is its largest depth.
Binary search tree: A binary tree where, at every node, the left subtree holds only smaller values and the right subtree only larger ones.
Traversal: Visiting every node of a tree once. In-order visits the left subtree, then the node, then the right subtree.
O(log n) and O(n): Ways to say how the work grows with n values: with the number of levels (about log2 of n) or in step with n itself.

تفاصيل إضافية

الملاحظات والمصادر

O(log n), read "order log n", means the work grows like the logarithm of n: doubling the number of values adds about one more comparison. O(n) means the work grows in step with n.
A plain binary search tree only stays balanced if the values arrive in a mixed-up order. Self-balancing trees, such as red-black trees and AVL trees, reshape themselves on every insert so the height stays about log2(n).
A full tree with 20 levels holds 2^20 - 1 = 1,048,575 nodes, and a search compares at most once per level.
This insert sends a value equal to a node's key to the right. Many libraries instead refuse duplicates or keep a count.
Strictly, the browser builds the DOM tree from HTML and fills in parts the page leaves out, such as a missing head or body.

اختبار يتاح بعد الخطوة الأخيرة.