已发布·持续改进
树与堆 指南 · 1/6
本章目前仅提供英文版。
Arrays and linked lists put data in a single line. Hierarchical data, such as folders inside folders, an org chart or the tags of an HTML page, does not fit a line well. The structure built for it is the tree. Restrict a tree one way and you get the binary search tree, which finds keys in sorted data quickly. Restrict it another way and you get the heap, which hands you the smallest (or largest) value quickly. This chapter sets up the vocabulary and intuition for all three.
A tree is made of nodes joined by edges, with these properties:
In graph terms, a rooted tree is a connected acyclic graph with one node chosen as the root.
| Term | Meaning |
|---|---|
| Parent, child | Nodes directly connected by an edge, above and below |
| Siblings | Nodes that share a parent |
| Leaf | A node with no children |
| Internal node | A node with at least one child |
| Depth | Number of edges from the root to the node (the root has depth 0) |
| Height | Number of edges from the node down to its farthest leaf (a leaf has height 0) |
| Subtree | A node together with all of its descendants |
| Degree | Number of children of a node |
The height of a tree is the height of its root. A single-node tree has height 0, and the empty tree is conventionally -1. Some textbooks count height in nodes instead of edges, so check the definition before solving a problem.
A binary tree is a tree where every node has at most two children, called left and right. Common shapes:
In Python a node is a small class.
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def size(node):
if node is None:
return 0
return 1 + size(node.left) + size(node.right)
# 8
# / \
# 3 10
# / \ \
# 1 6 14
root = Node(8, Node(3, Node(1), Node(6)), Node(10, None, Node(14)))
print(height(root), size(root)) # 2 6A binary search tree is a binary tree where, at every node, all keys in the left subtree are smaller and all keys in the right subtree are larger. Starting at the root, each comparison discards an entire subtree, which is the same effect as binary search on a sorted array. An in-order traversal (left, node, right) visits the keys in ascending order.
The rule applies to whole subtrees, not just to the immediate children. To check that a tree is a BST, pass the allowed range down as you recurse.
def is_bst(node, low=float("-inf"), high=float("inf")):
if node is None:
return True
if not (low < node.key < high):
return False
return is_bst(node.left, low, node.key) and is_bst(node.right, node.key, high)
print(is_bst(root)) # TrueSearch, insert and delete in a BST cost time proportional to the height h. With well-spread keys, h is about log2 n, but inserting keys in sorted order (1, 2, 3, ...) produces a degenerate tree with h = n - 1. Self-balancing trees fix this by restoring their shape with rotations on every insert and delete. The two best known are the AVL tree, which keeps the height difference between the left and right subtrees of every node at most 1, and the red-black tree, which colours nodes red or black so that no path is more than twice as long as any other. This guide explains the idea only; in practice you use the implementation your language provides.
A binary heap is a binary tree with two properties. First, its shape is a complete binary tree. Second, in a min-heap every parent is less than or equal to its children (a max-heap is the reverse). The root therefore always holds the minimum, but siblings and separate subtrees are in no particular order. A heap is not sorted like a BST; it only guarantees where the smallest element is.
Because a complete binary tree has no gaps, it can be stored in a plain array in level order, with no pointers.
def parent(i):
return (i - 1) // 2
def left(i):
return 2 * i + 1
def right(i):
return 2 * i + 2
heap = [1, 3, 2, 7, 4, 5] # a min-heap
for i in range(1, len(heap)):
assert heap[parent(i)] <= heap[i]
print(heap[0], left(1), right(1)) # 1 3 4The heap is the most common way to implement a priority queue, an abstract data type that supports "insert a value" and "remove the highest-priority value". With a heap, both operations take O(log n).
A tree is a hierarchy in which every node is reached from the root by exactly one path. A binary search tree keeps smaller keys on the left and larger keys on the right, and its performance depends on keeping the height low. A heap only maintains a complete shape and parent-child order, which lets it live in an array and implement a priority queue efficiently.
0 条评论
登录 · 登录后即可发表评论。
来发表第一条评论吧。