• 属于二分搜索树
  • 属于平衡二叉树

    1. 何为 2 - 3 树

  • 满足二分搜索树基本性质

  • 节点可以存放一个或者两个元素

image.png
每个节点有两个或者3个元素

  • 2 - 3 树是一颗绝对平衡的树,即每个节点高度一致

    2. 2 - 3 树如何维持绝对平衡

    image.pngimage.pngimage.png

3. 红黑树 与 2 - 3 树 的等价

image.pngimage.png
红 : 和父亲节点表示 2- 3 树中的 3 节点,所有红色节点左倾斜
image.pngimage.png

  • 从任意一个节点到叶子节点,经过的黑色节点是一样多的,保持 “ 黑平衡的二叉树 “,最大高度 2 log n => O ( log n )
  • 假如需要增删查改 红黑树
  • 只要查询 avl 树

image.png

红黑树添加元素:

image.png
image.png
image.pngimage.png
image.png