查找算法(6)红黑树(RBT)
前言:
2-3树虽然能实现平衡性,但在插入和删除的过程中需要判断插入的节点是2-节点还是3-节点等一系列问题,实现复杂且会增加额外的开销,所以就提出了红黑树(发明者--Sedgewick,1987年)
一.基本概念
1. R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。
2.红黑树的特性:
(1)每个节点或者是黑色,或者是红色
(2)根节点是黑色
(3)叶子节点是黑色
(4)如果一个节点是红色,则它的子节点必定为黑色,且父节点也必定为黑色
(5)从一个节点到该节点的子孙节点所有路径包含相同数目的黑色节点(确保没有一条路径会比其它路径长出两倍)
3.调整平衡的方式?
(1)颜色变换
(2)旋转
二.RBT插入调整
1.无需旋转调整的情况
(1)插入的节点为根节点,将插入节点红染黑,简称rootOver
(2)父节点为黑色,blackParentOver,简称bpOver
2.需要旋转调整的情况,仅仅需要考虑父节点为红色的情况(下面的父节点默认为爷爷节点的左孩子,右孩子情况相反)
(1)叔叔节点为红色,插入节点可左可右;父叔节点染黑,爷节点染红,插入节点回溯至爷节点
(2)叔叔节点为黑色,插入节点为右孩子;左旋父节点,插入节点指向父节点,转化为(3)
(3)叔叔节点为黑色,插入节点为左孩子;父节点染黑,爷爷节点染红,右旋爷节点
3.结论:RBT插入调整最多旋转两次
三.RBT删除调整
1.删除红色节点,不会影响BH,也不会影响到性质4.无需调整,直接删除
2.其它无需调整的情况为
(1)当前节点为根节点,无论root什么颜色,直接染黑(rootOver)
(2)当前节点为红色,将节点染黑,结束,redOver
2. 删除左孩子,分为四种情况:
(1)兄弟节点为红色,兄弟节点染黑,父节点染红,左旋父节点
(2)兄弟节点为黑色,左右侄子都为黑色,兄弟节点染红,X回溯至父节点
(3)兄弟节点为黑色,左侄红,右侄黑,左侄染黑,右侄染红,右旋兄弟
(4)兄弟节点为黑色,左侄随意,兄弟变父节点颜色,兄弟父节点都染黑,左旋父节点
四.插入和删除演示
1.插入
依次插入[12,1,9,2,0,11,7,19,4,15,18,5]
(1)插入12,插入1
(2)插入9
(3)插入2
(4)插入0
(5)插入11
(6)插入7
(7)插入19
(8)插入4
(9)插入15
(10)插入18
(11)插入5
2.删除
占坑...
三.性质分析
性质1:一棵大小为N的红黑树高度不会超过2logN
(最坏的情况是最左边的节点全部是3-节点,而其余为2-节点)
性质2:一棵大小为N的红黑树中,根节点到任意节点的平均长度为~1.00logN
(红黑树保证所有操作运行时间都是对数级别的)
四.红黑树相比AVL树的优势在哪?
红黑树的查询性能略微逊色于AVL树,因为他比avl树会稍微不平衡最多一层,也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较,但是,红黑树在插入和删除上完爆avl树,avl树每次插入删除会进行大量的平衡度计算,而红黑树为了维持红黑性质所做的红黑变换和旋转的开销,相较于avl树为了维持平衡的开销要小得多