|
I have this confusion. What is the local minimum of a complete binary tree? Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(T)$ is labeled with a real number $x_v$. You may assume that the real numbers labeling the nodes are all distinct. A node $v \in V(T)$ is a local minimum if the label $x_v$ is less than the label $x_w$ for all nodes $w$ that are joined to $v$ by an edge. |
|||||||||||||||||||||
|
|
As it stands, the definition is quite straightforward. A local minimum is simple a vertex where its label is less than the labels of all its neighbours. A completely made up example might be a vertex $v$ with label $5$, with a parent with label $10$ and children with labels $7$ and $9$. Then $v$'s label is less than all its neighbours, so it is a local minimum. Of course there can be more than one local minimum (as suggested by the local part). The fact that it's in a complete binary tree has no bearing on the definition, it's equally applicable to general graphs (or even hypergraphs, digraphs... pretty much anything where adjacency is well defined). As an additional note, this concept of "local minimum of a binary tree" is not a common notion, and doesn't appear as a usual property of a (complete) binary tree, though it does look like it might be related to search trees, or similar. |
|||
|
|
