12/1/31

AVL tree, Splay tree, B-tree

An AVL tree is identiacal to a binary search tree, except that for every
node in the, the height of the left and right subtree can differ by at most
1.
The basic idea of the splay tree is that after a node is accessed, it is
pushed to the root by a series of AVL tree rotation. By restructuring we can
make future accesses cheaper on all these nodes.
A B-tree of order m is a tree with the following structural propertires:
The root is either a leaf or has between 2 and m children.
All non-leaf nodes (except the root) have between [m/2] and m children.
All leaves are at the same depth.

0 個人 回覆 (←點這裡回覆):

張貼意見

熱門文章

最新文章

網誌存檔