二叉搜索树、AVL树、红黑树

一、二叉搜索树

        基础的二叉搜索树构建出来可能会存在不平衡的现象,比如极端情况下,按照A B C D 顺序插入树中,结果为:

        但实际上我们更想要平衡一点的二叉搜索树,因为平衡的二叉搜索树能有效提高查询效率,比如上面的要查询D节点则需要比较4个节点才找到,而平衡的二叉搜索树只需要比较3个节点。
        所以AVL树的出现就是为了解决平衡性问题,它的核心内容就是平衡处理机制,即所谓的旋转,一共有四种形式的旋转:右单旋、左单旋、左右双旋和右左双旋。
        旋转的意义:旋转之后树整体的高度降低了,查找的深度降低,查询效率提高了。

二、平衡二叉树(AVL树)

AVL树是一种特殊类型的二叉树,它的每个结点都保存一份额外的信息:结点的平衡因子。
结点的平衡因子 = 左子树的高度 - 右子树的高度
插入和删除操作都会导致AVL树的自我调整(自我平衡),使得所有结点的平衡因子保持为+1、-1或0。
当子树的根结点的平衡因子为+1时,它是左倾斜的(left-heavy)。
当子树的根结点的平衡因子为 -1时,它是右倾斜的(right-heavy)。
一颗子树的根结点的平衡因子就代表该子树的平衡性。
保持所有子树几乎都处于平衡状态,AVL树在总体上就能够基本保持平衡。
当节点的平衡因子不为 (1、0、-1)时,就需要采取对应的旋转策略,通过旋转使得树达到平衡的状态。
四种旋转方式:

动图展示:http://note.youdao.com/noteshare?id=e41bfc4f987f181f843a2d6e65c8a977&sub=9DBB68B4B95041A5BA26D80AFC080772

1、当树的节点为 左左子树时需要 右旋:
  • 通过右旋操作(顺时针转)将平衡因子大于1的结点进行调整

2、当树的节点为 右右子树 时 需要 左旋
  • 通过左旋操作(逆时针转)将平衡因子大于1的结点进行调整
3、当树的节点为 左右子树 时 需要 左右旋

  • 先通过左子结点的左旋操作(逆时针转)转成LL形式,再通过右旋操作(顺时针转)将平衡因子大于1的结点进行调整

4、当树的节点为 右左子树 时 需要 右左旋
  • 先通过右子结点的右旋操作(顺时针转)转成RR形式,再通过左旋操作(逆时针转)将平衡因子大于1的结点进行调整

平衡二叉树不足:节点需要存储额外的信息(int类型的),并且调整次数过于频繁,导致树整体的维护成本过高。

举个例子:有的人喜欢整洁:桌面整理的很整体,那么导致的问题就是他整天把时间浪费在了整理桌子上面,导致他的工作效率低下。

三、红黑树

红黑树是一种近似平衡的二叉搜索树(Binary Search Tree),它能够确保任何一个节点的左右子树的高度差小于两倍。具体来说,红黑树是满足如下条件的二叉搜索树:

  1. 每个结点要么是红色,要么是黑色
  2. 根结点是黑色的
  3. 每个叶子结点(null结点、空结点)是黑色的
  4. 不能有相邻接的两个红色结点
  5. 从任一结点到其他每个叶子结点的所有路径都包含相同数目的黑色结点。

性质:从根结点到叶子节点的最长路径不多于最短的可能路径的两倍长。

AVL树和红黑树对比
  • AVL树提供了较快的查询速度------原因:因为AVL树相对于红黑树它是更加严格平衡的,说明它在某些情况下树的深度低于红黑树。
  • 红黑树提供了更快的插入、删除操作---原因:因为红黑树对应平衡不是太严格,不需要频繁的维护整棵树的平衡,减少了一些旋转操作。
  • AVL节点存储的信息相对于红黑树要更多---原因:AVL树存储平衡因子使用的是一个int类型的,而红黑树只使用了 1bit 大小的空间存储红、黑的状态。
  • 读多写少:使用AVL树;写多的情况下使用红黑树。

已有 0 条评论

    欢迎您,新朋友,感谢参与互动!