B Tree

B Tree

B树相对于平衡二叉树的不同是:每个节点包含的关键字增多了。

  • 特别是在B树应用到数据库中的时候,数据库充分利用了磁盘块的原理(磁盘数据存储是采用块的形式存储的,每个块的大小为4K,每次IO进行数据读取时,同一个磁盘块的数据可以一次性读取出来)把节点大小限制和充分使用在磁盘快大小范围;
  • 把树的节点关键字增多后树的层级比原来的二叉树少了,减少数据查找的次数和复杂度。
阅读更多
Binary Search Tree 二叉搜索树

Binary Search Tree 二叉搜索树

简称 BST,也称二叉排序树或二叉查找树。

特点:

  • 任一结点 > 其左子树的所有结点,
    并且< 其右子树的所有结点;
  • 结点的左、右子树,也是二叉排序树;
  • 每个结点键值唯一(不能重复)

重要性质:

  • 中序遍历二叉排序树得到递增序列

所以判断 1 棵二叉树是否是二叉排序树?
只要中序遍历,得到递增序列才是。

阅读更多

二叉树遍历

二叉树遍历主要包括:

  • 深度优先遍历
    • 前序遍历(递归法,迭代法)
    • 中序遍历(递归法,迭代法)
    • 后序遍历(递归法,迭代法)
  • 广度优先遍历
    • 层次遍历(迭代法)
阅读更多

:D 一言句子获取中...

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×