红黑树（带有自平衡功能的AVL树） 1. 红黑树的规则特性： 节点分为红色或者黑色； 根节点必为黑色； 叶子节点都为黑色，且为null； 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）； 从任意节点出发，到其每个叶子节点…