Box2d源码学习<六>动态树的实现
本系列博客是由扭曲45原创，欢迎转载，转载时注明出处，http://blog.csdn.net/cg0206/article/details/8293049
今天我们将学习碰撞模块（collision）部分，该部分主要有一下内容：
1、 形状，该部分包括的定义、实现。
2、 操作形状方法，该部分包括距离(Distance)、撞击时间(Time of Impact)等。
3、 算法辅助类，包括动态树和broad-phase算法。用来提高系统的碰撞检测的速度。
其中前两项均以算法辅助类为基础的，所以我们开始学习这一项，今天我们将学习动态树部分，动态树顾名思义就是“会动的树”，在Bx2d中动态树是由b2DynamicTree类来实现的，它主要是通过用户数据来操作轴对齐包围盒（axis-alignedbounding boxes,AABBs）来完成树的各种操作，并不需要知道形状是什么东东。(如有童鞋像我开始一样，不知道AABB是何物，请记得我们还有维基百科啦)。同时动态树继承自AABB树，树上的每一个节点都有两个孩子。叶节点是一个单独的用户AABB。即便是惰性输入，整个数也可以使用旋转保持平衡。
好了，我们开始上正餐了。先看b2DynameicTree.h文件：
以上就是动态树节点插入的几种情况，主要做法就是：
a)、通过遍历树上的节点，对比aabb找到代价最小的节点A
b)、将A作为兄弟节点，先建一个父节点N，将A的父节点的孩子指针指向N，同时N将A和要插入的叶子节点L作为左右孩子节点连接起来
c)、如果出现树不平衡，旋转动态树，使它成为新的平衡二叉树。大家可以看到，目前上图倒数第一和第二幅图上的都还不是平衡树，这部分等到说的平衡树的函数的时候再弄。
另外关于box2d中的动态树，我们来思考一些问题，就是我们插入的节点会始终是树的叶子节点吗？如果不是的那些节点又到哪去了呢？如果是的怎么做到的呢？
关于这个问题先卖个关子，我们再看看删除叶子函数RemoveLeaf，还是先看图：
关于删除函数，主要步骤是：
a)、根据索引找到父节点、祖父节点、和兄弟节点
b)、将祖父节点的原本指向父节点的孩子指针指向兄弟节点，并释放父亲节点
c)、如果出现树不平衡，旋转动态树，使它成为新的平衡二叉树。
还要注意一点的就是我们插入的有用的信息都是叶子节点，剩下的节点全部都是辅助节点。等我们看到重新构建一棵新的二叉树的时候会对这方面有新的认识。
相信大家对节点操作有一定的认识了吧，现在知道上面问题的答案了吗？其实，不管插入还是删除还是我们下面要说的使树平衡的函数，叶子节点还是叶子节点，丝毫没有变成其他节点，我们插入的有用的信息都是叶子节点，剩下的节点全部都是辅助节点，插入的时候添加父节点，删除的时候同时也删除了父节点。等我们看到重新构建一棵新的二叉树的时候会对这方面有新的认识。
5、 对树的操作
哈哈，一棵平衡树就这样就成了，当然这个步骤不复杂，但是原理是一样的，就不介绍了。注意，我们可以看到，平衡操作后，叶子节点依然是叶子节点，我们所需要的信息还是在那里面。
下面我们说说RebuildBottomUp这个函数，它主要重新构建一棵树。
主要步骤是：
a)、获取所有叶子节点放入动态数组中，其他释放到叶子节点内存池中
b)、获取所有叶子节点中aabb最小的两个，申请一个节点，作为它们的父节点，形成一个新的子树
c)、用动态数组最后一个节点覆盖最小aabb的节点，用父节点放入动态数组aabb第二小的位置上。同时将动态数组中的节点个数减少一个。
d)、重复a、b、c步骤，直到动态数组中的节点个数为1个。
e)、获取头指针。
今天的动态树部分就说到这了，如有本人理解不妥或错误之处，望大家多多指正，同时也希望和大家多多交流。
