Hello everyone . This lecture of Data Structures and Algorithms is Chapter 6 tree. 大家好。数据结构与算法这一讲的内容是第6章树。
Today we introduce a parent pointer notation and union-find sets . 我们今天介绍父指针表示法以及并查集。
In some applications, we just need to know the information of parent pointer. 在某些应用里面，我们只需要知道父指针的信息。
In this case , we only need to save the information of a parent pointer domain 那在这种情况下，我们只需要保存父指针域的信息，
and do not need to save the information of child nodes. We can use the array to store nodes. 不需要保存子结点的信息。我们可以用数组来存储结点。
For these nodes , the location of their parent can be expressed by a pointer 那这些结点，它们的父指针的位置就可以通过
This is a static array of pointers . 数组的下标来表示。这是一个静态的 指针数组。
Important algorithm of father pointer arithmetic method, first is to query the root node. 父指针表示法里面的重要算法，首先就是查询结点的根。
Then we depart along its parent pointer chain can easily trace back to the root from a node . 那我们从一个结点出发沿着它的父指针链可以很方便地追溯到根。
With such an operation of the investigation of the root, we can easily 那有了查根的这么一个操作，我们就可以很方便地
determine whether two nodes are in the same subtrees. 判断两个结点它们是不是在同一个子树里面。
That, of course , if they have the same root , they are in the same subtree , otherwise in the different subtree. 那当然如果他们具有同样的根，就是在同一个子树，否则就在不同的子树。
Union-find sets are very important 并查集它是一种非常重要的
Abstract data types and like stack and queue has been widely applied . 抽象数据类型，就像栈和队列一样有着广泛的应用。
The application of union-find sets is mainly to solve the problem of equivalence classes . 那并查集的应用主要是用于求解等价类的问题。
So what is the equivalent class? First we look at the equivalence relation . 那什么是等价类？首先我们来看一下等价关系。
The set S has n elements, 那集合S它具有n个元素，
There is a set of relations above S. 另外在这个S之上有一个关系集，
The relationship is an equivalence relation . Equivalence relation 那它的关系是等价关系。等价关系
is reflexive , that is, x is equivalent with itself. 具有自反性，也就是x本身跟自己是等价的。
Symmetry means that if x is equivalent with y, 对称性指的是如果x跟y等价，
So y is also equivalent with x. It is also transitive, 那么y跟x也等价。还有传递性，
That is, if x is equivalent with y , y equivalent with z, then x is also equivalent with z. 也就是如果x跟y等价，y跟 z等价，那x跟z也是等价的。
This equivalence relation can be expressed by the 这个等价关系，我们可以用
Basic arithmetic operations: equal 基本的算术运算里面的相等
This analogy. Let us imagine , they are very relevant . 这样来类比。大家想一想，是挺相关的。
After there is equivalence relation , you can divide equivalence classes . 那有了等价关系以后，就可以来划分等价类。
The equivalence class 等价类是指
is the largest set of elements in which each element is equivalent with each other. 具有相互等价关系的元素所组成的最大的集合。
In the set, of course, they are equivalent . 在集合里面，它们当然是等价的。
While all other elements outside the set are not equivalent with the elements inside. 而集合之外的所有其他元素，都跟整个这个集合的元素
Under this condition, we divide the set S into 不等价。那这样的话，我们由这个等价关系就可以把
several disjoint equivalence class according to the equivalence relation, 这个大集合S划分为若干个不相交的
which are the equivalent subsets. 等价类，也就是这个等价的这些子集。
We can use a tree to represent the equivalence classes , 我们可以用树来表示等价类，
And we can use the relevant operation of tree 而且可以用树的相关运算来实现等价类的
to implement the union-find algorithm. 并查算法。
Then when we use the tree to represent the equivalence classes , firstly 那我们用树来表示等价类的时候，首先
we need to represent the set. The set can be seen as 我们就是要表示集合。那这个集合，我们可以看作是
the subset of the whole tree. 整棵这个子树就是一个子集。
It is clear that we can use the root to represent the subset. 那显然我们可以用根来代表这个子集。
We can use a static array of pointers 树的实现方法，我们
to implement the tree. 可以用静态的指针数组来实现。
In this array, 在这个数组里面我们把
we put each node into a one-dimensional array, and the information of their parent 每一个结点我们依次存在一个一维的数组里面，而它们的
is just the subscript of its position. 父结点信息就是父亲所在的位置的下标。
Then we look at the example of UNION algorithm. 那我们来看一下UNION算法的例子。
For this set with ten elements, 那对这个具有十个元素的这么一个
I give out the five equivalent pair. 集合，那我给出了这五个等价对。
After we dealing with it, it becomes five equivalence classes . 那我们经过处理以后，就变成了 五个等价类。
Then , I will give out two equivalent pair. 然后，我再给出两个等价对。
After that, we find that the node of K is C, 那给了这两个等价对，我们发现，首先K它的结点是C，
But they are in different sets , so they are merged. 那它们在不同的集合里面，因此把它合并。
At this time, we use any of these as the root. For the other relation, 那这个时候我们用任意一个当根就可以了。对另外一个关系对，
the same treatment makes it. 也是这样的处理。
Then we look at the implementation of the union-find algorithm 那我们来看一下父指针
in the parent pointer notation. 表示方法里面并查算法的实现。
Similar as our general data structure, we will have 跟我们的一般的数据结构类似，我们会有
such operations as finding this element and modifying it. 查这个元素啊、还有修改啊这样的相应的操作。
In the union-find algorithm , the most important is 在并查算法里面，最重要的就是啊读
to read parent pointer and the assignment of parent pointer. 父指针以及对父指针进行赋值这样的操作。
Still further, we need to know how many nodes there are in the subtree, 另外还有，我们需要知道整个这个子树里面
that is, the number of elements in this set . 有多少个结点，也就是这个集合有多少个元素。
The Union / Find algorithm, it is clear that 那Union/Find算法，它显然
There is a Find the most critical algorithm which is to find 最关键的有一个Find算法，也就是查找这个结点
the root of the node. Union is to merge these sets of these two nodes 它所在的根节点信息。Union就是合并这两个结点
that is, the subtrees. 所在的这个子集，也就是子树。
The Find algorithm is very simple. 那Find算法非常简单。
We are starting from a node , you can follow the pointer to its parent chain up 我们从一个结点出发，可以顺着它的父指针链一直往上找。
until a particular node , if it has no parent pointer , that means that it is the root, 找到某一个结点，如果它没有父指针了，那就表示它是根，
Return the root. Union algorithm , first 把这个根返回。Union算法，首先
To find the root of the two nodes which will be merged. 要找到这两个带合并的结点它们所在的根结点。
Find out whether the root node is the same. If so, you do not need to merge them. 看看这个根结点是不是一样。如果一样就不需要再进行合并了。
If not, then we have to look at the subtree represented by the root 如果不一样的话，我们要看一下这个根结点所代表的子树，哪一颗子树的
and find out which has more elements. 元素个数更多。
Then we put the more one as the new root. 那我们把更多的那个当做新的这个树的
Then put the root of the less one 树根，然后把那个数目少的那个根
to directly point to the new root . 就直接指向这个新的根。
Then we look at the use of the weight balance, 那我们来看使用这个重量的权衡考虑以后，
We deal with the equivalent pair (H, J). 我们处理等价对（H,J）。
The root of H nodes is D, 那H结点它所在的子树根是D，
The root of J is F, and it is clear that subtree of F 那J是F，那F的子树它显然
has less elements , so F points to D. 它的元素个数更少，所以F指向D。
In that process of search, we can see that 在刚才我们查找的这个过程中，我们可以看到，
from H to D there may be a relatively long line routing. H到D的过程中有可能有一条比较长的组线路径。
For the nodes in the routing, 那这些组线路径上头所遇到的点，
In fact, we do not care about the parent-child relationship or the brotherhood relationship. 其实我们并不关心它们之间的这个父子关系啊、兄弟关系是什么样的。
What we are only interested in is the root of it. 我们只关心它的根结点是谁。
Then we want to know can we put all the nodes in this path 那我们就想能不能够把这个路径上头的所有的结点
as the child of the root directly. 就直接都作为根的子结点。
This effect makes the whole tree shorter, 这个效果就使得我们整个树它
and the overall query efficiency will be greater. 变得更矮，那整体的查询效率就会更高。
If we apply such a path compression technology , we can produce a very shallow tree. 那如果我们应用这样一个路径压缩的技术的话，那我们就可以产生极浅的树。
Then we will look at process of the use of path compression rule for Find (H). 那我们再来看采用路径压缩规则处理Find（H）这个过程。
In the Find (H), we start from the current node until we find the roots. 那在Find（H），从这个当前结点出发一直找到根。
This path includes the node H , and the other node , except the root, 在这个路径上，包括这个起始的这个H结点， 以及其他的结点，除了根以外，
Then we put all the nodes on the path to point to the root node . 那我们把这个路径上所有的结点都给它指向根结点。
Then this is the compression process. Then we see the compression algorithm. 那这就是压缩的过程。那我们看压缩算法。
For the Find algorithm, return value is ultimately 我们这个Find算法，它的最终的返回值就是
the root of the subtree. If we adopt a recursive algorithm to write, 这个子树的树根。那我们如果采用递归的算法来写，
For each node, we will 那我们在每个结点，我们都
set its parent as the final return root node . set它的parent等于最终返回的那个根结点。
Because deep down layer by layer recursion is invoked . 因为递归是一层一层往下深入调用的。
After we get the root, layer by layer we return . So then, 那得到这个根以后，我们又一层一层的逐层返回。因此，
All nodes in the search path all point to the root node . 在这个查找路径上头的所有的结点， 它们都指向了根结点。
Path compression algorithm's efficiency is very high. 那路径压缩算法它的效率是非常高的。
Of course you want to add this weight to a comprehensive consideration. 当然要加上这个权重的一个综合考虑。
We do n times Find operation for the n nodes, 我们对n个结点进行n次Find操作，
After sharing equally, the time of each operation is log * n. 那均摊下来它的每一次操作的时间是log*n。
For the log * operation, it is actually n = logn 这个log*的操作，它实际上是n=logn
For such an operation , the value obtained is equal to 1 or less 这样一个操作，啊它所得的值在小于等于1之前所要
For the number of times of the logarithm of n. If we do the log* operation for 进行的对n取对数的次数。那我们对
65536 呃65536，呃
that is, do log to n 进行log*的操作，也就是反复对这个值
repeatedly. 取log。
Ultimately what we need is only four operations, we can achieve 那最终我们只需要4次操作，就可以达到
Such a stop condition as the value less than or equal to 1. 这样的一个小于等于1的这个停止条件。那
The log* operation is much faster than the log operation. log*的操作它比log操作要快捷很多了。
In many cases , it is actually close to the time of Θ(1) . 在很多情况下，它其实接近于Θ(1)的时间代价。
Therefore , the Union / Find operations is similar to the push and pop operation in the stack, 因此， 这个Union/Find操作它就类似于我们栈里面的
it is a constant level operation . 入栈出栈操作，它是一个常数级的操作。
In many applications, some operations on equivalence classes can be well supported. 那在我们很多应用里面，它都能够很好地支持一些对等价类的操作。
Finally leave you two thinking questions . In this algorithm, 最后留给大家两个思考题。那在我们这个算法里面，都是采用的
we save the nodes in a static array and its parent pointer is actually 就是把这个结点存在一个静态数组里面，然后它的父指针实际上是
the subscript of its parent node in the array. In this way the parent node is represented. 数组里面的父结点所在的下标，这样来表示的它的父指针信息。
If we adopt the "new" methods to apply in the heap, 那如果我们采用new的方法，来从堆里面去申请
for the true dynamic pointer, how do we achieve such parent pointer notation. 真正的动态指针，那我们怎么实现这样的父指针的表示方法。
In addition, the weight balance and path compression methods for union-find sets 另外，并查集的权重和路径压缩的方法
have many variants, please look them up and discuss the Similarities and differences and their pros and cons for various approaches 有很多的变种，请大家查阅一下，并且讨论各种方法的
Thank you. 异同和它们的优劣。谢谢。