二叉树存在的问题
假如说你依次插入 1 2 3 4 5 6 这六个元素, 此时二叉树就会形成一个单链表..
这样的话,虽然插入的速度没有受到影响,但是查询速度会很慢, 甚至比纯链表查询速度还要慢,原因是二叉树查询的时候会判断左右两个子节点是否为空.
而平衡二叉树解决了二叉树上面这种插入顺序的元素变成链表的问题.
什么是平衡二叉树
平衡二叉树是一种特殊的二叉树，所以他也满足前面说到的二叉树的两个特性，同时还有一个特性：
它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
平衡二叉树的实现方法
1.红黑树
2.AVL算法
3.替罪羊树
4.Treap树
5.伸展树
平衡二叉树插入图解
大家也看到了前面[35 27 48 12 29 38 55]插入完成后的图，其实就已经是一颗平衡二叉树啦。
那如果按照[12 27 29 35 38 48 55]的顺序插入一颗平衡二叉树，会怎么样呢？我们看看插入以及平衡的过程：
这棵树始终满足平衡二叉树的几个特性而保持平衡！这样我们的树也不会退化为线性链表了！我们需要查找一个数的时候就能沿着树根一直往下找，这样的查找效率和二分法查找是一样的呢！
一颗平衡二叉树能容纳多少的结点呢？这跟树的高度是有关系的，假设树的高度为h，那每一层最多容纳的结点数量为20+22+…+2^(h-1)。这样计算，100w数据树的高度大概在20左右，那也就是说从有着100w条数据的平衡二叉树中找一个数据，最坏的情况下需要20次查找。如果是内存操作，效率也是很高的！但是我们数据库中的数据基本都是放在磁盘中的，每读取一个二叉树的结点就是一次磁盘IO，这样我们找一条数据如果要经过20次磁盘的IO？那性能就成了一个很大的问题了！那我们是不是可以把这棵树压缩一下，让每一层能够容纳更多的节点呢？虽然我矮，但是我胖啊…
若有收获，就点个赞吧
0 人点赞
