Java零基础-237-自平衡二叉树数据结构原创

那行了，那咱们来看一看这个二叉树啊。这块呢，我就给他。删一下各位啊，删一下。来，呃，这块的话，咱们就直接叫做DAY30。对30啊，那么对30这块是叫做这个自平衡啊，自平衡二叉数。各位啊，平衡二叉树。保存一下啊，嗯，是这样的，什么是二叉树呢。当然分两个唱是不是？哎，分两个叉啊。来。自平衡二叉数。遵循什么呢？遵循左小。

又大原则。啊，遵循左小。存放。遍历二叉树的时候有三种方式，前续便利。中续便利。还有叫后续遍历，各位啊，前续遍历说的是跟左右，中续是左跟右。后续是左右跟，注意前中后说的是跟的位置，注意啊，注意前中后说的是根的位置。跟在前是前序，跟在中间是中序，跟在后面是后续啊。注意啊，跟在前面是。

跟在中间是中序。啊是中序，中序。跟在后面是后续便利。四平二叉树啊，遵循左小右大原则存放。便利。二、有三种方式，有。前中和后续前序是跟左右，左永远在右的左边，要记住啊，左永远在右的左边，各位啊。左跟右左右跟跟左右啊，然后大家注意。Set集合或者叫map集合，采用的是什么？采用的是中序便利方式啊，就是一迭代器啊，采用的是中方式啊。

中序便利方式。中啊，就是。跟右左跟右的方式，另外要注意自平衡，这是一个自平衡二叉数啊，就是出ET。或者叫map是自平衡二代数，遵循左脚右端原则存放，那现在我给我给大家一一堆数据啊。一堆数据啊，比如说嗯一呃一百二百。五十六十八十一百二一百四，然后130，嗯。130。然后是135吧，134。别别别134了180。

一米八有没有666。行吧，啊，就这堆数据啊，然后呢，我们把这堆数据。按照这个，呃，按照左小右大的原则，给它放到树上，各位。给它放到树上啊，我们放一下试一下啊，来第一个100。100是不是往里边存呀，所以这个时候呢，我们在这儿呢，就存进去一个100。那么这个100呢。这就是一个节点了。对吧？啊，这就是个节点啊，那么接下来呢，它遵循什么呀？左小右大的原则，假如说放200进去，左小右大原则，那么这个时候200是放到什么地方啊，200会放到幼子树上。明白吗？就它存放的时候有一个规则，它存放时候的规则是采用左小右大的原则存放的，那我问你，你既然采用左小右大的原则进行存放，那你是不是需要比较它的大小。

你好好思考一下，要靠这个原靠遵循左小右大的原则存放。存放时要依靠什么？要依靠左小右大。原则，所以这个存放的时候要进行比较。明白吧，要进行比较数字的话，可以直接。啊，不知道大家有没有理解这个东西啊。对。那这个时候他就放的时候，按照这个规则去存放一会儿采用中序便利的方式给他拿出来，我们看看是什么样的，好吧，那么存一个100进去之后呢，接下来200 200是左小右大，200:100要大，200比100大，放柚子树上。听懂了吗？诶，大家理解理解这个。为什么他要往柚子树上走。如果是。大于零的时候，为什么为什么往右子树上走，大家看见了吗？

这个T等于T点吧。这是不是就是那个T呀。是这个。对吧，是不是往右组上走了。大于零的情况就是十减五呗，十减五就是左边这个大呗。对吧，你想想现在是200啊。干啥呀，减去100吧，最后是不是大于零。大于零，这说明这个200是大的呀，200大往右组上走吗。对不对，所以说他这个时候呢，他就会把200放到这个位置上。200放到这儿。200放到放到这个位置上，柚子树上。啊。来。啊。是不是紧接着我们又来50，他50还是先和100进行比。明白吗？50和100比小于100，左小右大，所以50会放到左子数上。

它在存放的时候，它会一个元素一个元素进行比较，你拿出来一个50之后，这个50会先和我们的100进行比较，发现小于零啊。小于零的时候呢，就没有没有100大呀，没有100左子数啊，所以它往左子数上走了，小于零的时候，你看它是不是往左上面走了。对吧，小于零就往左子数上走了。看见了吧。哎，那么这个时候呢。左子，树上是空的呀。所以他马上就会把这个50放过来，他放到这儿了。明白吗？哎，放到那儿了。好。这样放过来。紧接着来一个什么呀，六十六十它还是会和我们的100进行比较，所以会减去100小于零，小于零之后一定是在左子数上，因为左小右大嘛。

左子上60 60回合50进行比较啊，所以60现在又减去50，它大于零啊。如果60减去50大于零的话，那应该是右子数，所以这个时候它60会放到50的右边，它会自动放到这个位置。明白吧，他在比，它在存储的过程当中，它会比较，比较比较完之后它就会放到左子数还是右子数上，它会这样决定。是不是，哎，60最终就放到这个位置上了。那么这个时候呢，我们的这个比，如果再往下再继续加的话，加的就是80啊，你加这个80的话，80和100进行比较啊，所以80减去100之后啊，它有一个结果是小于零的。小于零是左子数，那80会继续往下减去50啊对吧，有同学老师他会一直往下走吗？会的，你看这是个多循环吗？

它一直往下循环着走，是不是一直往下循环着走，是往左子数还是右子上跑啊，是不是那80减50它大于零啊，大于零的应该是什么呀？大于零呢就应该是幼子数。柚子数，但是上面有个60，那么这个时候80会和60相减呀，减去60之后是大于零，大于零还是柚子数啊。对吧，所以这个80应该放到60的右边，所以呢，这个数据最后啊，就是放到这儿了，这是80，哎呀，这个这个图画的80。对吧，它是这样去存放的。啊，然后接下来就是这个呗，等于是。是吧，然后一百二来了，一百二来了之后呢，一百二还会和我们的100进行比较，我就说了啊，一百二和我们的100进行比较，左，左小右大对吧，一百二在这儿，一百二和200比较对吧？诶诶左小右大。所以一百二是在什么地方，各位。

应该是在这儿吧。120比右右边大吗？大于100嘛，往右走。一百二和200进行比较。小于200吧。是不是放到这儿啊，好，这是120。那这个一百二呢，就放到这个位置上了。对吧，哎，往上点，然后呢，它是放在这个位置上的。好了。那再往下一百四呢，一百四往右边偏一百四小于它。举这个数据举的不太好啊。嗯，这个图画的来二二百二一百二一百二，那现在是一百四啊一百四各位一百四的话呢，应该是140，是放到左子数140。嗯，放到一百二的右边。

好吧。是这回事儿就行啊，100次。这个一百四放哪了呢？放到这个一百二的右边了。啊。一百二的右边啊。呃，然后接下来这样，各位啊。嗯。咱可以让它移动一下。行吧。移动一下啊各位。放这儿得了。行。这个。100。让它往这动一动。然后这块呢，你看P图呢是不是。是这个意思啊。来。啊，就就这么一个意思得了啊。

这么诡异呢，感觉。要求完美啊。我的天呐，就这么着吧。好了，那么接下来一百四再往下是130，那举一个数据是130，是不是那一百三这块呢。咱们接着往下走，应该是一百三在我的右边，一百三在左边，就一百三大于它在右边是吧，哎，那么一百三怎么着啊，小于140，哎呀这块。130。这个一百三是不是就到这儿了。对吧，哎，这样的没事啊，咱们看看到底最后画个什么鬼啊，135那135应该是在右边，135在左边，然后135在右边是吧？135应该是在左边啊。

135比130大，应该是135在这儿呢。画着画着不够了。我改改数据吧，各位啊。好，那一百八呢。一百八应该是在我们的右边，是不是一百八在左边，一百八呢，应该是在右边啊，然后一百八呢，应该是在右边，所以一百八呢，应该是在一百四的右边。一百八了。对吧。就是那个180。然后接下来呢，它这个666666的话是大于它大于它在右子数，那应该是666在这个位置上。对吧，666是不是放到这个柚子数上面了。对吧。那假如说这个时候来一个40呢，各位，我在这再加一个，假如说这会儿40来了一个，来一个40。

又来了个40，那40应该是小于它，40应该小于它，那40是应该在这个位置上。对。四是不是在这儿。对不对，往上。在这。对吧，然后紧接着呢，比如说这会儿来一个55。再来个55，各位。那55在哪啊。他这个数据这样加，加进去55在左边，55在右边对吧，55在左边，那55应该在哪啊在这吧，是不是根据这个算法，那就一直走一直走就加到这个位置上了。对吧。那这个55就是这样的。那各位它整个这个二叉树呢，最后它存放的时候就是这个结构了。它整个这个结构，那我问大家，我采用中序的方式给它取出来是什么样的。

采用中序，便历是左跟右各位。左跟右。明白吗？是不是这个东西啊。然后根是不是它这边是不是U。那我问你左跟右，左边是不是一棵树？它既然是一棵树，我问大家是不是我还会对它对这个子数进行左跟右啊，那是不是左是谁是不它。根是不是它呀，这是不是又啊。对吧，所以第一个先取出来是谁是40。40啊，根根是多少50啊对吧，那么左四十五十取出来之后呢，左跟右右边这边又是一个数，是一个数的话，它就会同一个算法，就是左跟右嘛，左跟右左的话是五十五六十八十。对吧，所以这个时候就是什么呀，就是55。60。对吧，80就取出来了。那五十五六十八十取出来之后呢，就相当于说我们整个这个就算结束了，因为你的左。

根右的算法结束了，左根对吧，右是不是那么等你这块结束之后呢，接下来这就是根啊。所以再往下会输出什么呀，100。100，然后再往下呢，左跟右右边这块我问大家是不是一个数。是一棵树的话，它会遵循左跟右吗？对吧，好，那么左边是谁，是不是这个这整个这这个是左，就是整个这一块什么意思，整个整个这块是一个左吗。对吧，哎，左左这边呢，是左是空的根对吧，右，所以说根是120。右边你看这是120，这是右边吧，来，所以这块首先第一个。是。左跟右左是空啊，根是120。右边是一棵树左跟右对吧，哎，然后左边右是一棵树左跟右。

所以一百三一百三十五吧，是不是就拿出来130。然后135 135之后呢，哎，左就结束了，根是一百四啊。右边是180。那到一百八结束之后呢，这个左这个根，还有这个右就结束了，那这个左就结束了，各位什么意思，整个这个左就结束了。结束后根用吗？所以这个时候呢，我们应该是200对吧，然后紧接着是什么呀？哎是666，所以说大家看，如果你采用这个左小右大的原则进行存放，然后最终采用中续便利的方式。中序是左跟右的这种方式进行遍历，取出的数据就是自动从小到大排序的，这就是这种数据结构，叫做自平衡二叉树的这种数据结构，各位啊，还是非常经典的一个数据结构啊，数据结构这个呢，可以这个提升我们的这个排序的这个性能啊，以及查找的性能都会啊，都会提升，因为我们在查找的时候，假如说我们查找的数据是大于100的，那么这时候我们会往柚子数上找。

对吧，你不会顾及左边这个东西，或者说你小于100的时候，你不需要顾及右边这个，对吧，它进行一个比较，一个比较就是最后呢，他查找啊，这种算法就。就查找的范围就会特别少啊，特别少，但是大家注意这里有个非常重要的东西，叫做遵循左小右大原则存放，那我问你大家有没有发现我刚才在存的时候。我存的时候。是不是一直都在比较大小。对吧，好各位这个方法是不是就是比较大小的。拿着这个K转成这个comparable，调comparable comp to方法是比较这个元素和这个元素，最后比较完之后是有一个结果，这个结果有可能是大于零，也有可能小于零，也有可能是等于零的，对吧？那最后比较完这个结果，就来决定我将来存到这个数上的哪个位置上，而且大家看这是个循环。这是个循环对吧，哎，我往上存这个55的时候，我是怎么存的，55先和100比。

发现比100小，所以从往左子数上走55，再和50比大于50，往右子上走55大于小于60，在左子数上，哎，八加到这个位置上，你看我在比较的过程当中，对吧，我就得通过这个方法。所以说你在你的程序当中啊，这里调用这个，呃，往这个集合里边添加这个元素的时候，这个元素啊，它在底层就会这个compare方法进行比较，而你这个compare方法呢，里边写的就是这个比较规则。明白什么意思吧？没有排序就直接存放吗？没有排序就直接存放，是一边存放一边排啊。一边存放一边排呀。什么叫没有排序就直接存放吗？是我放进去他才排的序。

明白吗？放的顺序，放的过程就是排序呢。存放的过程就是排序的过程啊。存放的过程就是排序的过程。取出来就是自动按照大小顺序排列的。那么这个时候比较尴尬的是什么呢？是字符串，它本身已经可以比了，所以你就不用管了，字符串int类型也可以比了，但如果说你这个集合里边放的这个类型是你自定义的类型，对不起，这个你得怎么着啊？哎，这个你就得自己在这实现这个compar接口了。啊。