Skip to content

算法

一、二叉树(Binary Search Tree)

特性

  • 左子树上所有结点的值均小于或等于它的根结点的值
  • 右子树上所有结点的值均大于或等于它的根结点的值。
  • 左、右子树也分别为二叉排序树。

分析

通过查找10可以看出查找方式是二分法的查找思想,查找次数等同于二叉查找树的高度。插入新的节点也是类似的方法,通过一层一层比较找到合适的节点插入

缺陷

容易导致不平衡

二、平衡二叉树

具有二叉查找树的全部特性

每个节点的左子树和右子树的【高度差】至多等于1

三、红黑树(Red Black Tree)

平衡树是为了解决二叉查找树退化为链表的情况,而红黑树是为了解决平衡树在插入、删除等操作需要频繁调整的情况

红黑树是一种自平衡的二叉查找树,除了符合二叉查找树的基本特性外,还具有一下附加特性

  • 节点是红色或者黑色
  • 根节点是黑色
  • 每个叶子节点都是黑色的空节点(NIL节点)
  • 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

有了以上特性可以保证

  • 可以保证红黑树的自平衡
  • 红黑树从根到叶子的最长路径不会超过最短路径的2倍

旋转和变色

AVL树与红黑树(RB树)的区别与联系

  • AVL是严格的平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多
  • 红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低开销;
  • 所以简单说,查询多选择AVL树,查询更新次数差不多选红黑树
  • AVL树顺序插入和删除时有20%左右的性能优势,红黑树随机操作15%左右优势,现实应用当然一般都是随机情况,所以红黑树得到了更广泛的应用 索引为B+树 Hashmap为红黑树

其他数据结构

  • 完全平衡二叉树
  • 哈希表
  • B树
  • B+树