乐趣区

关于java:红黑树

看不懂 找篇别的文章再看看吧

可在 O(logN) 工夫内实现查找、减少、删除

  • 节点是红色或彩色。
  • 根是彩色。
  • 所有叶子都是彩色(叶子是 NIL 节点)。
  • 每个红色节点必须有两个彩色的子节点。(从每个叶子到根的所有门路上不能有两个间断的红色节点。)
  • 从任一节点到其每个叶子的所有简略门路都蕴含雷同数目的彩色节点(简称黑高)。

左旋是将某个节点旋转为其右孩子的左孩子,而右旋是节点旋转为其左孩子的右孩子。

退出移动版