红黑树 回顾

一、首先是二叉树:

1)定义

2)前、中、后序遍历

 

二、二叉搜索树:

中序遍历是有序的

本身的定义也是递归的:

1)查找:复杂度 log2n (n表示数的节点个数)

极端情况,退化成链表,查找效率和链表一样

2)插入节点、删除节点也要会

 

 

三、平衡二叉树:左右子树都是平衡二叉树

1)2-3树

2)AVL树

3)红黑树

都是平衡二叉树

 

四、AVL树:平衡因子 {-1,0,1} 

树的每一个节点,左子树和右子树的高度差都属于平衡因子中的一个值,即: -1,0,1

1)左子树高度减去右子树高度的差的绝对值小于等于1

2)通过四种操作来保持平衡

4种旋转操作:(旋转过程中树还是满足二叉搜索树的性质)

左旋:右右子树

              A                                                          B

                    B            -------左旋             A                  C

                           C

右旋:左左子树

               A                                                         B

        B                       -------右旋            A                  C

C

 

左右旋:左右子树

               A                                                        A                                                     C

         B                       ------先左旋            C                -------再右旋                B           A

              C                                            B

 

右左旋:右左子树

          A                                                      A                                                         C

                B               -------先右旋                C         -------- 再左旋             B           A

          C                                                               B

 

带子树的旋转情况,类似,但有可能要更换父节点;

左左、右右、左右、右左四种情况的旋转方式。

3、AVL树总结:
1)平衡的二叉搜索树

2)每个节点存放了平衡因子:-1,0,1

3)四种旋转操作

不足:节点需要存储额外信息、且调整次数频繁(消耗资源)

 

五、近似平衡二叉树(红黑树)

红黑树:近似平衡的二叉树,确保任何一个节点的左右子树的高度差小于两倍

优点:旋转频次低,维护成本低

满足如下条件的二叉搜索树是红黑树:

1)每个节点要么红色要么黑色

2)根节点是黑色

3)每个叶子节点是空节点,是黑色

4)不能有两个邻接的节点是红色

5)任何一个节点到每个叶子的所有路径都包含相同个数的黑色节点

 

时间复杂度:近似 log2n

调整频次也减小了很多

 

旋转:情况复杂,之前看过STL解析,回顾下即可

 

 

六:AVL树和红黑树的对比:

1、AVL树查找比红黑树快,是因为AVL树的严格平衡的

2、红黑树插入和删除要比AVL树效率高是因为,红黑树是近似平衡的二叉树,旋转频率更低

3、红黑树比AVL树需要的存储空间更低,因为AVL树需要一个二外的整数来存储平衡因子或者高度来计算,然而红黑树每个节点只需要一bit额外的信息,来标示红色还是黑色节点

4、红和树被广泛应用于C++的数据结构中,比如map、multiset、multimap中,而AVL树被用在数据库中,为了更快的查询效率

 

所以:

查询操作特别多,那么用AVL树

查询和插入操作差不多的话,用红黑树

上一篇:AVL(平衡二叉搜索树)的实现


下一篇:c++ 类实现 AVL树容器(包含迭代器)