目录

树的遍历方式

平衡二叉树

旋转机制

左旋

右旋

旋转实例

左左

左右

右右

右左

总结

红黑树


相关概念

节点的内部结构如下

二叉树与二叉查找树的定义如下


树的遍历方式

前序遍历:当前节点,左子节点,右子结点
中序遍历:左子节点,当前节点,右子结点
后序遍历:左子节点,右子结点,当前节点
序遍历:一层一层的遍历


平衡二叉树

定义:树的任意节点左右子树高度差不超过1。

旋转机制

平衡二叉树拥有左旋右旋两种机制。当添加一个节点之后,若该树不再满足平衡二叉树的定义,则会触发旋转机制。

左旋

普通情况

复杂情况


右旋

普通情况 

复杂情况 


旋转实例

左左

左右

右右

右左

总结

① 左左:一次右旋
② 左右:先局部左旋,再整体右旋
③ 右右:一次左旋
④ 右左:先局部右旋,再整体左旋


红黑树

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部