构建一颗红黑树,数据为15 13 11 17 9 7 5 2 画出插入的过程
时间: 2023-04-10 16:01:27 浏览: 80
好的,我可以回答这个问题。以下是红黑树的插入过程:
1. 首先将15插入根节点,颜色为黑色。
2. 将13插入15的左子节点,颜色为红色。
3. 由于13的父节点15是黑色,所以不需要进行任何操作。
4. 将11插入13的左子节点,颜色为红色。
5. 由于11的父节点13是红色,需要进行旋转和颜色调整。将11、13、15进行左旋,然后将13变为黑色,15变为红色。
6. 将17插入15的右子节点,颜色为红色。
7. 由于17的父节点15是黑色,所以不需要进行任何操作。
8. 将9插入11的右子节点,颜色为红色。
9. 由于9的父节点11是红色,需要进行旋转和颜色调整。将9、11、13进行右旋,然后将11变为黑色,13变为红色。
10. 将7插入9的左子节点,颜色为红色。
11. 由于7的父节点9是红色,需要进行旋转和颜色调整。将7、9、11进行右旋,然后将9变为黑色,11变为红色。
12. 将5插入7的左子节点,颜色为红色。
13. 由于5的父节点7是红色,需要进行旋转和颜色调整。将5、7、9进行右旋,然后将7变为黑色,9变为红色。
14. 将2插入5的左子节点,颜色为红色。
15. 由于2的父节点5是红色,需要进行旋转和颜色调整。将2、5、7进行右旋,然后将5变为黑色,7变为红色。
最终得到的红黑树如下图所示:
```
11B
/ \
/ \
7B 15R
/ \ / \
5B 9B 13B 17B
/ \
2R 6R
```
相关问题
构建一颗 红黑树 数据为 15 13 11 17 9 7 5 2 并且画出关系图
好的,我可以回答这个问题。以下是构建红黑树的过程:
1. 插入节点 15,作为根节点,颜色为黑色。
2. 插入节点 13,作为 15 的左子节点,颜色为红色。
3. 插入节点 11,作为 13 的左子节点,颜色为黑色。
4. 插入节点 17,作为 15 的右子节点,颜色为红色。
5. 插入节点 9,作为 11 的右子节点,颜色为红色。
6. 插入节点 7,作为 9 的左子节点,颜色为黑色。
7. 插入节点 5,作为 7 的左子节点,颜色为红色。
8. 插入节点 2,作为 5 的左子节点,颜色为黑色。
以下是红黑树的关系图:
```
13(B)
/ \
9(R) 15(R)
/ \ / \
7(B) 11(B) 17(B) NIL
/ \
5(R) 2(B)
```
构建一颗 红黑树 数据为 15 13 11 17 9 7 5 2 并且画出之间树
好的,我可以回答这个问题。以下是构建的红黑树,并附上相应的图示。
```
13(B)
/ \
9(B) 15(R)
/ \ \
7(R) 11(R) 17(B)
/ \
5(B) 2(B)
```
图示:
```
13(B)
/ \
9(B) 15(R)
/ \ \
7(R) 11(R) 17(B)
/ \
5(B) 2(B)
```
希望这个回答对您有所帮助。