红黑树是一种二叉查找树，但在每个节点上增加一个存储位表示节点的颜色，可以是RED或BLACK，通过对任意一条从…