BST AVL 红黑树

发表于 | 分类于 | 评论数： | 阅读次数：
本文字数： 415 | 阅读时长 ≈ 1 分钟

摘要

待续。。。

BST(二叉 树)

特点

任意一个节点的左子树都比他小，右子树都比他大

优点

不管是插入还是搜索都只需要和每一层中一个节点进行比较就可以，速度依赖于树的深度

缺点

数据趋势比较明显的话，递增，递减的话，会变为一个链表

复杂度

最差的情况下读和写的复杂度都是O(n)

AVL(自平衡二叉树)

特点

首先他本身是一个二叉树，他要满足一个特点，任何一个左子树和右子树的深度差绝对值小于1

复杂度

复杂度 O(lgn)

红黑树

特点

  • 每个节点要不是红节点要不是黑节点
  • root节点需要是黑节点 叶子节点也必须是黑节点
  • 红节点的子节点必须是一个黑节点
  • 新插入的节点是红节点
  • 从任意一个节点出发，到叶子节点的路径上 黑节点数量必须是一样的

优点

红黑树的平衡有两种情况

  • 左右树节点数相同
    • 左右树上限是节点数深度差一倍以内

没有平衡二叉树要求苛刻，平衡条件宽松，操作变动小

复杂度

复杂度 O(lgn)

数据插入