Linux 内核常用数据结构
2020-02-09 本文已影响0人
黑小柴
红黑树
- 具有二叉搜索树的所有性质(lchild为较小元素, rchild为较大元素)
- 根节点是黑色的
- 所有叶子节点有左右孩子, 且左右孩子为黑色的空节点
- 不存在父子都为红色节点的情况
- 寻迹空节点的每一条路径上包含的黑色节点数量相同
平衡二叉树: 左右子树都是平衡二叉树, 且左右子树的深度差不超过1
红黑树并不是平衡二叉树, 他的平衡是大致的, 红黑树的性质保证了从根节点到叶子节点的最长路径长度不会超过最短路径的2倍, 性能要优于平衡二叉树.
通用链表
结构List_head中包含两个指针, 一个前指针, 一个后指针. 一个list_head结构描述链表中的一个节点. 空节点前后指针指向自身.
