平衡树（AVL tree）

引入

• 之前学习的树，都不是平衡的，查找时需要一个一个往内比较，一个结点只储存一个值，数据量存储较大，树的深度会非常的深，导致数据查询时效率会十分的低，本次学习的平衡树就能解决这个问题

定义

• 平衡树，即AVL tree，命名来源于第一种该类型树的两个发明者Adelson-Velsky 和 Landis，有时也叫Balanced tree，平衡树是一种能自我保持“平衡”的二叉搜索树，在一颗平衡树中，两颗子树之间的高度差最多不超过1，当他们之间的高度差超过1时，它就会自动重新平衡树的高度以恢复这种性质

平衡树的一些特性

• 查询、插入和删除在最坏情况和平均情况下都是花费O(log n)的时间，相对于一般的二叉树，降低了树的高度，提高了查询、插入、删除等效率
• 插入和删除可能需要对应部分的子树做一次或多次的旋转动作(后续红黑树中将会介绍到旋转的定义)

下面介绍和实现一种平衡查找树2-3查找树

2-3查找树

2-3查找树介绍

• 定义：2-3查找树是一种结点能储存最多两个元素最少一个元素的平衡树，储存1个元素的结点拥有2条子树边，称之为2-结点，储存2个元素的结点拥有三条子树边，称之为3-结点
• 2-结点：含有一个键(及其对应的值)和两条链,左链接指向2-3树中的键都小于该结点,右链接指向的2-3树中的键都大于该结点。
• 3-结点：含有两个键(及其对应的值)和三条链,左链接指向的2-3树中的键都小于该结点,中链接指向的2 3树中的键都位于该结点的两个键之间,右链接指向的2-3树中的键都大于该结点。
  
  一棵完全平衡的2-3树具有以下性质:

1. 任意空链接到根结点的路径长度都是相等的。
2. 4-结点变换为3-结点时,树的高度不会发生变化,只贿当根结点是临时的4-结点,分解根结点时,树高+1。
3. 2-3树与普通二叉查找树最大的区别在于,普通的二叉查找树是自顶向下生长,而2-3树是自底向上生长。

2-3查找树的查找过程介绍

实现2-3查找树的查找过程跟二叉树的查找过程几乎是一样的：

2-3查找树的不同情况下的插入过程：

1. 向2-结点插入新键：
   
2. 向一颗只含3-结点的查找树插入新键
   
3. 向一颗父结点为2-结点的3-结点插入新键
   
4. 向一个父结点为3-结点的3-结点中插入新键
   
5. 分解根结点
   
   在插入过程中，只要遇到含有四个子结点连接边的结点，就要对其进行平衡操作，以使其保持2-3的平衡定义

直接实现2-3树比较复杂,因为:

• 需要处理不同的结点类型,非常繁琐;
• 要多次比较操作来将结点下移;
• 需要_上移来拆分4结点;
• 拆分4结点的情况有很多种;

这里暂时不进行实现，但是需要对2-3树的思想着重进行理解，2-3查找树实现起来比较复杂，在某些情况插入后的平衡操作可能会使得效率降低。但是2-3查找树作为一种比较重要的概念和思路对于我们后面即将要讲到的红黑树、B-树和B+树非常重要。