平衡二叉树学习

原创
2016/07/06 11:20
阅读数 108

1. 二叉树:每个节点最多有2个子树,分为左右子树,且次序不能颠倒。树的第i层最多有2^(i-1)个节点。

2. 二叉排序数(BST):又称二叉查找树。性质如下: 

  • 若左子树不为空,那么左子树上所有节点的值均小于它的根节点的值。
  • 若右子树不为空,那么右子树上所有节点的值均大于它的跟节点的值。
  • 左右子树也都是二叉排序树。
  • 没有键值相等的节点。

    查找

    若根结点的关键字值等于查找的关键字,成功。
    否则,若小于根结点的关键字值,递归查左子树。
    若大于根结点的关键字值,递归查右子树。
    若子树为空,查找不成功。

    一直往左走就得到最小值,一直往右走就得到最大值。

    插入:从根节点开始,遇键值较大就向左,键值较小就往右,直到尾端就是插入点。

    删除

  • 如果只有一个子节点,则将子节点移至父节点。
  • 如果有两个节点,则以右子树中最小节点代替(一直往左走就是最小节点)。

3. 平衡二叉树(AVL):是在二叉排序树上引入的。左右子树深度之差不大于1。这样就保证查找的时间复杂度在O(logn)以内。所以在每次删除和插入节点的时候要保持二叉树的平衡。

4. stl中的map和set就是基于AVL的,通常是红黑树。注意这个map与hash_map不一样,hash_map是基于hash表的,即通过key可以直接找到value存放的地址。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部