堆是完整二叉树(除了最后一层,其他层都被完全填满)的一种。根据根节点放置的是所有键值中的最大值还是最小值,堆被分为最大堆和最小堆。堆常用数组来存储。堆(heap)堆是一个完整的树(所有的层都被填满了,除了最后一层,最后一层有尽可能多的键)。堆的这个属性使它适合存储在数组中。堆不是最小堆就是最大堆。在最小堆中,根上的键必须是最小的(最小堆只保证子树的根部节点值小于左子树和右子树,最终保证了整个树根是

- 阅读全文 -

avl树的实现

AVL树是一种自平衡二叉搜索树(BST),对于所有节点,其左右子树的高度差不能超过1。大多数BST操作(例如:搜索,最大,最小,插入,删除)以O(h)为时间,h是BST的高度。对于倾斜的二叉树,这些操作的成本可能变成O(n)。如果我们确保在每次插入和删除之后树的高度仍然是O(Logn),那么我们就可以保证所有这些操作的O(Logn)的上界。AVL树的高度总是O(Logn),其中n是树中的节点数。左

- 阅读全文 -

树:与数组、链表、堆栈和队列(它们是线性数据结构)不同,树是分层数据结构。术语节点的度:一个节点含有的子树的个数称为该节点的度树的度:一棵树中,最大的节点的度称为树的度叶节点或终端节点:度为零的节点非终端节点或分支节点:度不为零的节点父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点兄弟节点:具有相同父节点的节点互称

- 阅读全文 -