VvfzZ

Posted on

二叉树

  • 在二叉树的第i层上至多有2^(i-1)个结点（i>=1）。
  • 深度为k的二叉树至多有(2^k)-1个结点（k>=1）
  • 对于任何一颗二叉树T，如果其终端结点(叶子结点)数为n0，度为2的结点数为n2，则n0=n2+1。
  • 具有n个节点的完全二叉树深为log2x + 1（其中x表示不大于n的最大整数）。

AVL树

平衡二叉树&二叉查找树
任何节点的两个子树的高度最大差别为1

红黑树

红色结点不连续，任何结点到所有叶子的黑高相同
效率(查找、插入、输出) O(logN)

为什么需要红黑树？

避免二叉树树有序插入时，退化为链表，查找效率退化为O(N)
红黑树维持弱平衡（高度更高），避免AVL严格控制平衡带来的性能损耗
AVL适合查找多，增加删除少的情况

0%