您当前的位置: 首页 > 

程序员之路:简单学习红黑树

彭世瑜 发布时间:2018-05-05 11:01:31 ,浏览量:3

二叉查找树(BST)

binary search tree

1.左子树上所有结点的值均小于或等于它的根结点的值。

2.右子树上所有结点的值均大于或等于它的根结点的值。

3.左、右子树也分别为二叉排序树。

这里写图片描述

红黑树

red black tree ,自平衡二叉查找树

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点(NIL节点)。

4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这里写图片描述

红黑树的操作:

- 变色
- 旋转 
    - 左旋转  
    - 右旋转

参考:

  1. 漫画算法:什么是红黑树?
关注
打赏
1688896170
查看更多评论

彭世瑜

暂无认证

  • 3浏览

    0关注

    2727博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文
立即登录/注册

微信扫码登录

0.0751s