现有问题:该树可以视为数组和链接列表之间的数据结构。它具有快速的查询速度,并且具有快速的插入和删除速度。但是,在树上的极端或严重的失衡下,它将导致低效率
红色和黑色树木折叠中二元树的不平衡带来的低效率问题
什么是自我平衡的红色和黑树
红树插入场景
1.红树和黑树是空的
1.1将节点插入根节点,然后将节点设置为黑色
2.插入节点的父节点是黑色节点
2.1直接插入
3.插入节点的父节点是红色节点
3.1存在叔叔节点,是红色节点
1.位置P节点和S节点设置为黑色
2. PP节点设置为红色
3. PP设置为当前插入节点
4.再次重复上述步骤
3.2不存在节点叔叔或叔叔节点是黑色的
3.2.1 p节点是PP节点的左节点
3.2.1.1插入节点是p节点的左节点
1. P设置为黑色
2. PP节点设置为红色
3. PP节点右旋
3.2.1.2插入节点是p节点的正确节点
1. P节点左旋转
2.将P设置为插入节点(目前等于上述场景)
3. PP节点右旋
3.2.2 p节点是PP节点的右节点
3.2.2.1插入节点是p节点的正确节点
1. p节点设置为黑色
2. PP节点设置为红色
3. PP节点左旋转
3.2.2.2插入节点是p节点的左节点
1. P节点右旋
2.将P设置为插入节点(目前等于上述场景)
3. PP节点左旋转
PP节点左旋转
3.2.2.2插入节点是p节点的左节点
1. P节点右旋
2.将P设置为插入节点(目前等于上述场景)
3. PP节点左旋转