目录
树
相关概念
节点的内部结构如下
二叉树与二叉查找树的定义如下
树的遍历方式
前序遍历:当前节点,左子节点,右子结点
中序遍历:左子节点,当前节点,右子结点
后序遍历:左子节点,右子结点,当前节点
序遍历:一层一层的遍历
平衡二叉树
定义:树的任意节点左右子树高度差不超过1。
旋转机制
平衡二叉树拥有左旋和右旋两种机制。当添加一个节点之后,若该树不再满足平衡二叉树的定义,则会触发旋转机制。
左旋
普通情况
复杂情况
右旋
普通情况
复杂情况
旋转实例
左左
左右
右右
右左
总结
① 左左:一次右旋
② 左右:先局部左旋,再整体右旋
③ 右右:一次左旋
④ 右左:先局部右旋,再整体左旋
红黑树
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 数据结构(树、平衡树、红黑树)
发表评论 取消回复