理解二叉树,平衡二叉树,红黑树

2018年3月6日 2点热度 0条评论 来源: 成都fly

c++的STL 中set,map是红黑树(红黑树是平衡二叉树的一种),我们需要深入理解红黑树,平衡二叉树的起源。

为什么要用红黑树? 红黑树的起源,自然是二叉查找树了,这种树结构从根节点开始,左子节点小于它,右子节点大于它。每个节点都符合这个特性,所以易于查找,是一种很好的数据结构。但是它有一个问题,就是容易偏向某一侧,这样就像一个链表结构了,失去了树结构的优点,查找时间会变坏。

红黑树就是一种平衡树,它可以保证二叉树基本符合矮矮胖胖的结构,但是理解红黑树之前,必须先了解另一种树,叫2-3树,红黑树背后的逻辑就是它。


平衡二叉树:
http://lib.csdn.net/article/datastructure/9204


红黑树:
http://blog.csdn.net/chen_zhang_yu/article/details/52415077

    原文作者:成都fly
    原文地址: https://blog.csdn.net/ceasadan/article/details/79454638
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。