by Yung L. Leung

梁永良

are simple in direction. A linked list is a list of nodes (each containing their own data) that are linked from one node to the next (and to the previous, for a doubly linked list). A stack builds upward like a tower of data. Each node stacking atop another, and shortens in a last in first out (LIFO) manner. A queue is a line of nodes that elongate from the end of the line and shortens in a first in first out (FIFO) mechanism.

的方向很简单。 链表是节点列表(每个节点都包含自己的数据)，这些节点从一个节点链接到下一个节点(对于双链表，则链接到前一个节点)。 堆栈像数据塔一样向上构建。 每个节点堆叠在一起，并以后进先出( LIFO )的方式缩短。 队列是从行尾开始延伸并以先进先出( FIFO )机制缩短的一排节点。

Binary data structures are like a fork in a road of data. The nodes build like the branches of a tree or a heap of rocks.

二进制数据结构就像一条数据之路的分支。 节点的构建就像一棵树的树枝或一堆岩石一样。

树木 (Trees)

A binary search tree is made up of nodes that branch off to no more than two nodes (binary). A parent node can have left and right child nodes. By convention, left child nodes contain values less than the parent. Whereas right child nodes contain greater values (left is less, right is greater). All trees begin with a single root node.

二进制搜索树由分支到不超过两个节点(二进制)的节点组成。 父节点可以具有左右子节点。 按照惯例，左子节点包含的值小于父节点。 而右子节点包含更大的值( left较小，right较大 )。 所有树都以单个根节点开头。

To insert a value requires creating a new node, comparing its value to the root & its descendant values, while deciding to search further leftward (insertion of lesser value) or rightward (insertion of greater value). Once an available position is found, the node is inserted in place.

要插入值，需要创建一个新节点 ，将其值与根及其后代值进行比较，同时决定进一步向左(插入较小的值)或向右(插入较大的值)进行搜索。 找到可用位置后，将节点插入到位。

To find a value is similar to the insertion of a value. You are performing the search for a stored value and returning the node containing it.

查找值类似于插入值。 您正在搜索存储的值并返回包含它的节点。

To make a breadth-first search of values requires storing a root value. Then proceeding with the left child, then the right child and so forth.

要进行广度优先的值搜索 ，需要存储一个根值。 然后继续处理左孩子，然后是右孩子，依此类推。

To make a depth-first search (pre-order) of values requires storing a root value. Then proceeding with all leftward descendants, before the rightward descendants.

要进行值的深度优先搜索(预定) ，需要存储一个根值。 然后继续处理所有向左的后代，再向右的后代。

Since inserting & finding a node of some value are relatively similar processes (insertion inserts a node whereas finding returns a node), it is of no surprise that their complexity is the same, O(log n).

由于插入和查找某个值的节点是相对相似的过程(插入会插入一个节点，而查找会返回一个节点)，因此其复杂度相同( O(log n) )也就不足为奇了。

For a 3 node binary search tree, to find 5 requires two steps:

对于3节点的二叉搜索树 ，要找到 5则需要两个步骤：

• Is 5 greater than or less than 3? Proceed rightward.

  5是否大于或小于3？ 向右前进。

• Is 5 equal to the value being searched? Return node.

  5等于要搜索的值吗？ 返回节点。

Similarly to insert a node with value 6 requires two steps:

类似地， 插入值为6的节点需要两个步骤：

• Is 6 greater than or less than 3? Proceed rightward.

  6是大于还是小于3？ 向右前进。

• Is 6 greater than or less than 5? Insert the right side.

  6是大于还是小于5？ 插入右侧。

堆 (Heaps)

A binary heap is a pyramidal structure of nodes whose nodes can stack upward with rows of decreasing values toward a minimum (minimum binary heap) or with rows of increasing values toward a maximum (maximum binary heap). Like the tree, each parent node can extend up to two child nodes. Unlike the tree, each parent can contain a lesser value than its children (minimum binary heap) or a greater value (maximum binary heap).

二进制堆是节点的金字塔结构，其节点可以向上堆叠，而递减值的行朝着最小值( 最小二进制堆 )，或者具有递增值的行朝着最大值( 最大二进制堆 )。 像树一样，每个父节点最多可以扩展到两个子节点。 与树不同，每个父级可以包含比其子级更小的值( 最小二进制堆 )或更大的值( 最大二进制堆 )。

For a max binary heap, to insert a value at the base of the pyramid requires comparing it to parent nodes and bubbling up the larger value.

对于最大二进制堆 ，要在金字塔的底部插入一个值，需要将其与父节点进行比较，然后冒泡较大的值。

To extract a max value requires removing the apex value and sinking down a value from the pyramid’s base. This involves finding the higher of the two children nodes.

要提取最大值，需要删除顶点值，并从金字塔的底下沉一个值。 这涉及到找到两个子节点中较高的一个。

For a max binary heap, insertion of a node & extraction of a node with the max value both has a complexity of O(log n).

对于最大二进制堆 ， 插入节点和提取具有最大值的节点的复杂度均为O(log n) 。

For a 3 node max binary heap, insertion of a node with value 6 requires two steps.

对于3个节点的最大二进制堆 ，插入值为6的节点需要两个步骤。

• Upon attaching node of value 6 to a new row (below 4), is 6 greater than or less than 4? Swap.

  在将值6的节点附加到新行(在4以下)时， 6是大于还是小于4？ 交换。

• Is 6 greater than or less than 5? Swap.

  6是大于还是小于5？ 交换。

Similarly, after the removal of a node with a max value & replacing it with a node of value 1, two steps remain.

类似地，在删除具有最大值的节点并将其替换为值为1的节点后，剩下两个步骤。

• Is 1 greater than or less than 5? Swap.

  1是否大于或小于5？ 交换。

• Is 1 greater than or less than 4? Swap.

  1是大于还是小于4？ 交换。

Thank you for reading!

感谢您的阅读！

参考： (Reference:)

翻译自: