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